• Understand and apply complex data structures and algorithms.
• Use appropriate algorithms (and associated data structures) to solve complex problems.
• Have a thorough understanding of the Standard Template Library.
• Be able to analyze the complexity of algorithms (both sequential and recursive).
• Be able to use data structures in software design and implementation.
• Be able to apply the STL in software design.

An abstract base class, Dictionary and a driver program have been provided for you. Use inheritance to create derived classes based on the criteria given below.

This implementation should make use of a set to store the words from the dictionary file.

This implementation should make use of a cs285::vector to store the words from the dictionary file. Your search algorithm should make no assumptions about the order in which the words are stored in the dictionary.

This implementation should make use of a cs285::vector to store the words from the dictionary file. You should assume that the words are in order and implement a binary search algorithm for finding words in the dictionary.

This implementation should make use of a cs285::HashTable to store the words from the dictionary file. You will need to implement the cs285::HashTable (you may make use of the code given in the course handout).

The main function will need to be modified to handle all four of your implementations. A sample dictionary file is available here.

You should submit an activity log to indicate your activity and progress on this assignment during the first two weeks of the assignment. Please submit one log per team.

Here is a template file to use as a starting point for this report.

Your report should include:

• Narrative including:
  • Asymptotic time complexity analysis for each of the dictionary implementations. (Don't just give answers, explain your reasoning.) You should do analysis for the following:
    • Dictionary loading times for a dictionary with N words in it.
    • Spell check (after the dictionary is loaded) for a file with K words in it.
  • What issues (capitalization, punctuation, etc) that you chose to address and how. Also indicate any issues you identified but chose not to address.
  • How did you select your hash function. What things did you try.
  • Reactions to the project.
• Sample results: no sample results are required. You will be required to use your classes in week 10 lab to perform benchmarking measurements.
• A summary of your activity log indicating how much time you spent on the assignment (following the template provided in the lab5.xml template document). Please use the following categories:
  • Design
  • Coding
  • Debug (before you think it's working)
  • Test (after you think it's working)
  • Documentation
  • Other
Note: You should be working together the entire time on this project so your table should mainly contain "both" entries. If you both spent one hour debugging your code together, your activity log should indicate one hour (not two hours) was spent debugging.
• The Documented source code for your program.

As with any report you submit, correct spelling and grammar are required. In addition, your report should be submitted electronically following the Electronic submission guidelines. (You may wish to consult the XML help video and/or sample report before submitting your report.) Be sure to keep copies of all your files, in case something gets lost.

If you have any questions, consult your instructor.

This assignment was originally developed by Dr. Chris Taylor.

© 2001-2006 Dr. Christopher C. Taylor

Office: CC-36C

Phone: 277-7339