Due in lecture, ~~Thursday April 4~~Monday April 8. Please do the homework in a workbook.

# From the Text

Complete the following questions from the text:

- Section 3.1: 6, 24.
- Describe in pseudocode.

- Section 3.2: 18, 24.
- You're free to use the theorem in question 27 (without proving it) if you like.

- Section 3.3: 8.
- Compare answer to question 7(b): \(2n\) multiplications and \(n\) additions.

- Section 3.4: 8, 12.

# Questions

- What is the big-Θ running time of this algorithm? Assume the input list has \(n\) elements.
procedure print_things(list): end = length(list) while end > 1 total = 0 for i from 0 to end-1 total += list[i] print total end -= 1

- The following algorithm computes \(a^b\) for \(b\) a natural number:
procedure power(a, b) result = 1 for i from 1 to b: result *= a return result

What is the (big-Θ) running time of this algorithm?

- Prove from the definition that \(f(x)=x^3 + 12x\log x\) is \(O(x^3)\).
- Prove using theorems mentioned in lecture that \(f(x)=x^3 + 12x\log x\) is \(O(x^3)\).
- Prove that if \(n\) is an odd positive integer, then \(n^2\mathop{\mathbf{mod}}8=1\).