CS21 Lab 8: searching

Due 11:59pm Tuesday, Nov 13

Run update21, if you haven't already, to create the cs21/labs/08 directory (and some additional files). Then cd into your cs21/labs/08 directory and create the python programs for lab 8 in this directory (handin21 looks for your lab 8 assignments in your cs21/labs/08 directory):

$ update21
$ cd cs21/labs/08
1. Comparing Linear and Binary Search

Create a program called compareSearches.py that allows the user to search for words in the system dictionary (/usr/share/dict/words). Your program should use both linear and binary searches to look for the user's word. In addition to providing found/not found information, your program should report how many "steps" each search took when looking up the given word.

Here are some examples of a working program:

$ python compareSearches.py 

Type in a word and I will look it up in the dictionary.
Enter a blank line to quit...

word: zucchini
linear search: FOUND in 99147 steps
binary search: FOUND in 12 steps

word: Andrew
linear search: FOUND in 639 steps
binary search: FOUND in 17 steps

word: abcdefg
linear search: NOT FOUND in 99171 steps
binary search: NOT FOUND in 16 steps

word: PIZZA
linear search: NOT FOUND in 99171 steps
binary search: NOT FOUND in 16 steps

word: help
linear search: FOUND in 50211 steps
binary search: FOUND in 15 steps

word: harmlessly
linear search: FOUND in 49586 steps
binary search: FOUND in 1 steps

word: quirking
linear search: FOUND in 74379 steps
binary search: FOUND in 2 steps

word: 

$
2. Spelling Checker

Write a program called spellchecker.py that asks the user for a file name and then checks that each word in the file is spelled correctly.

Here's an example:

$ cat letter.txt 
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

$ python spellchecker.py 

Enter name of doc to spell check: letter.txt

The following errors were found by the spell checker: 
mis
oftn
allis
especialy
stoping
Satuday
Requirements and helpful tips
ADDITIONAL EXAMPLES

Extra Challenges...

These are not part of the lab assignment, but just "fun" extra things you can add to your program. Please don't try these until you have completed the above assignment. And they are just for fun -- no bonus points or extra credit. :(


Submit

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