CSC148H lab -- week 10

Here are the instructions for the week 10 CSC148H lab. To earn your lab mark, you must actively participate in the lab. As always, you will work as a pair, taking turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead. At the end of each exercise, show your TA what you've done, and then switch roles.

This week's exercises are on the topic of binary search and developing correct programs.

Exercise 1: Binary Search Correctness

Download the file binsearch1.py. It is a potentially correct implementation of binary search, and is very similar to the implementation we saw in class. The only difference is that we set i = mid instead of i = mid + 1 when the if condition holds.

The goal of this exercise is to determine whether this binary search is correct (including whether it always terminates). As we have been discussing in class, we can show that a program that uses a loop is correct by finding an invariant and variant such that all of the following hold:

• The invariant is true prior to loop entry.
• Under the assumption that the invariant holds prior to a loop iteration, it still holds after the iteration completes.
• The invariant, together with the negation of the loop guard, allows us to conclude our program's postcondition. (In our original binary search, we knew that once the loop terminated, i and j were equal. By the invariant, the only place the element we are searching for can possibly exist is a[i], since everything to the left is too small, and if a[i] is too large, so is everything to its right.)
• The variant is always zero or positive.
• The variant is decreased on each iteration of the loop.

For the modified binary search in binsearch1.py, determine whether each of these requirements holds. (If one or more does not hold, the program is incorrect.) To do this, it may be helpful to run the program on sample inputs to try to uncover situations in which it does not work correctly. You may also wish to print out the values of i and j that the binary search uses on each iteration. Based on what you find, you can narrow your focus. For example:

• If the program always terminates but yields incorrect results, there is something wrong with the invariant.
• If the program sometimes does not terminate, but yields correct results when it does terminate, there is a problem with the variant. (Recall that the variant implies termination. The variant is always an integer greater than or equal to 0, and we cannot decrease the variant an infinite number of times: there is a finite number of integers between zero and a given positive integer. So, at some point, the variant will reach 0 and the loop will terminate.)
• If the program sometimes does not terminate, and yields incorrect results when it does terminate, there is likely a problem with both the variant and invariant.

Discuss your findings with the TA. Is this binary search correct?

Exercise 2: Binary Search Correctness Again

Download the file binsearch2.py. It is another potentially correct binary search. Perform the same exercise as above using this version of the binary search, and discuss your findings with the TA. Is it correct?

Exercise 3: a Multiplication Algorithm

Consider the following observations that we can use to reduce the multiplication of two positive integers x and y to successive multiplications and divisions by 2:

• If x is even, x*y has the same value as (x/2)*(y*2).
• If x is odd, x*y has the same value as (x/2)*(y*2)+y. (We are assuming that / here is integer division, since x and y are integers.)

Use these observations to write a function that takes two positive integers x and y and multiplies them using only multiplications by 2, divisions by 2, and additions. You should begin by saving the values of x and y in two new local variables, so the original numbers you are multiplying are not lost. Before you write your loop, come up with an invariant and variant. An incorrect invariant would state that multiplying your two local variables yields the same result as multiplying x and y, because at some point the variable you divide by 2 will be odd. You will have to introduce a third local variable to accumulate the amount "lost" in these cases, and be able to combine it with your other local variables to represent the product of x and y. Be sure to also include the precondition (when does your program work?) and postcondition (what does it do when it is called with variables satisfying its precondition?).

Exercise 4: Celebrities

Imagine we have n people represented by the integers 0 through n-1. Define a celebrity as a person whom everyone knows but who knows no one. For example, consider the following collection of facts about the people 0, 1, 2 and 3:

• 0 knows 1
• 0 knows 2
• 0 knows 3
• 1 knows 3
• 2 knows 3

The goal of this exercise is to come up with an O(n) algorithm to determine the celebrity in a group of people, or otherwise determine that there is no celebrity.

You should write a function that takes a two-dimensional "array" (a list where each item is a "row" represented by another list). If item [i][j] is 1, person i knows person j; otherwise, i does not know j. Assume that all elements on the diagonal (i.e. [i][i]) are 1: everyone knows themselves.

Your function should use a loop to successively eliminate people from celebrity contention until only one person remains. In other words, begin with everyone as a potential celebrity, and prune this down on each iteration. Write a loop invariant that captures this intuition; together with the negation of the loop guard, it should allow you to conclude that the one person remaining is the only possible celebrity.

Hint: you can use a list that represents all current potential celebrities. On each iteration, take two people in that list and see if one knows the other. The result of this question will always allow you to eliminate one of them from your list. Think about how to do this; be careful to remove the candidate in constant time.

Once you have your potential celebrity, use a second loop to determine if they are actually a celebrity. Of course, this loop must be O(n) as well, or the entire function cannot be. Return the celebrity if one exists; otherwise raise a NoCelebrity exception.

Exercise 5: Majorities (Time Permitting)

Implement the majority algorithm from class in Python. Be careful to implement the second loop (the one that checks if our majority candidate has a majority) correctly. Include a loop invariant on both loops. On the second loop, the loop invariant should capture the intuition that the count of votes we are maintaining is the number of votes for cand that we have seen so far. Please post your solution on the course bulletin board.