Homework 11

CS 336 Spring 2003

Werth

 

Due May 1, 2003

 

Problems to turn in for the homework

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

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

3. <Change: (1<=k) added to loop invariant> 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) AND (1<=k)

                 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

 

 

Problems 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