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
- 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.
- Using the InsertionSort function in
sorts.cpp, argue that
Insertion Sort's average running time is approximately proportional to N^2.
- Use InsertionSort again, but now determine its (empirical)
time complexity if the initial array is already sorted.
Explain your observations.
- Compare Selection Sort to Insertion Sort in both the random-data and
pre-sorted contexts.
- Using the MergeSort function in
sorts.cpp, argue that
Merge Sort's average running time is approximately proportional
to N*log_2(N).
- 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.
- 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