1. Objective: Design and implement a spell checker

1. Objective: Design and implement a spell checker

2. Problem Description Spell checker is an application program that flags words in a document that may not be spelled correctly. If the word is not found it is considered to be an error. Most spell checker programs are running concurrently with the text editing programs, this type of spell check is called on-line spell checking. Since, in this course, we are focusing on the algorithms and corresponding data structure implementation, our goal in this project is to develop an off-line spell checker, which has the following basic functions.

a) Your program should be able to read an external dictionary text file and construct the corresponding data structures for the spell checker.

b) Your program should be able to read a regular text file and implement the spell check task on it.

c) The output of your program should be a list of unrecognized words with the line number information from the original text file.

Assume the dictionary is alphabetically ordered.

i) (10 points) use an linear data structure (array/List/ArrayList etc.) and binary search algorithm

ii) (15 points) use Ternary Search Tries(TST) and radix search

iii) (5 points Extra Credit) Compare the memory usage of the two implementations of spell checker program listed above.