Part 1: Theoretical Analysis

Suppose you are given a list of clock times and want to determine if all of the clock times are within 30 minutes of each other. For example, the clock times in [12:50am, 12:45am, 1:15pm] are within 30 minutes of each other, but the clock times in [12:50am, 12:45am 1:15pm, 1:30pm] are not. Assume you can calculate the difference between two clock times in constant time. Below are three different algorithms that attempt to determine whether all of the clock times in a list are within 30 minutes of each other.

For each algorithm, answer the following questions:

• Does the algorithm correctly determine whether all clock times are within 30 minutes of each other? If so, explain why. If not, give an example where the algorithm would return the incorrect answer.
• What is the worst case Big-Oh complexity for the algorithm, assuming N is the size of the list? Justify your answer.
• Do the best and worst case Big-Oh complexities differ for the algorithm? That is, will the algorithm require fewer steps for some lists of size N (depending on the values in the list)? Justify your answer.

ALGORITHM A:

1. Compare the first clock time in the list with every clock time later in the list.
   1. If the difference is ever > 30 minutes, then return FALSE.
2. Repeat step 1 for each clock time in succession (i.e., the 2nd, 3rd, ...), ,
   comparing each with all clock times that appear later in the list.
3. If no comparison finds clock times differing by > 30 minutes, return TRUE.

* * * * *

ALGORITHM B:

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

* * * * *

ALGORITHM C:

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

Part 2: Experimental Analysis

For the second part of this assignment, you will develop and use a program to experimentally measure the performance of various sorting algorithms. You are given the following three files:

Sorts.java

This class contains static methods (insertionSort, selectionSort, mergeSort and quickSort) for sorting an ArrayList of comparable items.

StopWatch.java

This class provides a simple (and simplistic) way of measuring execution time. Note that the elapsed time reported by this class is clock time, which is affected by many factors other than code execution (e.g., background jobs, garbage collection). To try to minimize these factors when using a StopWatch, you will want to limit background jobs and also perform multiple timings to identify and disregard outliers.

SortGUI.java

This driver class controls a GUI in which the user can select among the different sorting algorithms and specify the size of the list to be sorted. At the click of a button, a sort is conducted and the elapsed time is displayed.

You are to complete the project by implementing a class named SortTimer. This class should contain a single static method named time, that has two parameters: a String specifying the algorithm to be timed (either "insertionSort", "selectionSort", "mergeSort" or "quickSort") and an integer specifying the size of the list to be sorted. This method should create a randomized list of the specified size and return the time it takes to perform the sort (as determined by a StopWatch). Hint: to construct a randomized list of size N (without duplicates), first place the numbers 1 through N in the list, and then use Collections.shuffle to randomize it.

Once you have completed your class, conduct experiments to answer the following questions.

• Insertion sort and selection sort are both O(N²) algorithms. Does one tend to be faster, in absolute terms, than the other? Is it always faster, or do their relative speeds vary with list sizes? Justify your answers by providing timings for both algorithms on different list sizes.
  
  
• Theory suggests that doubling the size of the list should roughly quadruple the time for insertion sort and selection sort (once the lists are big enough). Sort lists of increasing sizes and report your timings using these two algorithms. Do your timings produce the quadrupling effect? Justify your answers.
  
  
• Quick sort and merge sort are both O(N log N) algorithms. Does one tend to be faster, in absolute terms, than the other? Is it always faster, or do their relative speeds vary with list sizes? Justify your answers by providing timings for both algorithms on different list sizes.
  
  
• Are the times for quick sort and merge sort significantly faster than the corresponding times for insertion sort and quick sort? Are they always faster, or is there a size threshold at which they become faster? Are the relative time differences fairly consistent regardless of list size or do they increase signficantly as the size of the list increases? Justify your answers.
  
  
• Theory suggests that doubling the size of the list should more than double the time for quick and merge sorts (once the lists are big enough). Sort lists of increasing sizes and report your timings using these two algorithms. Do your timings produce the more-than-doubling effect? Justify your answers.