Intermediate Programming 601.220

   Project 1
   ---------

1. Design and develop a linked list based repository that maintains a
   dynamic list of records in the order they were inserted. A record
   consists of a unique key and associated (potentially non-unique)
   data. For this project, keys and data are both integers.
   The repository should support the following operations:

   Insert - insert a {key, data} record into the repository. Each
            key should only appear at most once in the
            repository. If the key already appears in the
            repository, this operation should not change the list
            at all. The operation should return 1 if the key was
            inserted, 0 if the key was not inserted, and -1 if
            the operation had a problem completing correctly.

   Delete - remove a record with a specific key from the
            repository if such a record exists. The operation
            should return 1 if a record was removed or 0 if the 
            key was not found in the repository. 
 
   Get    - get a record with a specific key from the repository
            if such a record exists. The operation should return
            the data associated with the key if the key was found
            in the repository or 0 if the key was not found.

   Print  - print the current size of the repository, the number
            of 'next' steps performed so far (see below), and the
            current {key, data} records in it.

   A counter should maintain the number of steps performed on the
   list. The counter should be initialized to 0 and should be
   incremented each time a pointer is set to point to another member
   of the list. This gives an indication of how much effort was spent
   so far.

   Write a program that will use the repository with random operations
   generated by the "Get_next_op" function provided in class as part of
   the Project1_template.c file. The "Get_next_op" function randomly 
   generates the type of operation to perform, as well as key and data 
   values to use as needed for the operation.
   Note that you should NOT need to recompile your program between tests.

   Please use seed 20 unless otherwise specified.

1.a  Run it with numbers between 1..10, for 1000 operations, 
     printing every 100 operations. 
1.b  Run it with numbers between 1..100, for 10,000 operations, 
     printing every 1000 operations.
1.c  Run it with numbers between 1..100, for 1,000,000 operations, 
     printing every 100,000 operations.
1.d  Run it with numbers between 1..1000, for 10,000,000 operations, 
     printing every 1,000,000 operations. Avoid printing the actual
     numbers in this case (just the size and number of steps).

2. Design and develop a similar repository with the modification that
   the list is maintained sorted (smaller keys first). Re-run 1.a,
   1.b, 1.c, 1.d for this case as well.

3. Re-run 1.d and 2.d with 5 different seeds: 20, 21, 22, 23, and 24.
   Include in your document the number of steps in each case and
   calculate the average number of steps for the original repository
   and for the sorted repository. Please comment on the results and
   explain them if possible.

Please complete your design by Monday Sep 14 and development by
Wednesday Sep 16 (this will not be delivered or graded).

Submission date of complete project (including original documented
code, design, and results) is: Friday, September 18, 12pm (noon). 

Submission is accomplished by e-mailing a tar file that contains the
source code and the design-and-results document (not executables or object 
files) to amir220@cs.jhu.edu. Note that amir220@cs.jhu.edu is
*not* the cs220-help@dsn.jhu.edu e-mail that can be used to get help.
The design-and-results document should either be a plain text or pdf file.

You can submit as many times as you want. The last submission before
the deadline will be checked. We encourage submitting an early draft
to make sure you know how to submit.