# 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??

- 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

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??

```