Problem-solving recipes
A step-by-step procedure for every problem type this course teaches — what to do first, what to do next, and how to tell which case you're in.
What are you being asked to do?
Start with what kind of problem you're facing.
A naive count double- (or multiply-) counts each real outcome the same number of times — divide out the uniform overcount.
Lattice paths that never cross a diagonal, balanced parentheses, or binary tree shapes, and you need the count for a given size — the Catalan number formula.
A specific coefficient in an expanded (a+b)^n or (x_1+\cdots+x_m)^n, without expanding the whole thing — the binomial or multinomial extraction recipe, matching how many variables are actually summed.
A linear recurrence whose characteristic equation has a repeated root — the repeated-root recipe; a distinct-root recurrence is solved directly from the characteristic equation without this extra step.
A divide-and-conquer algorithm's running time, or its growth rate — read off a, b, f(n) first; the master theorem then gives the growth rate directly from those same three numbers.
A partition count p(n) too large to recall, small enough to list — split by largest part.
Binomial and multinomial coefficients
Extract one term from a multinomial expansion
Use when: you need the coefficient of one specific term in an expanded (x_1+\cdots+x_m)^n, without expanding the whole thing
Goal: the correct multinomial coefficient for the requested term
The multinomial theorem
The same idea as the binomial recipe above, generalized to any number of variables.
Solving recurrences with a repeated root
Divide-and-conquer recurrences
Apply the master theorem
Use when: you have a, b, and f(n)=\Theta(n^d) for a divide-and-conquer recurrence, and need its growth rate without building a recursion tree
Goal: the correct \Theta bound on T(n), by comparing the work exponent d to the critical exponent \log_b a
The master theorem
Extends the recipe above with the growth-rate comparison, once a, b, and f(n) are already in hand.