CS21 Homework #7: Searching and Recursion

Due 11:59pm Tuesday, November 6, 2007

You should save your program for this assignment in cs21/homework/07. A skeleton version of the program will appear in this directory when you run update21 in a terminal window. The program handin21 will only submit files in this directory. You should work alone on this assignment.



Comparing Linear and Binary Search

Edit the file compareSearches.py to create a program that will demonstrate the clear benefit of using binary search over linear search as shown below:

This program compares the efficiency of binary search to
linear search by looking up words in a dictionary.

Enter a word to lookup or 'quit' to end> aardvark
Linear search: Found in 2 steps
Binary search: Found in 15 steps

Enter a word to lookup or 'quit' to end> apple
Linear search: Found in 3033 steps
Binary search: Found in 13 steps

Enter a word to lookup or 'quit' to end> zebra
Linear search: Found in 80332 steps
Binary search: Found in 16 steps

Enter a word to lookup or 'quit' to end> swarthmore
Linear search: NOT found in 80461 steps
Binary search: NOT found in 16 steps

Enter a word to lookup or 'quit' to end> quit

Your program should use the dictionary stored in /usr/share/dict/words to create a list of all the words that are not proper nouns. Then you should repeatedly ask the user for a word to look up and then report the number of steps it takes each of the searches to find the word or discover that it is not in the list. Your program should end when the user types: quit.



Palindromes

A palindrome is a sentence that contains the same sequence of letters reading it either forwards or backwards. A classic example is: "Able was I, ere I saw Elba." Another example is: "A man, a plan, a canal, Panama!"

In the file palindrome.py, write a recursive function called isPalindrome that returns True when a given string is a palindrome, and otherwise returns False. The basic idea is to check that the first and the last letters of the string are the same letter. If they are, then the entire string is potentially a palindrome, as long as everything between those letters is also a palindrome. There are a couple of special cases to check for. If either the first or last character of the string is not a letter, you can ignore that letter and check to see if the rest of the string is a palindrome. Also, when you compare letters, make sure that they are all the same case.

Use your function in a main program that repeatedly prompts the user for a phrase and then reports whether or not it is a palindrome, as shown here:

This program will test if a series of phrases are palindromes.

Enter a phrase or 'quit' to end: wow
This is a palindrome!

Enter a phrase or 'quit' to end: mom
This is a palindrome!

Enter a phrase or 'quit' to end: wow mom
Sorry, this is not a palindrome.

Enter a phrase or 'quit' to end: wow, mom wow
This is a palindrome!

Enter a phrase or 'quit' to end: Able was I, ere I saw Elba.
This is a palindrome!

Enter a phrase or 'quit' to end: A man, a plan, a canal, panama.
This is a palindrome!

Enter a phrase or 'quit' to end: quit

Can you think of any other interesting palindromes? If so, add them as comments in your program.



Submit

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