Data Structures and Algorithms

Workshop 1 - 1997

Familiarisation

1. Download and save into your directory from the download window:
   1. collection.h
   2. collection.c and
   3. the test program testcol.c.

2. Compile into an executable:
   gcc -o testcol testcol.c collection.c

   Note that you will need to use an ANSI C compiler as the programs are written in ANSI C. On some Unix machines, cc only accepts the older "K&R C".

3. Run the program and verify that it runs as expected. Examine the test program listing to determine how it runs!

4. Now we want to find out how efficiently it runs:
   1. Modify the test program so that it inserts a large number, n, of integers into the collection.

      You will need to determine n by experimentation: it will need to be large enough so that each run measured in the next section takes several seconds. A value of 10⁵ would probably be a good start!

      Make a small function to generate a set of unique integers - the numbers from 1 to n will do fine for this exercise.

      By timing a run for suitably large n, determine the average time to insert an integer into the collection. You will need to use the Unix functions
      

      • ftime for the Suns
        
      • clock for the SG machines
        
      to time your programs. Note that the two functions have a different idea of how to tell you about the time. Read the manual page carefully!

      You will need to time quite a few runs for this course, so spend a little time to design a simple, efficient timing routine!

   2. Determine the average time to search the collection for a randomly generated integer - again by finding the time to search for n randomly generated integers. Use the random number generator, rand(), to generate random integers.

   3. Modify the program so that it prints out the insertion and searching times for a range of values of n. Suitable values will produce run times between about1 and 20 seconds. About 10 values should enable you to determine the characteristics of the time vs n curve.

5. Now download a linked list version of the same program collection_ll.c and use the same program to print out the time vs n values for this implementation. (You may need to change the range of the values of n!)

Submission Instructions