Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

SID: [No spaces and no dashes.]

Login ID :

1. Consider the following program for computing a^{b}:

function Pow(a, b): 1. Set z := 1 2. For i := 1,2,..,b, do: 3. Set z := z*a 4. Invariant: ___________ 5. return z

Theorem: For every natural number n, F(n) ≥ 0. Proof: The proof will be by strong induction on n. Let P(n) be the proposition that F(n) ≥ 0. Base cases: 0=F(0) ≥ 0, so P(0) is true. Also 1=F(1) ≥ 0, so P(1) is true. Inductive hypothesis: Let n >= 2. Suppose that P(0), P(1), ..., and P(n) are all true, i.e., F(k) ≥ 0 holds for all k with 0 ≤ k ≤ n. Inductive step: We have F(n+1) = F(n) + F(n-1) ≥ 0 + 0 = 0 (applying the inductive hypothesis twice). Therefore F(n+1) ≥ 0, so P(n+1) is true. By the principle of induction, the theorem follows.