Program 4: Spelling Corrector using Dynamic Programming

Due Date and Submission Requirements

Due Date: Sunday, May 5th at 11:59 p.m.
Partner Information: You are allowed to work with one partner. Both group members need to submit to D2L. Be sure to indicate in your submission who your partner is. Each Java class should have the name of each student in a comment at the top of the program
Submission Instructions: Upload your solutions (.java files) to the BrightSpace(D2L) Program 4 Dropbox.

Background and Directions

In this assignment, you will be building a program that identifies a misspelled word, and then suggests a list of similar words (similar to if you mispelled something you were googling). You will use the Edit Distance Dynamic Programming (discussed during 4/18 lecture) to identify similar words to the misspelled word.
You will use words.txt (same file from program 2) as a list of words in the English dictionary. The user will enter a word, and then you will need to compute the edit distance between the user input word and all words in the input file. You should be able to copy and paste the code that we wrote in class on 4/18.

You will need to identify if the user input word is mispelled. You can reuse your technique from program 2. If the word is misspelled, you will need to identify the top 10 words that are the most similar to the misspelled word, along with their edit distance. If the word is not misspelled, the program will print out "The word is spelled correctly". The program should keep on looping and asking for a new word. All the words in the file are lower case, so you will need to convert the input word to be lowercase.

Input files

words.txt contains a list of (most) of the words in the english dictionary.

Coding Style and Readability

I want to ensure that you are writing quality, readable code, so 10% of your grade will come from code readability and coding style. These are the things that the TAs and I will be checking for:

Comments. Each method should have a brief comment explaining what it does or why its there. Getter and Setter methods don't need comments. If you have a long, complex line of code, you should probably leave a comment explaining that line of code as well.
Indentation. Your indentation should be consistent. Code that belong inside of a class, method, loop, if statement should be indented inside of it. If you are using Eclipse, you can press CTRL + A to highlight all your code, and then CTRL + I to auto format/indent your code.
Dead code. Large chunks of code that are commented out, or never executed should not be submitted. Delete any dead code before you submit. If you have a few print statements for debugging purposes commented out, that is fine.
Naming Conventions. Class names need to be capitalized. The first letter of method names and variable names should not be capitalized.

Sample Output

Sample output showing spell corrections
Sample output showing spell corrections
Sample output showing a correctly spelled word

Your words still need to be an ascending order, and the edit distance caclcuations still need to be correct, but your output might have a slightly different ordering of words, and that is ok! There might be some words you see in your output that were not seen in my sample output, and if the edit distance calcuation is correct, there should be nothing to worry about.

Optional Hints

I would recommend making a Word class that holds the text of the word, and the edit distance between the word and the user input.
You can use a PriorityQueue<Word> to hold the words, and then sort it from least to greatest based on the edit distance of the objects.

Restrictions

You must use the Edit Distance dynamic programming algorithm we discussed in class. Here is the code we wrote in class that you should be able to copy and paste.

Given a memoization table, dp, (initalized with all -1s), two strings, and their lengths, this method computes the edit distance between the two words in polynomial time.

Grading (100 points)

Criteria	Points
Program identifies mispelled words	10
Program computes the edit distance between the misspelled word and all words in the text file	30
Program prints out top 10 words with the smallest edit distance	20
Dynamic Programming is used to compute edit distance	20
Program continually loops and asks for a new word	10
Your program follows good coding style and readability practices	10

Program 4 solution