Chapter 1 and 2
 Answers

Question 1.1

For a function f(n) determine the largest problem size n that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

Note for functions with inverses, such as:

f(n) = ^v n = 1,000,000 ms, the inverse ^v n ² = n = 1,000,000² =(10⁶)² = 10¹²

f(n) = log₂n = lg n = 1,000,000 ms, the inverse 2^{lg n} = n = 2^1,000,000

f(n)	t = 1 sec. = 106 ms	t = 1 min. = 6*107 ms
n	106	6*107
lg n	21,000,000	260,000,000
n!	9 from above table 362,880	9 from above table 39,916,800

Testing vs Verification

Question 2.1

1. Our precondition assertion was easy. What is the problem with defining an assertion for the postcondition: { Q is f == n!}?
     We must compute n! to assert f == n!
    
2. How is the assert different from a proof?

       assert at execution, tests some relation to be true for given input; other inputs may fail.

       Proof not an execution, guarantees correctness of results for all valid inputs.

Question 2.2 - Give the wp for each of the following:

1. { y<5 }     x := y           { x < 5 }
2. { y < 11 } x := y - 6      { x < 5 }
3. { x < 4 }   x := x + 1     { x < 5 }
4. { x < 5-y} x := x + y     { x < 5 }

Question 2.3 - Give the wp for each of the following:

1. {x<5} y := x           { y<5 }
   {y<5} x := y           { x < 5 }
    
2.  {x<8}   y := x + 3      {y<11}
   {y<11}   x := y - 6      { x < 5 }

Question 2.4 - Is this correct? How is the postcondition weakened?

Yes. Weakened because x>-1 is true for more values than x > 0.

Question 2.5 - Is this correct? How is the precondition strengthened?

Yes. Strengthened because x>5 is true for fewer values than x > 3. Remember we want the weakest.

Question 2.6 - Determine preconditions.

1. {y>17} if (x < 5)
                then {y>17} y := y – 7; {y>10}
                else {y>2}    y := y + 8; {y>10}
    
2. {y>27} if (x < 5)
                then {y>27} x := y - 7;  {x>20}
                        {x>20}   y := x / 2;  {y > 10}
                else  {y>2}   y := y + 8; {y > 10}

Java Validation

Exercise

1. Why is a proof of correctness preferred to testing? Testing verifies behavior only for inputs tested.
2. Why, in practice, is testing done rather than a formal proof? Proofs are hard.
3. Give an example of a specification error in a function to calculate n!. Precondition allows n<0.
4. Give an example of a specification error in a function to sort an array. Precondition allows empty array.

Divide

Question 2.7

1. Give the ESC pre annotation for:

//@ pre x >= 4; //@ post \result >= 5; int increment(int x) { return x + 1; }

2. Give the ESC pre and postcondition annotations for:

//@ pre true; //@ post \result == x+1; int increment(int x) { return x + 1; }

Double

Question 2.8

1. Does the postcondition:

       //@ post (\forall int j; 0 <= j && j < A.length; A[j] ==2*\old(A[j]) );

   hold when the loop is changed to:

   i=5;
   while(i < A.length) { ...

   No, the 0..4 values are not doubled.

    

2. Does the loop invariant still hold when changed to:

   //@ loop_invariant (\forall int j; 5<=j && j < i; A[j] == 2*\old(A[j]) );

   Yes but the range is 5<=j<i. Postcondition does not hold.

    

3. Does the loop invariant still hold when changed to:

   //@ loop_invariant (\forall int j; 0<=j && j < i ; j-1 <= i);

   Yes but is useless for computing the postcondition.

    

4. Does the above loop invariant serve any useful purpose?
   No.

Maximum 

Question 2.9

1. What is the effect of removing the precondition A != null?

   A.length is possibly undefined.
      

2. What is violated by changing the postcondition to:

   //@ post (\forall int k; 0 <= k && k < A.length; A[\result] > A[k]);

   Contradicts the loop invariant which states finding the location of maximum element of A.

    

3. What would be violated by changing the loop to:

   for( i=5; i<A.length; i++)

   Contradicts the loop invariant which states finding the location of maximum element of A.

    

4. What is violated by changing the loop-invariant to:

   /*@ loop_invariant
                  (\forall int j;
                             0<=j && j < i && 0 <= maxIndex && maxIndex < i;
                             A[maxIndex] > A[j]);
    *@/

   States finding the location of the element of A greater than any element of A.

    

Insertion Sort

Question 2.10

1. What does the postcondition say in English?

   That lower indices hold values <= higher indices; the array A is sorted in ascending order.
    

2. What does the following loop-invariant say in English?

   //@ loop_invariant (\forall int k; k>=0 && k <= j-1; A[k] <= A[j-1]);

   That the maximum of A[0..j-1] is at A[j-1].

    

3. Is that what we wanted? It could be stronger but it is correct. A better specification is the one below.
    
4. What is the implication of changing the loop-invariant of the for to:

   //@ loop_invariant (\forall int k; k>=0 && k < j-1; A[k] <= A[k+1]);

   The array A[0..j-1] is sorted in ascending order.
    

5. What is the implication of changing the loop-invariant to:

   //@ loop_invariant (\forall int k; k>=0 && k < j-1; A[k] >= A[k+1]);

   The array A[0..j-1] is sorted in descending order.

    

Math Induction

Example (page 242 of Rosen): Use induction to prove that for every integer n³1:

P(n): 1 + 2 + 2² + ... + 2ⁿ = 2⁰ + 2¹ + 2² + ... + 2ⁿ = 2ⁿ⁺¹ - 1

Question 2.11 What is P(4)? P(4): 2⁰ + 2¹ + 2² + 2³ + 2⁴ = 2⁴⁺¹ - 1 = 31

Base Step: P(1)

n = 1 then:
      1 + 2¹ = 2¹⁺¹-1 = 2²-1 = 3
              3 = 3

Question 2.12 Why is P(1) the base? P(n) defined on n³1. But works for: P(0) = 2⁰ = 2⁰⁺¹ - 1 = 1

Example (page 240 of Rosen): Use induction to prove that the sum of the first n odd positive integers = n²

P(n): 1 + 3 + 5 + ... + 2n - 1 = n²

Note that:

P(1): 1=1

P(2): 1+3=4

P(3): 1+3+5=9

P(4): 1+3+5+7=16

P(5): 1+3+5+7+9=25

Question 2.13 What is P(6)? P(6)=P(5)+2n-1=25+2*6-1=36

Example: ^ is AND, v is OR.

Recall the De Morgan law that:

   ______    __    __
   A₁ ^ A₂ = A₁ v A₂   

Use induction to prove the following generalization for the De Morgan law for Boolean algebra.

         ______________     __    __          __
P(n): A₁ ^ A₂ ^ ... ^ A_n = A₁ v A₂ v ... v A_n   for every integer n³2

Base Step: P(2)

n = 2 then De Morgan's law holds:
             ______    __    __
P(2):     A₁ ^ A₂ = A₁ v A₂   

Question 2.14 Why is P(2) the base? De Morgan's Law applies to binary operations v and ^.

Example: Use induction to prove that 2ⁿ < n! for every integer n³4

P(n): 2ⁿ < n! for every integer n³4

Base Step: P(4)

n = 4 then:
   2⁴ = 16 < 24 = 4!

Question 2.15 Why is P(4) the base? Definition for n³4

Example: Prove by Induction that: 5 divides n⁵ - n

Base Step:

P(0): 5 divides 0.

Question 2.16 Why is P(0) base? To establish for a positive integers.

 

Question 2.17 (p245 of Rosen): Show for n³1:

1+2+...+n = n(n+1)/2

You might recall:

Induction Hypothesis:

    P(n): 1+2+...+n = n(n+1)/2

Base Step: P(1)=1=1(1+1)/2=2/2=1

Inductive Step:

Show:    1+2+...+n+(n+1)=(n+1)(n+2)/2

(1+2+...+n)	=n(n+1)/2	IH: P(n): 1+2+...+n = n(n+1)/2
(1+2+...+n)+n+1	=n(n+1)/2+n+1	Add n+1 to both sides
	=[n(n+1)/2+2(n+1)]/2	2/2 * (n+1)
	=[n(n+1)+2n+2]/2	Terms over common denominator
	=[n2+n+2n+2]/2	Multiply n(n+1)
	=(n2+3n+2)/2	Collect terms
\	=(n+1)(n+2)/2	Factor

 

Question 2.18 (p253 of Rosen): Find a closed-end formula by examining small values of n for:

1/2+1/4+1/8+...+1/2ⁿ

 P(1)=1/2¹=1/2=1-1/2¹

 P(2)=1/2+1/2²=1/2+1/4=3/4=1-1/2²

 P(3)=1/2+1/4+1/2³=1/2+1/4+1/8=7/8=1-1/2³

 P(n)=1-1/2ⁿ

Question 2.19 Prove above formula using induction.

Recall that 1/2*1/2ⁿ = 1/2ⁿ⁺¹

Induction Hypothesis:

P(n): 1/2+1/4+1/8+...+1/2ⁿ = 1-1/2ⁿ

Base Step:

 P(1) = 1/2¹ = 1/2 = 1-1/2¹

Inductive Step:

Show: 1/2+1/4+1/8+...+1/2^k+1=1 - 1/2^k+1

1/2+1/4+1/8+...+1/2k	= 1 - 1/2k	IH: P(k): 1/2+1/4+1/8+...+1/2k =1-1/2k
1/2+1/4+1/8+...+1/2k+1/2k+1	= 1 - 1/2k + 1/2k+1	Add 1/2k+1 to both sides
	= 1 - 2/2k+1 + 1/2k+1	Multiply 1/2k by 2/2
	= 1 + (1-2)/2k+1	Add -2/2k+1 + 1/2k+1
\	= 1 - 1/2k+1

Insertion Sort

Question 2.20 What is the order of the best case for T(n)? an+b is O(n)

Question 2.21 - What is the order of T(n) for worst case? an² + bn + c is O(n²)

Question 2.22 Which does the graph indicate is more efficient? x*x has a lower growth rate by 1000x.

 

Divide-and-Conquer Algorithms

Question 2.24

Explain what is meant by the two recurrences above.

1. base case cost is constant, Q(1)
    
2. problem divided in 1/2 each time, T(n/2).
    
3. cost of problem division and combining results is constant as there is no combining step.

Question 2.25

æ c                                       if n = 1, Base case T(n) = í            è 2T(n/2) + D(n) + C(n)       if n > 1, Recursive case

Explain what is meant by the two recurrences above.

1. base case cost is constant, Q(1)
    
2. problem divided in 1/2 each time, T(n/2). Both halves are sorted, 2T(n/2).
    
3. cost of problem division D(n) and combining results C(n) are no worse than linear. D(n) is in fact constant.

Question 2.26    For n = 16 in Merge-Sort

1. Each recursion divides the problem size by 2. How many divisions before the problem size is 1?    4
2. What is the height of the tree?    4
3. State the height as a function of the problem size, 16.  lg 16 = lg 2⁴
4. How many sub-problems of size 1?  16
5. Each recursion doubles the number of sub-problems. State the number of sub-problems at the bottom of this tree as a function of the problem size, 16, and height.

   16 = 2^{lg 6}