Lab 14: 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
Write the HashTable class that implements the AutoCompleter interface
using a HashSet. Your class must have one attribute: private final HashSet<String> items.
Note: getBackingClass() should return java.util.HashSet.
Your implementation should provide the best \( O() \) performance you can.
Testing
Update your JUnit test class for the AutoCompleter interface from lab 8 to
test your HashTable implementation of the AutoCompleter interface.
O() Analysis
Create a PDF document and provide \( O() \) analysis for
the add(), 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. 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
Add a 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
Write a benchmarking program that 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.
Your benchmarking program is not the focus of this lab. You can hardcode it to generate just the data points that you need.
Reflection on Learning
In the final section of your report, address the following:
- What questions would you try to answer in order to improve your understanding of this project?
- Describe your greatest strength with respect to this course.
- Describe an area related to this course where you believe you could improve.
- 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.
Acknowledgement
This laboratory assignment, developed by Dr. Chris Taylor.