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
        /home/your_user_name/cs21/inclass
    $ mkdir w08-search        
    $ cd w08-search
    $ pwd
      /home/your_user_name/cs21/inclass/w08-search
    $ cp ~adanner/public/cs21/w08-search/* .
    $ ls
	

Open goodwords.py in vim. In a separate window, change to the w08-search directory so you can run the program using python goodwords.py. 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 search.py that wants to import code from goodwords.py. We can add from goodwords import * to the top of search.py if goodwords.py is in the same directory as search.py.

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

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 search.py 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?

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:40 PM