Search, Sorting, Recursion and Time Complexity A Spell Checker (searching words)

You will create a C++ program that implements a spell-checker, using efficient/inefficient sorting and effi- cient search algorithms. Algorithms will require recursion and you need to analyze O(). In essence a spell checker works by comparing all the words in a document to words in a dictionary. If a word is not found in the dictionary, Then the program assumes that it is an error (misspelled word). In order to efficiently spell check a document you need to store the dictionary in a sorted array, and you need an efficient way of determining if a word can be found or not in the dictionary array. Therefore, you must use an efficient search algorithm (Binary Search) to determine if each word of the input file is present in the dictionary. You will read the dictionary file into a linked list (STL acceptable ). The dictionary file may have errors, meaning duplicate words or numbers. The dictionary file must be processed to eliminate errors and sort the words to enable efficient search. Once the file is processed, you should allocate an array and use it as the dictionary You must delete the original linked list to free memory. You will use the dictionary to check spelling of an input file (e.g. some document). The input file to be checked can either be loaded into a linked list, sorted and stored in a more efficient manner, OR it can be processed one word at the time (but keep in mind we need word frequencies). The second method is less efficient, since there could be repeated words in the input documents, but easier. In either case you must use an efficient search algorithm (binary search) to determine if each word of the input file is present in the dictionary. You should produce a list with all the words that are misspelled in the document. The major goals of the homework are to master linear recursion and understand big O(). 2 Program and output specification The main program should be called spellchecker. Call syntax example: spellchecker input=f01.txt;dictionary=dict.txt;recursive=y When asked to output the list if incorrect words to a file you must write one word per line followed by a space and the frequency (number of occurrences).