Program 4: Spelling Corrector using Dynamic Programming

Due Date and Submission Requirements

Due Date: Sunday, May 4th 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 misspelled words in a sentence, 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/17 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 setence, and you will first need to identify any misspelled and print out which words were misspelled (just like with program 2). For each misspelled word, you will need to compute the edit distance between that word and all words in the input file (words.txt). You should be able to copy and paste the code that we wrote in class on 4/17.

You will need to identify if the user input word is mispelled and place a < and > around the word. You can reuse your technique from program 2. Words may be uppercase, lowercase, or a mixture of both. Words may also end in a punctuation mark (. , ! ? ). If the word is misspelled, you will need to identify the top 5 words that are the most similar to the misspelled word, along with their edit distance. The program should keep on looping and asking for a new sentece. All the words in the file are lower case, so you will need to convert the input word to be lowercase.

If a sentence has no spelling mistakes, then a "Good job" message should be printed out.

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 sentence where all words are spelled correctly

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

You should copy and paste some of the code from program 2 to identify misspelled words.

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.

Grading (100 points)

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

Program 4 solution