knerr cs21 notes...

back to schedule

WEEK08: searching, analysis of algorithms
---------------------------------------------------------------
 F: real-world example...anagrams

ANAGRAMS:

 - copy ~jk/inclass/anagrams.py and run the code:

$ python anagrams.py 

  -- Welcome to A N A G R A M --
  
  Enter a word and I'll find the anagrams (QUIT to quit): miles

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
miles
limes
smile
slime
selim
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

 - look at the code to see how it works. You should be able to understand
   all but the Anagram function, which uses recursion (we'll cover that
   next week)

 - the Anagram function just creates a list of all possible permutations
   of the given word. If you type in cat, Anagram creates the following
   list: ['cat', 'act', 'atc', 'cta', 'tca', 'tac']

 - this list of all permutations is sent to displayAnagram which only
   prints out the real English words.

 - what happens when I type in an 8-letter word???

 - why does it run so slow???

 - for a 3-letter word there are 6 permutations. How many are there
	 for a 4-letter word? How about a 5-letter word??

YOUR TURN:

 - change the displayAnagram function to use a binary search, instead
   of this linear search:

       if w in english and w not in uniqalist:

   make that something like this:

       if binarySearch(w,english) and w not in uniqalist:

   so your binarySearch function needs to return a True if the word is
   found, and a False if not found.

   Also, you probably need to sort the english word dictionary. Where
   is a good place to do that? (NOTE: if you have a list, L, you can use
   python's default sort by doing L.sort())


SOLUTION:

 - see /home/jk/inclass/binarysearchanagrams.py for a solution

 - how many anagrams does the word "education" have?

 - how long does it take to figure that out with binarysearchanagrams.py
   vs. anagrams.py??