Lab 15: Even More Auto Complete

Overview

This week you will use a hash table to implement the AutoCompleter interface. In addition, you will perform 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.

Video introduction for the lab

Details

Hash Table Implementation

The HashTable class will implement the AutoCompleter interface using a HashSet. It will have one attribute: private final HashSet<String> items. Note: getBackingClass() should return java.util.HashSet.

O() Analysis

Create a PDF document and provide O() analysis for the exactMatch() and allMatches() methods defined in the AutoCompleter interface for all your implementations. Your analysis should include separate results for the Unordered and Ordered Lists backed by both an ArrayList and a LinkedList as well as your Binary Search Tree and Trie implementations. In your analysis, use n to represent the number of elements in the AutoCompleter and m to represent the number of elements in the array returned by allMatches(). Be sure to clearly explain your reasoning.

AutoCompleter interface

There is a new static method, getString(int length), that returns a String with length randomly selected lowercase letters in it. This method will be used to generate word lists to be used in your benchmarking activities.

Benchmarking Program

The Benchmarker program collects data to characterize the performance of add(), exactMatch(), and allMatches() methods defined in the AutoCompleter interface as a function of input size. Generate data and plot the results for your LinkedList backed OrderedList, Trie, and Hash Table implementations. Be sure to collect enough data so that your graphs clearly show the growth rate of each algorithm. 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:

• Benchmark the allNonPrefixMatches(String substring) method that was added to the interface.
• Implement the Trie using an array as the backing structure, setting the length to 26 and using the indexes as "hash" values for each character.

Acknowledgement

This laboratory assignment, developed by Dr. Chris Taylor.