CS14, Program 4

Assigned: November 15^th, 2001

Due: November 26^th, 2001, 10pm

Comparing List implementations

In programs  2  and 3 you wrote two different implementations of a list.  In this program you will be comparing the performance of programs that use these implementations.  Since the methods in both implementations were the same, you can write one program and compile it with either implementation.

There are two short programs to write for this assignment.  Each one should be compiled twice, once with the array implementation of the list, and once with the linked list implementation.  You will then run the programs with input from different size data files and compare their running times.  Timing program runs was discussed in lab.    

The programs

1) Write a program that reads in characters from a text file into a list.  Then go through the list and double every character.  For example, if the original text was "abcde", the list after doubling should contain "aabbccddee".  The core of the program should be something like

   L.first();
   while (!L.isDone())
   {
      L.insertAfter(L.current());
      L.next();
   }

2) Write a program that reads in characters from a text file into a list.  Then go through the list and delete every occurence of a letter (user specified).


To Do

• Write the two programs described above
• Compile each program with each list class implementation
• Run the programs with input files of varying lengths.  Sample files can be found in ~deganit/cs14/data.  Or copy them from here.
• For each file, run the second program three times: once removing the letter 'e, once removing the letter 'r', and once removing the letter 'x'.
  
• Time each run.  
• For each program, create a table with three columns: input size, run time with array, run time with linked list.
• Summarize your results in a file called README, which you should turn in with your program
  

What to turn in

- stutter.cc, delletter.cc

- README file that gives the results of timing your programs (four tables).