EECS 215 Homework 3 Due Thursday Week 5 or 6

• Always write the time-complexity (in Big Oh notation) in a comment next to every method or function you write in this class.
• (40 points) Remember in Homework 2, you wrote programs to solve your choice of two of the 6 problems using Dynamic Programming. Solve each of the remaining four problems from homework 2 using Dynamic Programming, but this time just come up with the recurrance and describe how you would compute the optimal solution using dynamic programming - you need not implement them. Please type your solutions to these four problems and include them with your program and output below when you submit your homework via email.
• (40 points) Write class ChainedHashTable as presented in lecture.
• (20 points) Use a driver program, perhaps from your solution to homework 1, that allows the user to test your class implementation. 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 find every word from the test input file.
  • Test your program on random.txt and on words.txt and note the difference in speed. Both these files can be found in 215/src directory.
• What to submit:
  • Email me your source code and either an execution script, a screen shot, or output file that shows your program works as described above. Please use "zip" and not "rar" to combine it all together if you decide to wrap it all into one file.