CMSC 435 Algorithm Analysis & Design

Homework # 3

Due Thursday, October 22

This homework assignment will be collected, and it will count as 3 quizzes in your grade.  Each class period it is late, it will drop in value by one quiz.

You are to submit source code, results, and comments/observations (in an organized presentation) for problems 4 and 5; and your data, calculations, and observations (again organized in a manner to make your presentation) for problem # 1.  You will present both your design and your source code for problem # 3, and your conclusions and justifications for problem # 2.

All submissions must be in a folder to be accepted.

1.      Complete the Sorttest Lab found on this web site.  When you have completed entering the data into the tables provided on the instruction sheet you may do one of two things to determine the behavior of the number of compares in the sorting algorithm as a function of the sample size n:  (a)  Plot the log (any base) of the number of compares versus the log of the sample size n.  If a straight line can reasonably be fitted to these points, then the number of compares as a function of n is given by the formula  f(n) = n^p where p is determined by the slope of the line.  (You will expect that some of these algorithms will exhibit f(n) = Q(n²) behavior.)   If these points do not fit a straight line, then f(n) is not given by a power function, and an alternative approach must be used to determine the behavior of the algorithm.  (b) Compare the ratios of the successive values of the number of compares to the ratios of the successive sample sizes and determine the functional dependence of the two.  For instance, if our table of values contained an entry such as the one shown below:

Sample Sizes

            Then you your comparisons would include:

            996/69 = 14.4                         <-->     64/16 = 4

            16,328/996 = 16.4                   <-->     256/64 = 4

            269,176/16,328 = 16.4            <-->     1024/256 = 4

            1,045,946/269,176 = 3.9         <-->     2048/1024 = 2

and you would conclude that the ratios of the comparisons is roughly the square of the ratios of the sample sizes (give more weight to the values obtained for the larger sample sizes).  and your experimental evidence would indicate that X-sort is a Q(n²) algorithm.  If the ratios of the comparison counts are not approximately the square of the ratios of the sample sizes, try fitting them to n lg(n) of the ratios of the sample sizes.

List all of the observations that you can make from the data collected in this laboratory exercise.

2.      Banks often record transactions on an account in order of the times of the transactions, but most people like to receive their bank statements with the checks listed in the order by check number.  People usually write checks in numerical order and merchants usually cash them with reasonable dispatch.  Which sorting procedure would you use to convert time of transaction ordered checks to check number ordering.  Explain your reasoning and cite evidence from the above laboratory exercise to back up your assertions.

3.      Use the design methodology illustrated in the lecture on Quicksort (and previously used to develop the algorithm for selection sort in the big-O lecture) to write the java code for insertion sort.

4.      Use the Quicksort algorithm given in the lecture notes, and the Counter class referenced on the web site to develop a program to conduct the following  experiment:  Repeatedly fill an array of size 4096 with randomly generated integers and record the count of the number of compares needed to sort the list each time.  Run this test inside of a loop 50 times, and when finished, record the average number of compares, the best value, the worst value, and the standard deviation.  You will have to increment a counter every time you make a comparison inside the partition function.  The standard deviation is given by the following formula:

s= Standard deviation

m= mean

         _{n                                         n}

s = (å (x_i - m)²/n))^1/2  =  ((åx_i²)/n - m²)^1/2

        ^{i=1                              i=1}

5.      Modify your sorting algorithm in the previous problem to stop partitioning the list in Quicksort when the size of the (sub)list is less than or equal to 12 and sort the remaining sublist using insertionSort.  Your counter will now have to count compares in both the partition function and in each iteration of insertionSort.  Again, run the experiment for 50 iterations and record the same set of statistics.  Compare your results for the two different sorting techniques and comment upon your results.