Homework #5

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

From the Text

Complete the following questions from the text:


  1. 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
  2. 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?

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