
PAGE UNDERGOING MODIFICATIONS
Sample Exam Problems, CPSC 500101, Fall 2013
 First Week and Chapter 0

Let A :
ℕ
→
ℕ
satisfy
 A(n)=A(n1)+A(n2)+1 for all n>2 .
Let
Let T :
ℕ
→
ℕ
satisfy
 T(n)=T(n1)+T(n2)+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
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.

The Fibonacci numbers are given by f(1)=f(2)=1, and
f(n) = f(n1) + f(n2) for all n>2.
Show, by induction, that for any n>1, f(n1) 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.

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

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

The Fibonacci numbers are given by f(1)=f(2)=1, and
f(n) = f(n1) + f(n2) for all n>2.
Show, by induction, that for any integer n > 1,

A merge sorting algorithm takes time T(n) given by T(1)=5, and
(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.

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



 Chapter 1
 Chapter 2
 Etc.
