Hw08: Program Correctness (iteration), big-Oh

Due 04.Mar.30 (Tue) 17:00. Will be accepted until Apr.01 (Thu) 17:00 w/o penalty, though hw09 goes out on Mar.30 (Tue) as usual.

Before you tackle the homework, remind yourself of our general hw policies (includes proof-by-induction tips).

Reading: Rosen 3.6 (program correctness for imperative languages), 2.2 (growth of functions), 2.3 (time-complexity of algorithms)

1. (5pts) Section 3.6, #12 (p. 290).
   Be sure to clearly state your loop invariant, and show the four parts of the proof obligation as mentioned in lecture.
   Quick re-cap of how reading relates to lectures [from newsgroup].

2. (6pts) Here is an iterative program for repeated-squaring (roughly similar to the recursive formulation from last week, but in a bottom-up way).

   // pow: return xn,
   // where x is any number, n ≥ 0, 
   // and if x=0,n=0 we return 1
   // even though NaN is the mathematically correct answer.
   //
   rational pow( rational x, natnum n) {
     rational soFar     ← 1
     natnum   restOfN   ← n    
     rational xToTwoToI ← x    // This will be x^(2^i), where i is number of times through loop.
   
     // LoopInvariant: x^n = (xToTwoToI ^ restOfN) * soFar, and …?
     while (restOfN > 0) {
       if odd?(restOfN)  soFar ← soFar * xToTwoToI
       restOfN   ← quotient(restOfN, 2)
       xToTwoToI ← xToTwoToI * xToTwoToI   // Repeatedly square.
       }
   
     return soFar
     }
   

   Using the loop invariant as stated in the code, show the four parts of the proof obligation for the loop. (You may need to tweak add a detail to the invariant, to get your proof to go through.)

   You can assume that your programming language is high-level enough to do arithmetic at the fourth-grade level (add and multiply rationals without round-off or overflow error). As last time, be sure to get a feel for what the algorithm is doing, presumably by working through some test cases.

3. (4pts) In the definition of big-Oh, give particular values of c,n₀ (Rosen: "C,k") which witness:
   1. 17log(n)+19 is O(log n);
   2. n²log(n) is O(n³);
   3. n³+2 is O(n¹⁷).
4. (2pts) Section 2.2, #8 (p.142). (4ed: p.90 #8.) Polynomial upper bounds.
5. (4pts) Section 2.2, #12 (p.142). (4ed: p.90 #12.) x² vs x log(x).
6. (3pts) Section 2.2, #20a. (p.143). (4ed: p.91 #20a.) Simplify big-Oh. Recall your answer previous problems.
7. (2pts) Section 2.3, #12a,b. (p. 152). (4ed: p.112, #12a,b) Some best-case performances.

8. (4pts) You have accepted a job at the startup KaZoo, whose rad new product automatically creates random re-mixes from your music collection and shares them with any buddy who has ever visited a web page owned by one of your friendsters, all the while searching for extra-terrestial life .

   Their current version works, but unfortunately is too slow: because of all the network traffic it generates, the program becomes bogged down after only 10 buddies. (It is the amount of network traffic that dominates the running time -- the local processing time is negligible.) "Unacceptable!" your boss cries. "We need to support at least 500 buddies!"

   Indeed, you work day and night, and a month later report to your overjoyed boss, that you have cut the amount of generated network traffic by an impressive factor of 64. (Or equivalently -- network technology/capacity improved 64x over the course of the month.) Your boss is overjoyed, and marketing promptly announces "Now, supports 64 times as many buddies!"

   You're not so sure about Marketing's new claim, though. You think of the function netTraffic_KaZoo(), which takes in the #buddies, and returns the amount of net traffic generated by the original version of KaZoo. Thus, the number netTraffic_KaZoo(10) is a benchmark to compare new performance against.

   What should Marketing's ``such-and-such times as many buddies'' claim actually now be?, presuming that the original underlying function netTraffic_KaZoo was:

   1. netTraffic_KaZoo(b) = log₂b (You may want to defer this arithmetic to last)
   2. netTraffic_KaZoo(b) = b
   3. netTraffic_KaZoo(b) = b²
   4. netTraffic_KaZoo(b) = b³
   5. netTraffic_KaZoo(b) = 2^b
   What do you say to your (intelligent) boss, to explain in lay terms why a 64-fold speed improvement may not mean a 64-fold number-of-buddies improvement?