HOMEWORK 9: SPELL CORRECTING HASH TABLE


NAME:  < insert name >


COLLABORATORS AND OTHER RESOURCES:
List the names of everyone you talked to about this assignment
(classmates, TAs, ALAC tutors, upperclassmen, students/instructor via
the forum, etc.), and all of the resources (books, online reference
material, etc.) you consulted in completing this assignment.
This should not be "none"!

< insert collaborators / resources >

Remember: Your implementation for this assignment must be done on your
own, as described in "Academic Integrity for Homework" handout.



ESTIMATE OF # OF HOURS SPENT ON THIS ASSIGNMENT:  < insert # hours >



MOST COMMON PREFIXES & SUFFIXES:
"inter" is the most common 5 letter prefix in the
words_with_frequency_10k.txt dataset.  Is this the most common 5
letter prefix for all of the provided dictionary datasets?  What are
the most common prefixes for other prefix lengths?  What about
suffixes?  What about a combination of prefix AND suffix?



HASH TABLE CONFIGURATION:
What are the relationships between the dictionary size, hash table
size, hash function, and collision strategy on the time to create the
hash table and the total memory used by the hash table?  What about
the running time for the applications of spell checking and spelling
correction?  Write down your hypotheses before testing.  Organize and
present your data below.  Discuss what conclusions you can
draw from this testing, and whether your hypotheses are confirmed or
contradicted.



QUALITY OF SPELL CHECKING & SUGGESTED REPLACEMENTS:
Comment on the quality of the spell checking and the output of the
algorithm to suggest replacements.  What worked well, what needs
improvement?  Paste examples below.  Do you have specific ideas
for how the dictionary data, algorithm, or program could be improved?



EXTRA CREDIT - OPEN ADDRESSING W/ QUADRATIC PROBING:
Discuss your implementation.  Collect data to compare this technique
to Separate Chaining and Open Addressing w/ Linear Probing.



MISC. COMMENTS TO GRADER:  
(optional, please be concise!)