Due in lecture, Thursday April 18. Please do the homework in a workbook.

From the Text

Complete the following questions from the text:

Section 3.6: 10, 12, 26
- Question 10: using the algorithm described in lecture.
- Question 12: no need for a “proof”, but give an explanation of why it works.
- Question 26: calculating mod counts as a division.
Section 4.1: 4, 22
Section 4.2: 10, 26, 30
Section 4.3: 26(c)
Section 4.4: 44
- Show enough steps to convince us you know what was happening. You don't need to show every single variable change. Draw the steps in whatever way makes the most sense to you.

Questions

Prove by induction that \(6\mid n^3-n\) for all \(n\ge 0\). [Hint: look at \(n-2\) or \(n+2\).]
This recursive algorithm computes \(a^b\) where \(b\) is a positive integer:
```
procedure power(a, b)
    if b=0
        return 1
    else
        return a * power(a, b-1)
```
What is the big-Θ running time of this algorithm?
Give an algorithm that solves the same problem as the one in the previous question, but runs in \(\Theta(\log b)\).