With this project, you will exercise and enhance your abilities with the use of data structures and algorithms studied throughout our course, including array-based data structures, linked lists, searching algorithms, hashing, dictionaries, and algorithmic techniques. Based on the topics learned, you will design and implement your own solution for the given problem.
Write a spell checker that stores a set of words, W, in a hash table and implements a function, spellCheck(s), which performs a spell check on the string s with respect to the set of words, W.
If s is in W, then the call to spellCheck(s) returns an iterable collection that contains only s, because it is assumed to be spelled correctly in this case. Otherwise, if s is not in W, then the call to spellCheck(s) returns a list of every word in W that could be a correct spelling of s.
Your program should be able to handle all the common ways that s might be a misspelling of a word in W, including
• swapping adjacent characters in a word;
• inserting a single character in between two adjacent characters in a word;
• deleting a single character from a word; and
• replacing a character in a word with another character.
The input to your program will consist of the name of a text file, and strings of characters manually entered by the user. The text file will contain the set of words, W, one word per line, and should be read in the program when the program starts. The strings of characters input by the user will be used to test the hash table and the spellCheck function. The program will keep running the tests until the user enters the string “quit”.
Create classes SpellChecker and HashTable to implement the spell checker and the hash table, respectively. Create a UML class diagram that describes your class design.
Note: This exercise is a variation of Project P-9.1 in Chapter 9 of the textbook.
1. Create a folder and name it Project.
o Inside this folder, create the subfolders Docs and Programs.
o Place the UML diagram document, a text file with a set of words, and a screenshot of the execution window in the folder Docs. Place the source code files (i.e., .h and .cpp files) you created in the folder Programs. Do not submit other files or folders, including those automatically generated by the IDE.
o Compress the Project folder and submit the resulting zipped folder.
2. The deadline for submission is Sunday at midnight at the end of Week 7.
Category Points % Description
Submission 7 7 The student has submitted the project solution using the requirements for deliverables specified in the project description.
Organization and Cohesiveness 7 7 Code is expected to be neat, organized, readable, and commented.
Content 86 86 • UML diagram: 16 points
• Implementation of HashTable class: 25 points
• Implementation of SpellChecker class: 25 points
• Testing the described operation: 20 points
Total 100 100 A quality project will meet or exceed all of the above requirements.
First of all, it is important to have a clear idea about what the problem is. Be sure you understand its parts and relationships. Second, think carefully about the data-structuring portion of the project, because there are a number of variables to take into consideration. Third, as a software project, a design is required before starting the implementation, so make sure your UML class diagram is not missing any important components. Finally, test your project components, from the individual units to the entire system.