CS21 Homework #7: Searching and Recursion
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.
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.
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.
Once you are satisfied with your program, hand it in by typing handin21 in a terminal window.