Exercise 1: Mystery Program

1  print "Think of a number between 1 and 100, but don't tell me what you choose."
2  min_n = 1
3  max_n = 100
4  right_answer = False
5 
6  while not right_answer:
7     mid_n = (max_n + min_n + 1)/2
8     answer = raw_input('Is it ' + str(mid_n) + '? ')
9     if answer[0] == 'y':
10        right_answer = True
11    elif answer.startswith('higher'):
12        min_n = mid_n + 1
13    elif answer.startswith('lower'):
14        max_n = mid_n - 1
15    else:
16        print 'Sorry, I don\'t understand your answer.'
17
18 print 'Woohoo! I got it!'

1. The while loop exits when the variable right_answer is True. What will cause right_answer to be true?
   
   
   
   
2. How many times will the program print out 'Woohoo! I got it!'?
   
   
   
   
3. What are we using the variable answer for?
   
   
   
   
4. The program makes a guess in line 8. What user responses will be understood by the program after it makes it’s guess?
   
   
   
   
5. If the program gets the response 'higher', what does that tell it about its guess?
   
   
   
   
6. What algorithm is the program implementing? You saw something very similar to this in class.
   
   
   
   
7. So what are the variables min_n, max_n and mid_n used for?
   
   
   
   

Exercise 2: Sorting and Movie Stats

In this exercise, we will explore the sort method available for lists in python.

Exercise 2.1 - Sorting

Below is some code that shows a list of tuples. Tuples are sequences, just like lists except they are not mutable, i.e. you cannot modify them.

tuples_list = [ ('t', 10), ('w', 2), ('d', 8), ('p',3) ]

for (letter, number) in tuples_list:
    print letter, number

for pair in tuples_list:
    print pair[0], pair[1]

Try running the code above in IDLE. You will notice that both loops print out the exact same thing.

Now let's see how the sort method works. Try running the code below:

tuples_list = [ ('t', 10), ('w', 2), ('d', 8), ('p',3) ]

for (letter, number) in tuples_list:
    print letter, number

tuples_list.sort()
for (letter, number) in tuples_list:
    print letter, number

You should notice that the second loop prints the tuples sorted in alphabetical order.The default behavior of the sort method is to sort the tuples in the list based on the value of the first element in each tuple. So what can we do to print the list sorted in numerical order? The sort method has an optional parameter that takes a function that compares two objects, x and y, and returns a negative number, 0 or a positive number depending on whether x<y, x==y, or x>y. During the course of the sort the relationships must stay the same for the final list to make sense. Below is an example of how this works.

def numeric_compare(x, y):
   if x[1] > y[1]:
      return 1
   elif x[1] == y[1]:
       return 0
   else:
       return -1

tuples_list = [ ('t', 10), ('w', 2), ('d', 8), ('p',3) ]

for (letter, number) in tuples_list:
    print letter, number

tuples_list.sort(numeric_compare)
for (letter, number) in tuples_list:
    print letter, number

The function numeric_compare takes two tuples and compares their second elements. The line in red calls the sort method with the numeric_compare function as a parameter. Notice that now the second loop prints the elements sorted numerically, i.e. based on the second element in the tuples.

2.2 Movie Stats

The Interned Movie Database (IMDB) stores an enormous amount of movie data. There you can find a list of the top 250 most popular movies of all time. Save the file movie_list.py to your problem set 05 directory (right click on the link and click on Save link as, and give the file name movie_list.py). It contains a python list of the top 250 most popular movies. The items in the list are tuples with three elements - title (a string), year made (an integer), number of votes (an integer). Use the code below to print the list:

from movie_list import movie_list

for movie in movie_list:
    print movie

The movie_list variable is imported from the module movie_list that you saved to your directory. When you run the code above, you should get the following output:

('The Shawshank Redemption', 1994, 428500)
('The Godfather', 1972, 354504)
('The Godfather: Part II', 1974, 206385)
...
('My Man Godfrey', 1936, 6567)
('Planet of the Apes', 1968, 48691)
('Bringing Up Baby', 1938, 20476)

Your goal is to write a program prints out the following:

1. The 10 most popular movies of all times based on the user votes.
2. (Optional) The oldest movie or movies of the list, that is the movie or movies listed with the earliest year of release.
3. (Optional) The most recent movie or movies, that is the movie or movies with the newest release date (very likely 2009).

Use functions.

# Hint: To create a copy of a list, use the following:
list_copy = list[:]

# To reverse a list use:
list_copy.reverse()

Once you have your program working, you can verify the output here.

When you are done, print a copy of the file and turn it in. Make sure your name is in the comment section of your program.

Submit the file electronically by typing:

 athena% submit ps5 movie_stats.py

Exercise 3: Efficiency of Algorithms

Exercise 3.1

ALGORITHM-ONE is a for loop that calls ALGORITHM-TWO n times. ALGORITHM-TWO has time complexity O(n²). What order time complexity is ALGORITHM-ONE?

Exercise 3.2

What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2ⁿ on the same machine?

Exercise 3.3 (Optional)

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n² steps, while merge sort runs in 64nlog(n) steps. For which values of n does insertion sort beat merge sort?

Exercise 4: Your Program

When you got your admission letter from WTP, we had you fill out a form in which you answered the question: “If you were to write a computer program to do something you would find useful or entertaining, what would it
do?”

1. First, write down a one or two sentence description of your answer here. If you don’t remember what you answered, ask us, and we’ll look it up for you.
   
   
   
   
   
   
   
   
   
   
   
   
2. Now that you’ve learned a bit about computer science, do you think this is something that is do-able with current computer science technology? Why do you think that?
   
   
   
   
   
   
   
   
   
   
   
   
3. Leaving aside the issue of whether or not you could write the program, do you think the program you wanted to write would be hard for the computer to do? Why or why not?