This week we are going to write a spelling checker.

1. Use the Binary search tree program Binary Search Tree (bst3a.txt). Populate it with a dictionary, " dict45k_r.txt" contains 45,000 random words (right click your mouse over the link and use the "Save Link As.." option to transfer the file).
This program has a minor flaw that I am going to let you fix :-) A word that ends or begins with a single quote will be kept, as is, this needs to be fixed. Write an internal routine that removes leading or trailing non-alpha character. That is the word 'base or base' would be just base. Maybe it could be called trimNonChars().
If you feel this file is too small, you can try the 349,000 random dictionary file " dict349k_r.txt".

2. Process all the words in the file " puppet.txt (524,470 words)" (right click your mouse over the link and use the "Save Link As.." option to transfer the file).

3. If a word from "puppet.txt" is in the dictionary, skip it, if it is not in the dictionary, output it to a miss_spelled.txt file.

4. It is very important that you time the spell-check process and turn that in as part of your results. We will be comparing your results with another spell-checker program next week.

Helps:
Millisecond time (mtime.txt) program that demonstrates how to measure elapsed time - measure how long it takes to find the frequency of all the words in the book.

Turn in:
A source code listings and results from your timed test. A test file containing miss spelled words and the time it took to spell-check the book