Algorithms · topic
Greedy choice and optimal substructure with exchange arguments; activity selection, fractional knapsack, job sequencing with deadlines, Huffman coding with average code length, optimal merge pattern, and counterexamples where greedy fails.
A greedy algorithm builds a solution one choice at a time. At every step it picks the option that looks best right now, never undoing that choice later. The hope is that a sequence of locally optimal choices produces a globally optimal answer.
Huffman coding builds an optimal prefix code for a set of symbols with known frequencies: no codeword is a prefix of another, so a bit stream decodes uniquely without separators, and the expected codeword length is minimised among all binary prefix codes.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
