Homework #6

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

From the Text

Complete the following questions from the text:


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