Early submission will earn you 10 points bonus on top of 100 points. On-Time submission earns you up to 100 points. Note the bonus is not extra credit because the points may affect the final curve.
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.
Always write the time-complexity (in Big Oh notation) in a comment next to every method or function you write in this class. E.g.,
class Foo
{
public:
void insert(int N) // O(N lg N)
{
}
}
For a program timer class, see src/PCTimer.h for Win32-family OS and see src/Timer.h for Unix-family OS.
For test input use the file src/words.txt, which contains 45,000 words from the Unix dictionary.
(30 points) Write class ArrayList as presented in lecture.
(30 points) Write class LinkedList as presented in lecture.
(40 points) Write a driver program that allows the user to test two implementations of the unordered list data structures: ArrayList and LinkedList. Your driver should use the provided 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 find all every word from the test input file.
the total time needed to remove all words given in the test input file.
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.