PAGE UNDERGOING MODIFICATIONS

Sample Exam Problems, CPSC 500-101, Fall 2013

  1. First Week and Chapter 0
    1. Let A : ℕ satisfy
      • A(n)=A(n-1)+A(n-2)+1 for all n>2 .
      Let Let T : ℕ satisfy
      • T(n)=T(n-1)+T(n-2)+Overhead(n), for all n>2 ,
      where Overhead(n) is a function of positive integers n for which
      • Overhead(n) ≥ 1, for all n.
      Use induction on n to show that if
      • T(1) ≥ A(1), and T(2) ≥ A(2),
      then for all n we have
      • T(n) ≥ A(n).
      Explain the relevance of this to computing Fibonacci numbers in a (pretty awful) recursive algorithm, where each function call involves some (presumably polynomial time) overhead, but surely must perform one addition.

    2. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, that for any n>1, f(n-1) and f(n) are relatively prime (you may use the fact that if a and b are integers, then a is relatively prime to b iff b is relatively prime to a+b.

    3. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, that for any n > 1,
      • f(n)f(n)-f(n-1)f(n+1)
      is -1 if n is even, and +1 if n is odd.

    4. Prove by induction on n that
      • 1+4+9+16+...+n^2 = n(n+1)(2n+1)/6.

    5. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, that for any integer n > 1,
      • 2^(n-1) ≥ f(n).

    6. A merge sorting algorithm takes time T(n) given by T(1)=5, and
      • T(n) = 2 T(n/2) + 5n
      (if n is not even we need to use the floor and ceiling functions, but let is ignore this here). Show that if n is a power of two, namly 2^m, then
      • T(n) = 5n (m+1) = 5 n (log(n)+1),
      where the logarithm is base 2.

    7. The Fibonacci numbers are given by f(1)=f(2)=1, and f(n) = f(n-1) + f(n-2) for all n>2. Show, by induction, the exact formula for f(n) in Exercise 0.4 of the text.




  2. Chapter 1
  3. Chapter 2
  4. Etc.
    1. UBC Math Home| Joel Friedman Home| Course Materials