Searching and Sorting?

In class exercises
Create a w08-search subdirectory in your cs21/inclass directory, and from within your w08-search subdirectory copy over some python files from my public directory:

    $ cd 
    $ cd cs21/inclass
    $ pwd
    $ mkdir w08-search        
    $ cd w08-search
    $ pwd
    $ cp ~adanner/public/cs21/w08-search/* .
    $ ls
Good Words
Open in vim. In a separate window, change to the w08-search directory so you can run the program using python This should be somewhat familiar except for the if __name__ == "__main__": bit, so let's explain that.

We've seen that we can use import to add extra functionality to our python programs. Examples are from math import *, from graphics import * or from random import randrange. We can also import functions from code we write. For example we could have a file called that wants to import code from We can add from goodwords import * to the top of if is in the same directory as

Now note that has some test code. When we run python we want to run this test code to see if works. However, when we import goodwords we may want to run different tests and not the ones in The line if __name__ == "__main__": allows us to control this behavior. When we run python, the expression evaluates to True, but when we use import the expression evaluates to False in

Earlier in the semester we mentioned that Computer Science is concerned with two major questions: (1?) (2?). The study of algorithms allows computer scientists to answer these questions. We will motivate an introduction to algorithms using the problem of searching.

Under what conditions can a computer algorithmically search for and find information? What is the minimum set of input? What is the format of the input? What are the possible outcomes? How can a computer express thouse outcomes in output? Finally, what steps should a computer take to perform this task and how do the number of steps needed depend on the size of the input?

We will discuss two searching methods: linear search and binary search.

Open in vim.

What should the search functions return? Let's describe linear search, implement it, test it, and analyze its run-time together. What is the minimum number of steps required? What is the maximum number of steps? What constitutes a step?