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.