COMP9123 — Week 10
Foundations & proof moves
Week 10 foundations are really proof foundations. The technical core of the week is learning when exchange arguments work, how to build sharp counterexamples, how interval depth gives a lower bound, and why Huffman's weighted path-length objective matches its merge rule.
Exchange Arguments: Show an Optimum Can Be Reshaped to Match Greedy
The standard greedy proof is not usually “the greedy solution is obviously best.” It is: take any optimal solution that disagrees with the greedy choice, modify it locally so it agrees, and show the objective does not get worse.
Assume an optimal solution differs from the greedy one at the first disagreement. Swap in the greedy choice, preserve feasibility, and prove total objective value stays at least as good. Repeating this eventually transforms some optimum into the greedy solution.
This is exactly the logic behind the lecture's fractional-knapsack proof and the tutorial's weighted scheduling problem, where an adjacent swap tells you which local order is safe.
Counterexamples: The Fastest Way to Reject a Bad Rule
A counterexample is not just “an input where the algorithm does something odd.” It is a smallest clear witness that the greedy rule's local preference can block a better global outcome.
Make the wrong move tempting
Give one option exactly the feature the bad rule values most.
Hide a better combination
Arrange the remaining options so that the greedy first move blocks a stronger overall solution.
Keep it tiny
A three- or four-item instance is usually better than a huge one because the failure mode stays visible.
The tutorial's “infinite classes where a wrong rule still works” is a great caution: many supporting examples do not prove correctness, because the one instance that fails is enough to destroy the theorem.
Interval Depth: Why the Classroom Lower Bound Is Immediate
The interval-partitioning lecture introduces a very clean lower bound. If some time point lies inside \(d\) open intervals, then any valid schedule needs at least \(d\) classrooms, because those \(d\) lectures overlap and cannot share a room.
The depth of a set of intervals is the maximum number of intervals containing any one time. This is a lower bound on the number of classrooms required.
The lecture's optimality proof for interval partitioning says the greedy algorithm never uses more classrooms than this lower bound forces. Once it matches the depth, the proof is done.
Weighted Scheduling: Adjacent Swaps Reveal the Right Ratio
The tutorial's weighted completion-time problem is a classic place where exchange arguments become algebra. You compare two jobs in the wrong order, swap them, and inspect how the weighted objective changes.
For two adjacent jobs \(i\) and \(j\), compare the cost of ordering \(i\) before \(j\) versus \(j\) before \(i\). The sign of that difference reveals which local ordering is globally preferable, leading to a sorting rule by the appropriate ratio.
The tutorial writes the ratio as \(t_j / w_j\), but it is the same priority idea you may know as Smith's rule: jobs with smaller processing-time-to-weight ratio should go earlier.
Huffman Objective: Weighted Path Length Is Why the Merge Rule Works
Huffman coding is not optimizing tree height. It is optimizing weighted external path length: frequent symbols should be shallow because every extra level charges their frequency again.
Minimize \(\sum_{c \in C} f(c)\cdot depth_T(c)\). Every extra bit in the codeword for \(c\) costs \(f(c)\) more total bits in the encoded text.
In an optimal prefix tree, the deepest sibling leaves can be assigned to the least frequent symbols.
Merge that sibling pair into one contracted symbol whose frequency is the sum of the two.
Solve the smaller contracted problem optimally, then expand the merged symbol back into the sibling pair. This gives an optimal full tree.
How to review this page well
The three quick checks are anchored to the core proof habits: exchange arguments, interval depth, and Huffman's weighted objective. If one feels weak, redraw the smallest relevant example and narrate the proof move out loud.
Tutorial review
Open the tutorial after the study guide. Week 10 works best when you already know which rule you are trying to prove or disprove before you look at the instance.
Week 10 checklist. You should be able to state the generic greedy template, build a tiny counterexample to a bad local rule, explain why ratio ordering solves fractional knapsack, justify interval partitioning with the depth lower bound, derive the right weighted scheduling order from an adjacent swap, and describe Huffman's merge step using weighted path length rather than vague intuition.