A skeleton version of the program spellchecker.py will appear in your cs21/labs/08 when you run update21. In addition, this will copy two documents called letter and correct that can be used for testing, as well as the start of a list of words to ignore in the file called ignore.

You may work with a partner on this assignment. The best way to work as a team is to sit together to design and to code your solution. Take turns typing and watching. If you work with a partner, put your name and the name of your partner in the list of authors at the top of your program. Only one partner should run handin21 to submit the files for the group. Both partners will receive the same grade.

For this assignment you will implement an automated spell checking program that uses both searching and sorting. You should continue to practice using top-down design, and focus on breaking up the problem into appropriate functions. Also be sure to test your program incrementally.

You will use a dictionary of words that is available in a file on our system to determine whether each word in the document is a valid word. However, some valid words like Swarthmore will not appear in this dictionary. Therefore you will need another file of words, created by you, that should also be considered correct.

The goal of your program is to report all misspelled words found in the document. For example, suppose you had the following document called letter:

Dear Sam,

How are you?  I'm fine, but I mis seeing you more oftn.  Hope allis
well with your family, especialy your brother. I'll be stoping by next
Satuday when I get home from Swarthmore.  Love, Alice

Running the spell checker on this document should result in the following interaction with the user:

Enter filename of document to spell check: letter
Enter filename of list of words to ignore: ignore

The following errors were found by the spell checker:
mis
oftn
allis
especialy
stoping
Satuday

In the above example, the ignore file only contained the words Swarthmore and Chopp. The names Alice and Sam are actually in the dictionary.

Focus initially on checking whether the words in the document are found in the standard dictionary.

• Read in the name of a document to spell check.
• Create a list of words from the system dictionary file /usr/share/dict/words that will be used to check the spelling of every word in the document. The words are stored in sorted order in this file. Note that this dictionary file is huge, so when testing you may only want to print a small section of it.
• Read in each word from the document. You can split each line based on a space to get each word. You can use strip to remove punctuation.
• Use binary search to look up each word from the document in the sorted list of dictionary words. As you look up words from the file, add any misspelled ones to a list of misspelled words. Capitalization should be ignored (i.e. the word "Horse" and the word "horse" should both be determined to be correctly spelled by your program). You can use the string method lower to convert a string to all lower case letters.
• Display the results of spell checking the document. Either:
  (a) a message that there are no spelling errors;
  (b) a message that there were spelling errors and printing out the words from the misspelled list.

Implement and test this functionality before moving on to the next step.

Once you have the basic spell checking functionality implemented from above, you can add the ability to ignore other words not found in the dictionary. Many spell checking programs use this ignore list idea. The ignore list often contains proper nouns (e.g. Chopp), well known acronyms (e.g. WWW) that do not appear in a dictionary, but are also not misspellings.

With the lab starting point code is an example ignore file that you can add entries to. Just be sure to keep in the line break after the very last line in this file (just add new words to the top of the file to avoid making this change).

• In addition to asking the user for the name of the file to spell check, ask the user for the name of a file containing additional words to ignore.
• Read the words from the ignore file into a list and sort the list using the selection sort algorithm that we discussed in class. The algorithm is given below:

  for each position i in the list (except the last)
    indexOfMin = i
    for each position j in the list starting from i 
      if the item at position j is smaller than the item at indexOfMin
         indexOfMin = j
    swap the items at indexOfMin and i
  

• Modify the spell checking functionality so that only when a word does not appear in the dictionary and does not appear in the ignore list should your spell checker count it as misspelled.

1. Your main function should be short and concise. You must break the problem up into suitable functions.
2. You must use binary search to check for words in the dictionary.
3. You must use selection sort to sort the list of words to ignore.

Note:These are not required parts of the assignment.

Once you have the full functionality implemented and tested. You can try adding some additional features. Here are some suggestions:

1. Change your program so that it only lists a misspelled word one time, rather than once per misspelled occurrence in the document.
2. Handle words inside quotes and parentheses (i.e. "dogs" and (dogs) should be considered correctly spelled words.
3. Ignore non-alphabetic collections of characters, like numbers.

These features should not be added by using the ignore file, but should be added to the spell checking functionality.

A good test case for these changes is something like the following that contains quotes, numbers, and parens:

Barak Obama said today, "I'm pleased with the passage of the Health
Care bill."  After 8 months of negotiations (which were sometimes
quite heated), the bill is a reality.

With the above features added, your program should indicate that this document has no misspelled words.

Once you are satisfied with your program, hand it in by typing handin21 in a terminal window.