Description
The focus of this lab will be on doing experimental timing of algorithms.
- Mehrdad will explain to you how to do timing tests and how to seed a random number generator so you can produce and reproduce data sets. Then, do the following:
- Implement the insertion sort algorithm. The algorithm discussed in class is given in pseudocode below. Use -100,000 as the value in A[0].
insert_sort (A : data; n : integer)
// Assume first element of the list is in A[1] and that
// A[0] is a sentinel, a value smaller than all list elements
for i ¬ 2 to n do
j ¬ i; tmp ¬ A[i]
while (tmp < A[j-1]) do
A[j] ¬ A[j-1]
j ¬ j – 1
A[j] ¬ tmp
- Timing tests—part 1
Generate ten (different) data sets each of size 200,000 containing integers in the range from -40,000 to 40,000. (There will be duplicates but that’s OK.) The random number generator should be seeded only once, before generating the first data set. After generating the first data set, start the clock, run your insertion sort program, stop the clock and record the time used to sort the data.
Then, (in the same run of your program) generate the next data set, and repeat the timing process until a total of 10 tests have been run. When your program finishes you should have ten time values. The code for testing your program as well as the times taken for each data set must be part of your submission for the lab. Include all timing test results in your lab submission.
If you seed the generator incorrectly, and repeatedly generate the same data set you will lose significant credit.
- Timing tests—part 2
In order to see how your implementation differs in efficiency from others in your lab, do the following five tests and also include these results in your lab submission. Next week you can compare your results with those of the others in the lab. Be sure to clearly label the part 1 and part 2 results.
Using the seed value indicated below for your lab, in the manner described above, generate five (different) data sets each of size 400,000 containing integers in the range from -80,000 to 80,000. Again, record the amount of time needed for each of the test cases (i.e. you should have five time values). Include all timing test results for this part in your lab submission and also the average time taken by your program.
Seed values: Monday 10, Tuesday 15, Thursday 20
The lab submissions are due by midnight Tuesday for the Monday lab, midnight Wednesday for the Tuesday lab, and midnight Friday for the Thursday lab. NOTE: It is important that the timing tests be done on the machines in the lab so that the part 2 results for the students in your lab can be compared.
Here’s an example of what your data should look like:
n = 400000
7.231 seconds
7.158 seconds
7.281 seconds
7.189 seconds
7.465 seconds
(The numbers above are not the result of actual timing tests so your results won’t be in this range.)
