CS 331 Design and Analysis of Algorithms



CS 331-01 Design and Analysis of Algorithms

Project #1

Implement the following algorithms:

a. Insertion Sort

b. Mergesort

c. Quicksort1 (Regular Quicksort)

d. Quicksort2 (Quicksort / Insertion Sort Combo)

e. Quicksort3 (Randomized Quicksort)

The first three algorithms have been given in class. The only difference between Quicksort1 and Quicksort2 is that when n ( 16, Quicksort2 will not partition the list but call Insertion Sort. Note that Insertion Sort is fast when the problem size is small because it has low overhead.

A possible input on which Quicksort displays worst-case behavior is one in which the elements are already in sorted order. In this case the pivot creates an empty partition and the rest of the elements will fall in the other part. The performance of any divide-and-conquer algorithm will be good if the resultant sub-problems are as evenly sized as possible. Can Quicksort be modified so that it performs well on every input? The answer is yes. A simple solution is the use of a randomizer. While sorting the array a[p..q], instead of picking the first element, pick a random element (from among a[p],…,a[q]) as the partition element. Each call to the randomizer Random() takes a certain amount of time. If there are only a very few elements to sort, the time taken by the randomizer may be comparable to the rest of the computation. For this reason, we invoke the randomizer only if (q-p+1)≥16. Now, write algorithm Quicksort3 to include the following line before the call to Partition.

if ((q-p+1)≥16) then

swap a[p] and a[p + Random() mod (q-p+1)];

Carry out a complete test of your algorithms with n = 2, 4, 8, 16, 32, 64, 128, 256, ... up to 216. In order to obtain more accurate results, for each different value of n, the algorithms should be tested with the same unsorted array many times. The total time spent is then divided by the number of times the algorithm is performed to obtain average time taken to solve the given instance. Note that given the high speed of modern computers, the running time may fail to register at all and be reported as zero for small instances. To overcome this obstacle, you need to run the program in an extra loop many times, measure the total running time, and then divide it by the number of the loop’s repetitions.

Explain how you verify the correctness of your implementation of the five algorithms. Write a detailed report together with tables and graphs explaining the data sets, test strategies and evaluation of the results. What computer system do you use for testing? When did you run the program and collect data if it’s in a multi-user environment? Did you try both random inputs and sorted arrays? Does Quicksort3 significantly improve the performance of Quicksort1 on sorted arrays? What does your program show about the average execution time of the five algorithms for different sizes of input? Is Quicksort2/Quicksort3 always faster than Quicksort1? What is the relation between the average computing times of Quicksort2 and Quicksort3? What are the theoretical complexity comparisons of the five algorithms in worst-case and best-case? Does your experimental result match with the theoretical analysis of the algorithms? If not, what are the possible reasons? Also find out when (the value of n) does Quicksort2/Quicksort3 become faster than the other three methods. Conclude your report with the strength and constraints of your work.

Please zip your submission including your source code, output of executions, and a typed report. Name your zip file as username_p1.zip and send it to ftang@cpp.edu. Output of executions should include the average execution time for different sizes of input from all five implementations. For verification purpose, you shall also print the original arrays and the corresponding sorted arrays for n up to 32, but the cost of printing should not be included for comparing the performance of different algorithms. They will just be included for verification purposes.

This project will be graded based on the correctness and efficiency of your implementation of the five algorithms (60%) and the quality of your report (40%).

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download