Unit 8 · Culminating
Choosing a strategy rather than a structure. The central discrimination is when a greedy choice is provably safe and when overlapping subproblems force a table instead.
Know
A greedy algorithm commits to a local choice and never reconsiders, which is only valid given a greedy-choice property and optimal substructure.
Apply
Before choosing greedy, argue why the local choice cannot preclude a better global one.
Watch out
Assuming greedy works because it works on the examples tried. Fractional knapsack is greedy-solvable; 0/1 is not.
Know
Dynamic programming applies when subproblems overlap and the problem has optimal substructure. Memoization caches on demand; tabulation fills in dependency order.
Apply
Define the state, the recurrence, and the base case before writing any code.
Watch out
Writing the recursion without defining the state precisely, which produces a table nobody can index correctly.
Know
Backtracking builds a partial solution and abandons it as soon as it cannot be completed, pruning entire subtrees of the search space.
Apply
Identify the earliest point at which a partial assignment becomes impossible, and prune there.
Watch out
Pruning only at the leaves, which reduces backtracking to exhaustive enumeration.
Know
P is solvable in polynomial time; NP is verifiable in polynomial time. NP-complete problems are in NP and at least as hard as everything in it.
Apply
Recognise a known NP-complete shape and pivot to approximation or heuristics rather than seeking an exact fast solution.
Watch out
Treating NP-complete as proven impossible. No polynomial algorithm is known, and none has been proved not to exist.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
For a scheduling problem with weighted jobs, decide between greedy and dynamic programming, and justify the choice with the property that settles it.
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic