CS 70 Reading Quiz -- Week 3, Sunday

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 ab:

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
Fill in the blank: What is the strongest invariant you can give that will always hold every time execution reaches line 4? (Your answer will be a relationship involving a, z, and i.) You do not need to justify your answer -- just show the invariant.

2. Let F(n) denote the n-th Fibonacci number. Consider the following proof using strong induction:
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.
Suppose that we wanted to convert this to a proof using simple induction, instead of strong induction. What should the inductive hypothesis part of that proof be? (You only need to show the inductive hypothesis; you don't need to give the proof itself.)

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 70 home page