CSC 321: Data Structures
Fall 2017

HW3: Algorithm Analysis


 

Part 1: Theoretical Analysis

Suppose you are given a list of dates and want to determine if all of the dates are within seven days of each other. For example, the dates in [9/20/2017, 9/15/2017, 9/21/2017] are within seven days of each other, but the dates in [9/20/2017, 9/15/2017, 9/21/2017, 9/23/2017] are not. Below are four different algorithms that attempt to determine whether all of the dates in a list are within seven days of each other.

For each algorithm, answer the following questions:

ALGORITHM A:
  1. Compare the first date in the list with every date later in the list.
    1. If the difference is ever more than seven days, then return FALSE.
  2. Repeat step 1 for each date in succession (i.e., the 2nd, 3rd, ...(N-1)th), comparing each with all dates that appear later in the list.
  3. If no comparison finds dates differing by more than seven days, return TRUE.

* * * * *

ALGORITHM B:

  1. Sort the list of dates into ascending order (earliest to latest) using merge sort.
  2. For each adjacent pair of dates (1st & 2nd, 2nd & 3rd, ..., (N-1)th & Nth), compare the pair of dates.
    1. If any adjacent pair is more than seven days apart, return FALSE.
  3. If no comparison finds dates differing by more than seven days, return TRUE.

* * * * *

ALGORITHM C:

  1. Sort the list of dates into ascending order (earliest to latest) using merge sort.
  2. Compare the first and last dates in the sorted list.
    1. If they are within seven days, return TRUE.
    2. Otherwise, return FALSE.

* * * * *

ALGORITHM D:

  1. Find the earliest date as follows:
    1. Let earliestDate = the first date in the list.
    2. Traverse the list, comparing each date with earliestDate.
    3. If you encounter a date that is earlier than earliestDate, then update earliestDate to be that date.
  2. Similarly, find the latest date as follows:
    1. Let latestDate = the first date in the list.
    2. Traverse the list, comparing each date with latestDate.
    3. If you encounter a date that is later than latestDate, then update latestDate to be that date.
  3. Compare earliestDate and latestDate.
    1. If they are within seven days, return TRUE.
    2. Otherwise, return FALSE.

 

Part 2: Experimental Analysis

For the second part of this assignment, you will develop and then utilize a program to compare the performance of ArrayList and LinkedList operations. Your program will need to generate large lists of values and measure the time it takes to perform operations on those lists. To perform the timings, use the StopWatch class, which has methods for measuring elapsed clock time (like a real-world stop watch). Be aware that clock time is affected by many factors other than code execution (e.g., background jobs, garbage collection) - minimize these factors by limiting background jobs and also performing multiple timings to identify and disregard outliers.

Recall that the get operation is O(1) for ArrayLists, but O(N) for LinkedLists. This means that the time it takes to perform a get operation on an ArrayList is independent of the size of the list, but proportional to the list size in the case of LinkedList. Thus, if you double the size of a LinkedList, the time it takes to perform a get operations should roughly double as well.

Your program should prompt the user for an initial list size and the number of get operations to measure. It should construct an ArrayList of that size (the actual values in the list are unimportant), and then use a StopWatch to time the specified number of get operations (using the index at the middle of the list). Similarly, construct a LinkedList of that size and measure the time required to perform the same number of get operations. Finally, repeat both tasks five times for increasingly larger lists (by factors of two), displaying the times in a table for easy comparison.

For example, the output of your program might look like the following (note: the times are purely fictitious):

Enter the initial list size: 100000 Number of get operations: 1000 list size ArrayList gets LinkedList gets --------- -------------- --------------- 100000 10 msec 50 msec 200000 10 msec 100 msec 400000 10 msec 200 msec 800000 10 msec 400 msec 1600000 10 msec 800 msec

Use your program to measure get operations using ArrayLists and LinkedLists of increasing sizes, and record the table of timings you obtain. The list sizes should be large enough to produce reasonable and consistent results. Do these experimental timings demonstrate the expected patterns for ArrayLists and LinkedLists? Justify your answers.

Next, modify your program so that it measures add and remove operations from the front of ArrayLists and LinkedLists. Recall that adding and removing from the front of a LinkedList are O(1) operations, but O(N) operations for ArrayLists. Modify your code so that instead of get operations, it measures pairs of operations, a remove (from index 0) followed by an add (at index 0). As before, record the table of timings and comment on whether these timings demonstrate the expected patterns for ArrayLists and LinkedLists.