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.
What a strong answer looks like
A strong Unit 8 answer names the strategy, states the property that justifies it, and does not claim greedy optimality without an argument.
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.
Study move
Find an input where a plausible greedy rule fails, and explain why.
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.
Study move
Define state and recurrence for a simple knapsack before implementing anything.
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.
Study move
Place N queens and state the earliest conflict check that prunes effectively.
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.
Study move
Name two NP-complete problems and say what you would do on meeting one in practice.
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.
