Hw07: Structural Induction, Program Correctness

Due 04.Mar.23 (Tue) 17:00

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

Reading: Rosen Review 3.5 (recursive algorithms), 2.5 (just the first part, "representations of integers")

1. (5pts) Rosen 3.4, #36 (p.272) 4ed -- p.210 #28 (string-reversal).
   Be sure to read the paragraph preceding the problem, and the solution for #35.
2. (4pts) Rosen 3.4, #44 (p.272) 4ed -- does not exist (leaf-counting)
   Be sure to read the paragraph preceding the problem.
3. (2pts) Convert the following binary numerals into numbers (express your answers using conventional base-10 numerals). Observe how each numeral relates to the one before it.
   1. [ 1101 ]₂
   2. [ 11010 ]₂
   3. [ 110101 ]₂
4. (1pt) Section 2.5, #6 (p. 179). 4ed -- let me know ([BADFACED]₁₆ into binary.)
   (See Rosen's Example 6.)
5. (5pts) Section 2.5, #12.
   
   • Explicitly give the translation algorithm hex->bin (abbreviation: h2b), which converts numerals.
     Be sure to give the header/contract (that is, mention your data-represention of numerals).
   • You can take as given, a correct function hexdig->bindigs which translates individual digits, returning a list of exactly four binary digits ("bits"). (Abbreviation: hd2bds.)
   • Then show that for any hex numeral h, the number it represents is the same as the number represented by the binary numeral hex->bin(h).
   • Clearly state what form of proof you use.
   • Compared to Rosen's answer for #11, your answer should more clearly state the algorithm, clearly distinguish between numerals and numbers, and not be riddled full of ``...''.
6. (5pts) Prove that the following algorithm computes xn:

   ;; pow: real, natnum --> real
   ;; Return xn.
   ;;
   (define (pow x n)
     (cond [(zero? n) 1]
           [(even? n)      (sqr (pow x (quotient n 2)))]
           [(odd?  n) (* x (sqr (pow x (quotient n 2))))]
   

   Be sure to clearly state which proof method you are using.

   sqr is a function which squares its input. You may take as given, that (quotient n 2) returns n/2 if n even, and (n-1)/2 if n odd.

   The above procedure is called "repeated squaring", and is based on the fact that to compute (for example) 504^18, you don't need to do 18 multiplications, but rather just compute (504^9)^2. In turn, 504^9 can be computed by observing 504^9 = 504^8*504 = (504^4)^2*504. (Work through a couple of test cases, so that you internalize your understanding of why the algorithm works.)

   Next week's homework will visit an iterative version of this same algorithm.

7. Extra credit (4pts): Rosen's Section 3.3, Example 12 described the Batch Scheduling Problem, gave a greedy algorithm, and proved (by mathematical induction) that the algorithm produces an optimal schedule.

   Consider a slightly different greedy algorithm, which doesn't necessarily schedule the job with the earliest end-time, but instead schedules the job with the largest begin-time. Show by strong induction on the input size, that this algorithm is also correct.

   (The kernel of the proof is unchanged, but between the slight variant and needing to re-phrase the proof goal amenable to inducting on input-size, a solution here shows understanding of the interesting original argument. By reflecting on which parts of Rosen's explanation were hardest for you to internalize, feel free to give a better write-up than the book!)

[an error occurred while processing this directive] [an error occurred while processing this directive]