|
|
|
|
CS 223 In-lab 2 For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments. These will be due at the end of the lab period. You may occasionally be assigned homework problems as well. Homework will always be due at the beginning of the next lab. Homework
Programming Assignment Download the non-randomized selection algorithm based on quicksort that we developed in class. Determine what would be a bad (worst-case time) input for this selection method. The programming assignment is to test how long this selection algorithm takes on these bad arrays. Your program should create instances of these bad areas for n = 10, 100, 1000, 10000. Time how long it takes for each these test cases (use a stop watch, or the built time functions in Java). Then try the same test cases using the randomized version of the quicksort selection algorithm. What do you conclude? Print out your source code and test run data and conclusions. Turn this into your TA. The homework is due the following lab. |