Project Week 4: Auto Complete


This week you will use a hash table to implement the AutoCompleter interface. In addition, you will preform asymptotic time complexity analysis and benchmark all of your implementations from previous weeks. The assignment this week is focused on summarizing the what you have learned in the previous weeks and drawing conclusions on how the various data structures used in this project behave.


Hash Table Implementation

Implement the AutoCompleter interface using a HashSet. Your class must have one attribute: private final HashSet<String> items that is assigned via a one-argument constructor. Note: the constructor should remove any strings in the table passed to the constructor.

O() Analysis

Create a Word document and provide O() anaylsis for the add(), exactMatch(), and allMatch() methods defined in the AutoCompleter interface for all your implementations. Be sure to clearly explain your reasoning.

Benchmarking Program

Update your benchmarking program that benchmarks the time it takes to complete the add(), exactMatch(), and allMatch() methods defined in the AutoCompleter interface. Generate data and plot the results for all of your implementations of the interface. Place the graphs in your report. In your report, explain how you decided on the number of strings in your auto completer objects. Suggest improvements for how your data gathering process could be improved, if you had more time.

Reflection on Learning

In the final section of your report, address the following:

  1. What questions would you try to answer in order to improve your understanding of this project?
  2. Describe your greatest strength with respect to this course.
  3. Describe an area related to this course where you believe you could improve.
  4. Give an example of a software project you think would be valuable that you believe you could now implement.

Just For Fun

Ambitious students may wish to:


This laboratory assignment, developed by Dr. Chris Taylor.

See your professor's instructions for details on submission guidelines and due dates.