CS127 Assignment: Timing

Due Wednesday, 1/24/01. Submit your analysis, pictures, and code on paper.

The basic idea

For this assignment, you'll collect and discuss timing data for a few standard algorithms. Simply put, your goal is to argue from empirical evidence that, for example, Insertion Sort's average running time is approximately proportional to N^2, Merge Sort's is approximately proportional to N*log_2(N), etc. You should make these arguments by collecting timing data, displaying it graphically along with graphs of functions such as A*N^2 and B*N*log_2(N) with suitably chosen A's and B's, and discussing the results.

To time a program, you can use the UNIX command "time". For example, here's what happened when I compiled and ran sorts.cpp: 


	atanasoff> time sorts
	11.500u 0.010s 0:11.50 100.0%   0+0k 0+0io 120pf+0w

The 11.500u tells you that your program used 11.5 seconds of "user time," which is the time during which your own code was running. "System time" is the time during which system code resulting from input/output statements, etc. The third field, the 0:11.50 is the actual time by the clock on the wall between the time you launched the program and the time it stopped running. This is often significantly different from the user time, since other programs are running on the computer, too. For this assignment, you should report user times.

There are many software packages with which you can graph data and functions (e.g. Mathematica, SPSS, Excel, AppleWorks,...). If you need help producing graphs for this assignment, feel free to talk to me.

The specifics

  1. Comment out the InsertionSort() call in main() in sorts.cpp. For the N's you use in the later parts of this assignment, find out how long the program infrastructure (notably the Shuffle() routine) takes to run. You may wish to subtract these times from your timings of the sorting routines.

  2. Using the InsertionSort function in sorts.cpp, argue that Insertion Sort's average running time is approximately proportional to N^2.

  3. Use InsertionSort again, but now determine its (empirical) time complexity if the initial array is already sorted. Explain your observations.

  4. Compare Selection Sort to Insertion Sort in both the random-data and pre-sorted contexts.

  5. Using the MergeSort function in sorts.cpp, argue that Merge Sort's average running time is approximately proportional to N*log_2(N).

  6. Suppose you want to search 1000 times for a number that's not in your N-item array (I know that you're unlikely to search for the same item over and over, but by doing so, you are more or less simulating the worst-case search scenario). You can use linear search all 1000 times, or you can first sort the array and then use binary search. How big does N have to get before binary search is worth the effort.

  7. Which of your claims in the items above depend on the particular computer system you're using, and in which claims are computer-independent?

Have fun, start early, and keep in touch.


Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057, (507) 646-4364, jondich@carleton.edu