ECE 144 Homework 3 Due Early Week 4, On-Time Week 5 Last modified: 9/25/02

• Always write the time-complexity (in Big Oh notation) in a comment next to every method or function you write in this class.
• Use the test input and timers from homework 1. You may also use *your* solutions from previous homework as starts on these, but only if you really wrote them by yourself.
• Note submitting any program that you did not write yourself is plagiarism - a very serious form of cheating. Anyone caught submitting a homework solution they did not author themselves will be prosecuted to the fullest extend of UCI law. Just as a reminder, please re-read my cheating policy. Cheating policy.
• (30 points) Write class LinkedQueue as presented in lecture using a tail pointer to allow O(1) additions to the end. Note your OrderedList from last week can be easily adapted to this, but the interface is different.
• (30 points) Write class ArrayQueue as presented in lecture with a circular representation.
• (40 points) Write a driver program that allows the user to test your class implementations. Again use the PCTimer class to measure the following times
  • the total time needed to insert all words from the test input file.
  • the total time needed to remove all words from the appropriate Queue. Note this will not make another pass over the file as the other test functions did.
  • This time, be sure your main program takes arguments from the command line for input file name and output file name.
• What to submit:
  • Show your TA that both data structures work as described above.
  • Submit (and save) your times for each data structure. We will build a comparison table for a final project at the end of the course.