The George Washington University
School of Engineering and Applied Science
Department of Electrical Engineering and Computer Science

CSci 131 -- Data Structures
Project #6

due date: Last Class

We need to get these graded as soon as possible.
Late projects can be accepted at the final exam (subject to the usual 20% late fee),
but none after that time.

This project involves benchmarking several sort algorithms to compare their theoretical big O running time with their actual times as measured on Unix or a personal computer. Then compare the actual running times of the algorithms, for different array sizes, to the theoretical "big O's".

Preliminaries:

(A). Background on CPU timing in a shared computer. As you know, package Ada.Calendar provides "time-of-day" operations, but does not provide operations for finding the CPU time used by a running program. On a time-sharing system, using Ada.Calendar to measure the running time of an algorithm is meaningless, because the CPU is being shared among many users and the Calendar elapsed time really measures the amount of "competition" in the system.

Ada doesn't provide CPU time operations in the standard libraries, but the operating system usually does. In this case, we will use Unix's built-in timing operations by means of a small C program that will be called by an Ada package CPUClock . You don't have to do any C programming to use this, but you should become reasonably familiar with how it all fits together even if you don't understand the C code.

(B). Getting ready to do CPU timing on Unix.

The package spec is Program 3.17; a body suitable for a single-user PC version is Program 3.18, and a test program is Program 3.19.

1. Compile and test these as usual. On a single-user computer, this would suffice, but on a shared computer the timings are meaningless. So we need a different implementation of the timing package. This is in cpuclock.adb.

2. Compile cpuclock.adb as usual.

3. next compile the C function unixtime.c that gets the Unix CPU time: type

gcc -c unixtime.c

This compilation will produce, in your directory, an object file unixtime.o

4. now re-link testclok, informing the linker that unixtime.o is to be linked in.

glink testclok.ali unixtime.o

Chapter 14 provides a set of generic sort procedures, all available in the programs131 directory. In this project we will use bubble, shell, quick, and heap sorts. Compile these.

The Sort Project:

Each of the four sorts is to be run on arrays of size 2^K where K runs from 4 (i.e. array size 16) to 10 (i.e. array size 1024). Three arrays of integers will be used: one in upward-sorted order, one in downward-sorted order, and one in random order. You should generate a random 1024-element array using the random-number package, leave it available in your program, then copy "slices" of this array to use in your sort procedures. For the sorted arrays, use the subscripts themselves as values, i.e. if the array has N elements, use A(i)=i for the upward sorted case and A(i)=N-(i-i) for the downward sorted case.

How you organize your driver program to do all the sorting runs is up to you; note that there will be a total of 84 sorts performed: 7 sizes x 3 array orderings x 4 sort procedures. To save on machine overhead, try to combine a number of sort runs into a single run of your program (perhaps all 21 runs of a given sort procedure, for example).

IMPORTANT:

The Unix system shared with many other users. This project will use a lot of CPU time, so you should be certain everything you are doing has been thoroughly tested on small arrays before you run it with large arrays. Try not to waste "long" runs!

Extra Credit:

• up to 3 additional points for doing some good experiments with the two versions of CPUClock to show that CPU time and elapsed time differ on a timesharing machine.

Documentation:

In this project, you are not building a "deliverable," but rather doing an experiment. The coding for the project is very easy. A large part of the project is the way in which the results are presented. Present your results in tabular form (the table does not have to be produced by your program) and as a set of appropriately designed graphs. In your report, discuss the meaning of your results. Do they agree with the theory?