Description
In this assignment you are to implement a hash table for use in a simple spell
checker. The spell checker should be set up with a GUI for the interface. The
hash table MUST be built as specified in this document. The GUI can be built with
Java Swing or JavaFX. There is extra credit of 20 points for using JavaFX.
Partial credit will be awarded to non-working projects. The assignment is worth
220 points, allocated as follows:
Correctness and completeness – 2000
Having a minimum reasonable Program Style – 20
Human Engineering of the GUI – 20
There is an automatic deduction of 70 points for any code longer than 10 lines
copied from the Internet.
The project can be done in pairs, and we encourage this. There is no penalty or
extra credit for a pair submission.
Submission
Your project must be created and emailed to both graders
PAGE 2
Naren.Thanguturi@rockets.utoledo.edu
Yamini.Nuvvula@rockets.utoledo.edu
before 1:00 PM on Monday December 11. You must submit a single Zip file. On a
Mac, Zip files can be created using the Compress option on a folder).
1. Name the Zip file using the format Project7_YourName. Example:
Project7_Ledgard
Project7_Ledgard_Smith (If you have partner).
2. The Zip file can only contain .java, .png, or .pdf files.
3. For taking snapshots of the output of code use the Windows snipping tool,
or on a Mac, Control-Shift-4. This creates a .png file. Make sure you take
snapshots for all of the output.
4. You can include the snapshots directly as .png files. Or better, organize
them in a word file and convert the word file to a PDF file.
5. Do NOT send MS word files directly. Convert all .doc or .docx files to .pdf
files
Only one copy should be sent if you have a partner. No need to send a version
from each partner, as BOTH names should be on the project and the zip file.
Late projects may be submitted up to Wednesday December 13 at 1:00, and will
be charged a 60 points penalty, even if one hour late. Later submissions will not
be accepted.
You submission must include
a) Listings of each program you have created
PAGE 2
b) A printout of the results from running your program using the two example test sets given at
the end of this document. The printout should highlight or mark any words that do not
appear in the dictionary.
c) The results of any other document given as input
d) The number of collisions in the hash table and the length of the longest chain
e) A “ReadMe file” explicitly stating any grounds for extra credit.
There should be enough sample runs to demonstrate all required functionality.
Hash Table Class
Implement a hash table to store strings (i.e. objects of the Java String class). The
Hash Table must be implemented as a data type with the class name
“HashTable”. The HashTable class will have the following methods:
HashTable ( ) Constructor for a hash table of default size: 1000
HashTable (int n) – Constructor for a hash table of size n.
void Insert (String S) Inserts S into the hash table.
boolean Contains (String S) Return true if S is in the table, false otherwise
int Count ( ) – Returns the number of strings stored in the table
Hash Function
The insertion of a word requires the computation of an array index
array index = HashValue mod array size
The insert function must thus generate a hash value from a given word w. The
hash value should be calculated by assigning the values 1 to 26 to the letters a to
z (regardless of letter case) and calculating a numerical value based on the
letters in the word as follows:
Group the letters of w in chunks of 4. For each four letters, calculate
ch1 * 313 + ch2 * 312 + ch3 * 311 + ch4 * 310
and add the total value of each chunk to get the hash value. For the actual index
of the word, compute
PAGE 2
HashValue mod array size
For example the string “cat” has the hash value 90,954:
3*313 + 1*312 + 20*311 = 90,344
and the string “table” has the hash value 745,810, calculated as follows
tabl = 20*313 + 1*312 + 2*311 + 12*310 = 596,855
e = 5*313 = 148,955
596,855 + 148,955 = 745,810
For a hash table of size 101, “cat” maps into the index
90,954 mod 101 = 54
and “table” maps into the index
745810 mod 101 = 26.
Note: In Java, there is a built-in hash code function which can be applied to a
string object S
S.hashCode()
This built in function computes the hash code for a string S as
S[0]*31^(n-1) + S[1]*31^(n-2) + … + S[n-1]*31^(n-n)
= ch1*31^(n-1) + ch2*31^(n-2) + … + chn
where S[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. This function may NOT be used.
Insertion and Collisions
Your insert function must deal with collisions (a collision occurs when two different
strings have the same hash value). You must use linear probing to deal with
collisions. You should test your insertion method carefully. In particular you
should ensure that insertion still works correctly when the hash table is nearly
full.
For one test, consider setting your hash table’s size to be smaller than the size of
your word list (see below) and attempting to insert the entire word list into the
hash table. This may cause errors that you might not encounter with smaller test
PAGE 2
data sets. When you get your hash function working correctly, and your hash
table is an appropriate size you should be able to successfully enter all the words
in the word list (see below) into it.
Let N be the number of strings to be stored in the table. Choose an array size
that will have a load factor around 1/3. That is, make the size of the array larger
than 3*N. You must choose a modulus that is prime (i.e. choose an actual array
size that is a prime number just over 3*N) and have your program automatically
choose this prime number. Automatically means that your program needs to use
the size of the word file as a starting point in your search for a prime; do not hardcode a value that happens to work for this data set.
Spell Checker
Use your hash table to implement a simple spell checker. The spell checker
should load a dictionary into a hash table, and then test each word in a given
document to see if it is contained in the dictionary. For the dictionary you must
use the list of frequently used words given in the text file
“SpellCheckDictionary.txt” posted on the website. Store this file in the project
for access by your program in the project.
There are two documents to be spell-checked given at the end of this assignment.
Place the first document in a text file called TestFileDogs.txt. Place the second in
a file called BillOfRights.txt. Your sample runs should include checking both of
these files.
Your spell checker should thus be implemented as a program that reads in the
dictionary file and the name of the file to be checked, and then checks the file for
possible spelling errors.
Extra Credit
Extra credit may not be counted if it is not explicitly stated in the readme document. It is your
responsibility to document in the Readme file what you think counts as extra credit. It is not
our job so somehow deduce what you did for extra credit.
There are many options for extra credit.
a. Use excellent program style (see the posted programming guidelines). Pay special
attention to the use of alignment, comments, and naming.
b. Develop a good graphical user interface.
c. Use JavaFX for the graphical user interface
PAGE 2
d. Present good documentation of the project.
e. Augment your spell checker so that it tries to change one letter in an incorrect
word to find some valid word to suggest.
f. Check a misspelled word against a list of common misspellings.
g. Use a special dictionary (there are some online).
h. Show that your hash table works correctly when the table is almost full or totally
full.
i. Allow the user of the GUI to enter his or her own text to be checked.
j. Demonstrating the kind of test used to ensure that the program is reliable, without
any kind of error.
k. Other options of your own are also fine, just try to be reasonable.
There is no extra credit for the use of pointers, e.g. to achieve chaining of
collisions.
Notes
The following incomplete code fragments may be helpful. The first reads a
dictionary into a hash table:
File F = new File(“Dictionary1.txt”);
Scanner dictFile = new Scanner(F);
String line;
while (dictFile.hasNextLine()) {
line = dictFile.nextLine();
// insert the words in line into the hash table
}
For reading a document into an array of single words, consider:
public static String readFile(String fileName) {
// Reads the text file fileName into a single string of words
PAGE 2
File F = new File(docName);
Scanner docFile = new Scanner(F);
String result, line;
result = “”;
while (docFile.hasNextLine()) {
line = docFile.nextLine();
result += line + “\n”;
}
return result;
}
public static String[] getWords(String str){
// Breaks str into an array of words
// Splits str on the basis of blanks
// Returns an array of words
}
For testing if an integer is prime:
boolean isPrime(int n) {
if (n%2==0) //check if n is a multiple of 2
return false;
else
for(int i=3; i*i<=n; i+=2) {
if(n%i==0)
return false;
PAGE 2
}
return true;
}
Test Set 1 – Simple text
This is a test document.
How many dogs can fly?
Do you think this realy works?
Test Set 2 – The Bill of Rights
Article the first — Not Ratified
After the first enumeration required by the first article of the Constitution, there shall be
one Representative for every thirty thousand, until the number shall amount to one hundred,
after which the proportion shall be so regulated by Congress, that there shall be not less than
one hundred Representatives, nor less than one Representative for every forty thousand
persons, until the number of Representatives shall amount to two hundred; after which the
proportion shall be so regulated by Congress, that there shall not be less than two hundred
Representatives, nor more than one Representative for every fifty thousand persons.
Article the second — Amendment XXVII — Ratified 1992
No law, varying the compensation for the services of the Senators and
Representatives, shall take effect, until an election of Representatives shall have intervened.
Article the third — Amendment I
PAGE 2
Congress shall make no law respecting an establishment of religion, or prohibiting the
free exercise thereof; or abridging the freedom of speech, or of the press; or the right of the
people peaceably to assemble, and to petition the Government for a redress of grievances.
Article the fourth — Amendment II
A well regulated Militia, being necessary to the security of a free State, the right of the
people to keep and bear Arms, shall not be infringed.
Article the fifth — Amendment III
No Soldier shall, in time of peace be quartered in any house, without the consent of the
Owner, nor in time of war, but in a manner to be prescribed by law.
Article the sixth — Amendment IV
The right of the people to be secure in their persons, houses, papers, and effects,
against unreasonable searches and seizures, shall not be violated, and no Warrants shall
issue, but upon probable cause, supported by Oath or affirmation, and particularly describing
the place to be searched, and the persons or things to be seized.
PAGE 2