Foundations — Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm)

Before you can read a proof about "finish times" or "value-per-weight" or "sibling leaves at maximum depth", you need to know what each of those pieces is and what it looks like. We build them in order, so that no symbol is used before it is drawn.

0. What is a "problem" here, and what is "optimal"?

The whole game is: out of the huge cloud of feasible solutions, land on an optimal one without checking them all. Greedy tries to do this in one straight sweep.

1. Number line, intervals, and "overlap"

Activity selection lives entirely on a number line — a straight horizontal axis where each point is a moment in time.

Figure s01 (below): two horizontal bars on a labelled time axis. The black bar is activity $i$ running from $s_i=1$ to $f_i=4$; the red bar is activity $j$ running from $s_j=5$ to $f_j=8$. The gap between them (from $4$ to $5$) is the visual proof that they never share a moment — they are compatible.

Look at the figure. Two bars overlap if they share any point of the line at the same time. Two bars are compatible (non-overlapping) if one finishes at or before the other starts — the red bar starts after the black one ends, so they can both be scheduled.

The parent note's line "pick the next activity whose start $\ge$ last picked finish" is nothing more than this single inequality, applied over and over.

2. The symbols $\sum$, $x_i$, and inequalities (knapsack's language)

Now the parent's cryptic line reads in plain English: $\text{maximise }{\sum }_i{x}_i{v}_i\text{subject to}{\sum }_i{x}_i{w}_i\le W,0\le x_i\le 1.$ "Pick fractions of items so the money is as big as possible, but the packed weight never exceeds the bag."

Now that $w_i$, $v_i$, $x_i$ and $W$ all have meaning, we can read a filled bag.

Figure s02 (above): the tall rectangle is the knapsack of capacity $W=50$. It is filled from the bottom by three slabs whose heights are the weights actually packed ($x_i{w}_i$):

• item $A$ taken whole, $x_A=1$: weight $w_A=10$, value $v_A=60$;
• item $B$ taken whole, $x_B=1$: weight $w_B=20$, value $v_B=100$;
• item $C$ taken as a fraction $x_C=\frac{2}{3}$ (red slab): weight used $x_C{w}_C=\frac{2}{3}\cdot 30=20$, value $x_C{v}_C=\frac{2}{3}\cdot 120=80$.

The three packed weights are $10+20+20=50=W$, so the bag is exactly full — the red slab is the "last slot" idea, filling the final gap with a fraction of the next item. The annotation totals the value ${\sum }_i{x}_i{v}_i=60+100+80=240$.

3. Trees, nodes, leaves, and depth (Huffman's world)

Huffman coding is drawn as a binary tree. You must be fluent in tree pictures before the algorithm makes sense.

Figure s03 (above): a small binary tree. The top dot is the root (depth $0$). Every edge is labelled 0 (left) or 1 (right). The two black leaves at the bottom hanging off the same parent are marked as siblings. One leaf is drawn in red at depth $2$; reading the two edge-labels down to it spells its codeword 01. This is the picture that turns "depth" into "number of bits".

4. The min-heap / priority queue

Huffman repeatedly needs "give me the two smallest frequencies right now". Doing that fast needs one data structure.

Why not just re-sort every round? Because after each merge you insert a new combined frequency; a heap absorbs that in $\log n$ time instead of re-sorting from scratch. This is why Huffman's core loop rests on the heap, not on sorting.

5. Sorting and the $O(\cdot )$ symbol

6. The proof tool: the exchange argument

Every correctness proof in the parent note is the same trick, so learn it once.

You will meet three flavours of the same swap:

Activities. First fix an indexing convention: sort all activities by finish time and rename them so that $f_1\le f_2\le \cdots \le f_n$. Under this convention, $a_1$ denotes the activity with the earliest finish time overall (index $1$ after sorting). The swap: in any optimal schedule, replace its earliest finisher with $a_1$. Since $a_1$ finishes no later, everything that fit after the old choice still fits — feasible, same count.

Knapsack. Let $\epsilon$ (Greek "epsilon") be a tiny positive amount of weight — small enough that both items involved still have room to give and take it. Move $\epsilon$ kilograms out of a low-density item $j$ and into a high-density item $i$ (with $d_i>d_j$). Value lost $=\epsilon d_j$; value gained $=\epsilon d_i$; net change $=\epsilon (d_i-d_j)>0$. So the swap strictly improves value, meaning a solution that did not take the densest item first could not have been optimal.

Huffman. Here we must use two different symbols so nothing is overloaded:

(Notice we wrote depth as $\text{dep}(\cdot )$, not $d$: the symbol $d_i$ was already spent on knapsack density in §2, and ${\ell }_i$ is the finished code length — three different ideas, three different names.)

The prerequisite map — read it as a dependency chain

Each arrow below means "you need the left thing to understand the right thing". Read from the raw ideas at the top down into the three greedy problems, which all merge into the parent topic.

• Number line + intervals → gives you the compatibility test $f_i\le s_j$ → which powers Activity Selection.
• Summation $\sum$ and density $v/w$ → both feed Fractional Knapsack.
• Sorting + Big-O → feed the sort-first steps of activity selection and knapsack.
• Min-heap → is what Huffman's core loop actually uses (pull the two smallest frequencies), not a sort.
• Binary tree (depth, leaves, siblings) + prefix-free code → feed Huffman Coding.
• The exchange argument → is the correctness proof shared by all three problems.
• Activity Selection + Fractional Knapsack + Huffman Coding → together are the parent greedy topic.

Here is the same chain as a diagram (each box is one foundation, arrows point toward what it unlocks):

This whole map feeds the parent greedy topic. Two other places reuse these pieces: Minimum Spanning Tree (Kruskal/Prim) (greedy + exchange again) and Dynamic Programming (what you fall back on when greedy fails, as in 0/1 knapsack).

Equipment checklist

Close the page and answer each; if you stumble, reread its section.