COMP9020-Set 6 Induction, Recursion, Complexity Analysis Solved

1. (Induction proofs)

a. Prove by induction that 1 ⋅ 1! + 2 ⋅ 2! + … + n ⋅ n! =

b. Given the definition,

s1 = 1 sn+1 =
prove by induction that

sn =

for all n ≥ 1 (n ∈ N).

(n + 1)! − 1 for all n ≥ 1 (n ∈ N).

    1         (n 1)
1+sn

FIB(n)

 

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.

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))

v.   P(0) and P(1) and ∀n ≥ 1(P(n) ⇒ P(2 ⋅ n) ∧ P(2 ⋅ n + 1))

vi.  P(0) and P(1) and ∀n ≥ 1(P(2 ⋅ n) ⇒ P(2 ⋅ n − 1) ∧ P(2 ⋅ n + 1))

[

 
FIB(n + 1)

2. (Recursive definitions)

Recall the recursive definition of a rooted tree:

⟨v; ⟩     is a tree consisting only of a root node ⟨r;T1,T2,…,Tk⟩⟩ is a tree with root r and subtrees T1,T2,…,Tk 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 

3. (Recurrences)

Recall the recurrence for Mergesort:

 T(1) = 0

T(n) = 2T( n2 ) + (n − 1)
Prove that n ⋅ (log2 n − 1) + 1 is a valid formula for T(n) for all n = 2k (with k ≥ 1).

4. (Asymptotic running times)

a.  Suppose you have the choice between three algorithms:

i.    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 n3 , recursively solving each subproblem, and then combining the solutions in O(n2) time.

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

b.  Order the following functions in increasing asymptotic complexity:

i. (n − 1) ⋅ (n − 2) ⋅ √n−
3n ii. 

 

iii.   √−7−n−3−+−−3−n−+−−1

iv.  5nlog(log(n))

v.    3nlog(n) + 2n2

vi. 8 + log(n) ⋅ (n − 1)
[hide answer]

5. (Big-Oh)

a. Without using the Master Theorem, give tight big-Oh upper bounds for the divide-and-conquer recurrence T(1) = 1; T(n) = T( n2 ) + g(n), for n 1, where

i. g(n) = 1 ii. g(n) = 2n iii. g(n) = n2
b.  For each of the following functions, use the Master Theorem to determine the best upper bound complexity of T(n). i. T  ii. T  iii. T  iv. T  v. T 

c.  Analyse the complexity of the following recursive algorithm to test whether a number x occurs in an unordered list L = [x1,x2,…,xn] of size n. Take the cost to be the number of list element comparison operations.

  Search(x,L = [x1,x2,…,xn]):

      if x1 = x then return yes

      else if n 1 then return Search(x,[x2,…,xn])

      else return no

d.  Analyse the complexity of the following recursive algorithm to test whether a number x occurs in an ordered list L = [x1,x2,…,xn] of size n. Take the cost to be the number of list element comparison operations.

  BinarySearch(x,L = [x1,x2,…,xn]):

      if n = 0 then return no

      else if x⌈n⌉ x then return BinarySearch(x,[x1,…,x⌈n⌉−1])

                                            2                                                                                                                                                                           2

      else if x⌈n⌉ < x then return BinarySearch(x,[x⌈n⌉+1,…,xn])

                                            2                                                                                                                                             2

      else return yes

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 ∑v∈V deg(v) = 2 ⋅ e(G).