[SOLVED] COMP9020-Set 6 Induction, Recursion and Complexity Analysis

Description

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

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.

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

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−_n−₃−+−−3−_n−+−−1

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

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 ^x_⌈n⌉ > x then return BinarySearch(x,[x₁,…,^x_⌈n⌉−1])

2                                                                                                                                                  2

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

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