1. Prove by induction that 1 1! + 2 2! + + n n! = (n + 1)! 1 for all n 1 (

n N).

1. Given the definition,

s₁ = 1

sn+1 = 1+1sn (n > 1)

prove by induction that FIB(n)

s_n =

FIB(n + 1)

for all n 1 (n N).

1. Suppose you would like to conclude that P(n) is true for all n 0 (n N). For each of the following conditions, determine whether the condition is sufficient to prove this.
2. P(0) and n 1(P(n 1) P(n + 1) P(n + 2)) ii. P(1) and n 0(P(n + 1) P(n) P(n + 2)) iii. P(0) and P(1) and n 1(P(n) P(n + 1) P(n + 2)) iv. P(0) and P(1) and n 1(P(n) P(n + 2))
   1. P(0) and P(1) and n 1(P(n) P(2 n) P(2 n + 1))
   2. P(0) and P(1) and n 1(P(2 n) P(2 n 1) P(2 n + 1))

[show answer]

2. (Recursive definitions)

Recall the recursive definition of a rooted tree:

v; is a tree consisting only of a root node

r;T₁,T₂,,T_k is a tree with root r and subtrees T₁,T₂,,T_k at the root (k 1)

Prove that in any rooted tree, the number of leaves is one more than the number of nodes with a right sibling.

Hint: This assumes a given order among the children of every node from left to right; see slide 22 (week 7) for an instance of this theorem.

[show answer]

3. (Recurrences)

Recall the recurrence for Mergesort:

T(1) = 0

T

Prove that n (log₂ n 1) + 1 is a valid formula for T(n) for all n = 2^k (with k 1).

[show answer]

4. (Asymptotic running times)
   1. Suppose you have the choice between three algorithms:
   2. Algorithm A solves your problem by dividing it into five subproblems of half the size,

recursively solving each subproblem, and then combining the solutions in linear time. ii. Algorithm B solves problems of size n by recursively solving two subproblems of size n 1 and then combining the solutions in constant time.

iii. Algorithm C solves problems of size n by dividing them into nine subproblems of size n , recursively solving each subproblem, and then combining the solutions in O(n2) 3 time.

Estimate the running times of each of these algorithms. Which one would you choose?

1. Order the following functions in increasing asymptotic complexity:
2. (n 1) (n 2) n

3n ii.

• 7_n3+3_n+1

1. 5nlog(log(n))
2. 3nlog(n) + 2n²
3. 8 + log(n) (n 1)

[show answer]

5. (Big-Oh)
   1. Without using the Master Theorem, give tight big-Oh upper bounds for the divide-andconquer recurrence T(1) = 1; T(n) = T( ⁿ₂ ) + g(n), for n > 1, where
   2. g(n) = 1 ii. g(n) = 2n iii. g(n) = n²
   3. For each of the following functions, use the Master Theorem to determine the best upper bound complexity of T(n).
   4. T ii. T iii. T iv. T v. T
      1. Analyse the complexity of the following recursive algorithm to test whether a number x occurs in an unordered list L = [x₁,x₂,,x_n] of size n. Take the cost to be the number of list element comparison operations.

Search(x,L = [x₁,x₂,,x_n]):

if x₁ = x then return yes

else if n > 1 then return Search(x,[x₂,,x_n])

else return no

1. Analyse the complexity of the following recursive algorithm to test whether a number x occurs in an ordered list L = [x₁,x₂,,x_n] of size n. Take the cost to be the number of list element comparison operations.

BinarySearch(x,L = [x₁,x₂,,x_n]):

if n = 0 then return no

else if ^xn > x then return BinarySearch(x,[x₁,,^xn1])

2 2

else if ^xn < x then return BinarySearch(x,[^xn+1,,x_n])

2 2

else return yes

[show answer]

6. Challenge Exercise

Prove by induction that every connected graph G = (V,E) must satisfy e(G) v(G) 1.

Hint: You can use the fact from a previous lecture that _vV deg(v) = 2 e(G).

[show answer]