Benchmarking Algorithms Summary: In this homework, you will be implementing code to generate test data and benchmark sorting. As we have seen with...
I need help with this assignment! It's about benchmarking algorithm.
Benchmarking Algorithms Summary: In this homework, you will be implementing code to generate test data and benchmark sorting. 1 Background In this assignment you will practice predicting and verifying the impact of data "nature" on the run—timeof sorting algorithms. As we have seen with algorithms like insertion sort, the runtime (even worse case likeBig-Oh) can be impacted by the nature of the input. To do this, we will create three different types of input data, that may give different results when sorted.Two sorting algorithms will then be benchmarked on these three types of data. Each algorithm will berun twice, for different dataset sizes, in order to get times that we can use to apply the doubling formula. (See slide 23 (Modeling Small Datasets) in the Analysis of Algorithms slide deck for details on the doubling formula.) The doubling formula is lg% = b. If we compute the formula, then we will be able to figure out the algorithm’s Big-Oh for a particular type of input data, since they will be 0(nb). b is simply thepower. This document is separated into four sections: Background, Requirements, Testing, and Submission.You have almost finished reading the Background section already. In Requirements, we will discuss what isexpected of you in this homework. In Testing, we suggest some basic tests you use to start to verify yourimplementation. Lastly, Submission discusses how your source code should be submitted on BlackBoard. 2 Requirements [35 points] For this assignment you will be writing code to generate test data, as well as benchmark sorting algorithmson it (edited from Sedgewick and Wayne: 2.1.36). First, write a series of methods that generate test datathat is “non-uniform” : 0 Half the data is Us, half Is. [5 points]0 Half the data is Os, half the remainder is Is, half the reminder is 2s, and so forth. [5 points]0 Half the data is US, half random int values (can use nextInt() from J ava’s Random package) . [5 points] 0 Each of these three techniques should be implemented as a static method that takes a integer repre-senting the size of a dataset, and returns an integer array containing that number of elements generatedwith the corresponding rule. Randomize (shuffle) the contents of the array after you populate it. Using the three methods you implement, develop and test hypotheses about the effect of input on theperformance of two of the algorithms (your choice) we have covered. (Get their source code from BlackBoard.) o The program should contain your hypotheses (3 per algorithm) as comments: describe what you thinkthe running time will look like (0(a)? 0(112)? 0013)?) on each data set, and explain briefly why youthink that. As long as your ideas make sense, you will receive full credit on the hypotheses. [8 points] 0 For each of the two sorting algorithms, you should run them on the three types of test data. Test themwith datasets size of 2048 and 4096. Time each of these twelve tests with the Stopwatch class givenin class. (If your system is so fast you don’t get good results, you may increase the dataset size.) [6points] 0 Display the result of applying the doubling formula to the run times from the 2048 and 4096 test pairsto get the power (“b”) for that algorithm on that type of input. [6 points]
Show more
