Part One

This program obtains timing information on a particular sequence of inserts and deletes into a linked list, a TreeSet, and a hash table respectively. It uses corresponding classes in Java's API. Run the program a few times, and report the times for a run that you consider typical. Based on what we have learnt about linked lists, binary search trees, and hash tables, comment and try to explain the observed running times.

Part Two

Suppose that we have a large collection of words in the English language, represented as strings. (Maybe these are obtained by reading in one or more text files.) Now suppose that we wish to quickly answer a query that asks if a given word is in our collection. Maybe the query involves the string "measure" -- we want to say whether this is in our collection or not. This is easy to do if we use a hash table to store our collection.

Let us assume that we want to answer the queries in a more robust way: If the user queries "maesure" or say "mesure", we still want to output a hopefully small list of words in our collection that includes "measure" (assuming "measure" is in our collection). That is, if the user queries with a string that is close to one of the words in our collection, we should output a small set of words from our collection that includes the right word. Our goal is to develop a reasonable solution to this problem based on variants of hash table ideas.

One thing we can assume is the ability to manipulate any string by omitting or swapping characters from it. We'll talk about the details of this later.

In this homework, you are not required to develop any code for this problem. Rather, you should think about the problem and outline a possible line of attack. Questions that you should address include: In what way can hashing or variants help in solving this problem? Do you want to use the library class java.util.Hashtable, or build a hash table like data structure yourself, possibly modifying the textbook code?

The next homework will require us to actually develop a program for this problem. This program does not have to correspond to the outline you give in this homework.

For both parts of this homework, please submit files into the folder Homework6.