knerr cs21 notes...

back to schedule

WEEK08: searching, analysis of algorithms
---------------------------------------------------------------
 W: linear and binary search on words

ANNOUNCEMENTS:
 - quiz 4 this Friday...while loops, file I/O!
 - practice quiz is up on the web page
 - Lab 7 due *next* Tuesday night (Nov 3)
 - if you want to use Andy Danner's lab 6 functions in your
    lab 7, do this:

from lab06 import *

   then use his GetAConsonant, GetMenuOption, IsAVowel, PrintMenu
   functions. For the function help info, do this:

>>> import lab06
>>> help(lab06)



SEARCHING words:

 - can use in operator for numbers or words:

>>> L = ["dog", "cat", "pony"]
>>> "fish" in L
False
>>> "pony" in L
True

 - how does the "in" operator work?? does it use linear search,
   binary search, or some other search??

YOUR TURN:

 - copy ~jk/inclass/goodwords.py and figure out what it does!

 - now copy wordsearch.py and see how it uses goodwords

 - now add your linear and binary search functions from last time
   to wordsearch.py, and see if you can get it to work:

$ python wordsearch2.py 
Found apple at index 2401 using linear search
Found apple at index 2401 using binary search

Found pony at index 42026 using linear search
Found pony at index 42026 using binary search

Linear search did not find Swarthmore
Binary search did not find Swarthmore

Linear search did not find swarthmore
Binary search did not find swarthmore

VIM TIPS:

 - when you want to copy a file into the file you are currently
   editing, use :r filename

   (note: you must be in command mode to do this. If you're not
    sure what mode you're in, hit the ESCAPE key to get to command mode)

 - if you want to cut and paste with the mouse, try this:

     * in the file you want to add to, make sure you're in INSERT
       mode and at the right line. Now hit the F2 key to get into
       INSERT(paste) mode

     * with the mouse, use the left button to drag across the text
       you want to copy, then go to the vim window and hit the middle
       mouse button to paste the text

 - if you want to move a block of text over to the right or left, try this:

     * get to command mode (hit the ESCAPE key)
     * use shift-v and the arrow keys to highlight a block of code
     * hit shift-greaterthan to move the block right or
           shift-lessthan to move the block left

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