Ch4: Divide and Conquer

Question 1

For the substitution method of solving recurrences, what technique can you try if you hit a snag in the math?

Answer 1

Revise the guess by subtracting a lower-order term (this will be <= what you try to prove, therefore T(n) <= new guess <= desired guess implies T(n) = O(desired))

Question 2

3 steps of divide and conquer

Answer 2

DIVIDE the problem into subproblems that are smaller instances of the same problem, CONQUER the subproblems by solving them recursively (or trivially), COMBINE the subproblem solutions into the solution for the original problem

Question 3

Case when subproblems are large enough to solve recursively

Answer 3

Recursive case

Question 4

Case when subproblems are small enough to no longer recurse

Answer 4

Base case

Question 5

Recurrence

Answer 5

An equation or inequality that describes a function in terms of its value on smaller inputs

Question 6

3 methods of solving recurrences

Answer 6

Substitution method, recursion-tree method, master method

Question 7

When we state and solve recurrences, we often omit…

Answer 7

floors, ceilings, and boundary conditions (assuming the latter are O(1))

Question 8

Steps for the substitution method

Answer 8

1) Guess the form of the solution (we do this sometimes w/ output of recursion-tree method!) 2) Use mathematical induction to find the constants and show that the solution works

Question 9

In a recursion tree, each node represents…

Answer 9

the cost of a single subproblem somewhere in the set of recursive function calls

Question 10

Using the recursion tree method, we get the total T(n) by…

Answer 10

Summing the cost at each level, then summing all the level costs to get the total cost T(n)

Question 11

A recursion tree is best used to…

Answer 11

generate a good guess which you can then verify using the substitution method

Question 12

You can use a recursion tree as a direct proof of a solution to a recurrence if…

Answer 12

you are very careful when drawing out the recursion tree and summing the costs

Question 13

How do you determine the recursion tree height (h) in terms of n?

Answer 13

Create an equation describing the subproblem size at a level i in terms of n: n[i] = f(n, i). Then solve the equation for the level i when the subproblem size = 1 (at the leaves of the tree). This is the tree height h

Question 14

What is the key trick to solving an “unbalanced” recursion tree - one where the subproblems do not have equal sizes?

Answer 14

Determine which subproblem size leads you down the longest simple path from the root node to a leaf (the biggest subproblem). Since the tree is not complete, this longest tree height is an upper bound we can use, since we know the actual total cost will be smaller than that of a complete tree