Homework 10

CS 336 Fall 2003

Werth

Due Friday Dec 5, 2003

Homework to turn in

1. Section 8.7: 4, 6, 8, 12, 18

2. Section 8.8: 2, 4, 6, 18

3. Problem 12 Section 3.6 page 290. Use the following loop invariant:

a=dq+r AND r=>0. Use the method of weakest preconditions.

4. Show the total correctness of the following program with the pre- and post- condition and loop invariant given, using weakest precondition arguments where you can. Invent your own bound function.

Precondition: (m=>1) AND (n=>1)

Postcondition: c=C(m,n) {combinations of n things out of m}

Loop invariant: (m=>1) AND (c=C(m,k-1)) AND (k<=n+1)

You may use the following equality:

for m=>1 AND k=>1: C(m,k-1)*(m-k+1)/k = C(m,k)

You may assume that c*(m-k+1)/k is an integer

c:=1

k:=1

while k<=n

begin

c:=(c*(m-k+1))/k

k:=k+1

end

Things to study for the Pop Quiz:

1. Study the notes on total correctness and on planar graphs and graph coloring

2. Section 8.7: 3, 5, 7, 13

3. Section 8.8: 1, 3, 5, 17, 23, 27

4. Section 3.6: 7, 13