Data Structures and Algorithms

Workshop 1

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 random integers into the collection.
      You will need to determine n by experimentation: it will need to be large enough so that the run times measured in the next section are each several seconds. A value of 105 would probably be a good start!
      Use the random number generator, rand(), to generate random integers.
      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
      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.
    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