Divide and Conquer Paradigm

Question 1

Describe the three steps that the divide and conquer paradigm divides recursion into

Answer 1

• Divide* the problems into sub problems of the same problem - D(n)
• Conquer* each subproblem. Solve either recursively or not - aT(n)
• Combine* the solutions into an overall solution - C(n)

Question 2

What is recurrence

Answer 2

An equation or inequality that describes a function in terms of ites value on smaller functions

Question 3

what is the recurrence equation of merge sort

Answer 3

c if n = 1

2T(n/2) + cn n>1

Question 4

what is the recurrence equation of factorial

Answer 4

c if n = 1

T(n-1) + c n>1

Question 5

what is the recurrence equation of binary search

Answer 5

c if n = 1

T(n/2) + c n>1

Question 6

describe the substitution method to solve recurrences

Answer 6

make a good guess.

1. guess the form of the answer
2. use induction to find constants
3. show the solution works.

Question 7

describe the iteration method to solve recurrences

Answer 7

1. expand the recurrence
2. work out the algebra to express as a sum
3. evaluate the sum

Question 8

describe the master method to solve recurrences

Answer 8

T(n) = a T(n/b) + f(n)

1. find a b and f(n)
2. calculate n^(log_b a)
3. how does f(n) relate to the above

Question 9

give the three different cases in the master method

Answer 9

O(n^log_b a)                   if f(n) = O(n^(log_b a - constant)) 
O(n^(log_b a) log n)        if f(n) = O(n^log_b a)
O(f(n))                               if f(n) = O(n^(log_b a) + constant))
                                         and af(n/b) <= cf(n)   for large n