COMPSCI320 Chap.4 Greedy Algorithms and Exchange Arguments
Greedy Algorithms and Exchange Arguments
Greedy algorithms take one irrevocable choice at a time, and the course judges them by their proofs.
This chapter proves earliest-finish-time interval scheduling optimal by staying ahead, proves shortest-first file ordering optimal by an exchange of adjacent files, and shows how to break a wrong greedy rule with a concrete instance, the greedy output and a strictly better solution.
The worked examples use new job lists and file lengths, and the practice cards ask for counterexamples to rules that look reasonable, such as the largest coin first or the shortest job first.
The chapter closes with the interval problems of the second programming assignment and the edge cases a closed-interval convention creates.
What this chapter covers
- 01
Interval scheduling by earliest finish time
- 02
The greedy stays ahead induction
- 03
Exchange arguments with adjacent swaps
- 04
Building a counterexample to a greedy rule
- 05
Coin change and knapsack traps
- 06
Interval problems in the second assignment
Worked example · free
Schedule the most jobs by earliest finish time
- 1Sort by finish time: b 4, c 5, a 6, d 7, e 9, f 10, g 11.
- 1Take b, skip c and a, take d at 4, skip e and f, take g at 8.
- 1Greedy's k-th finish time is never later than any other schedule's k-th finish time.
- 1A longer schedule would leave room for greedy to add a job, so three jobs is optimal.
Key terms
- Greedy Algorithm
- An algorithm that builds a solution by repeatedly making the locally best choice under one fixed rule.
- Exchange Argument
- A proof that transforms any optimal solution into the greedy one step by step without making it worse.
- Interval Scheduling
- The problem of choosing the largest set of jobs whose time intervals do not overlap.
- Counterexample
- A specific instance on which a proposed rule produces a result that a strictly better solution beats.
- Earliest Finish Rule
- The greedy choice of the compatible job that finishes first, which maximises the number of scheduled jobs.
- Stays-Ahead Argument
- A proof that after every step the greedy solution is at least as good as any other solution under a chosen measure.
Greedy Algorithms and Exchange Arguments FAQ
What must a greedy counterexample contain to earn full marks?
It needs a specific instance, the solution the greedy rule actually produces on it with its value, and a strictly better feasible solution with its value. A sentence saying the rule can fail earns nothing. Small instances work best because the marker can verify each solution at a glance, and one line explaining why greedy missed the better answer completes it.
When should I use stays ahead rather than an exchange argument?
Stays ahead suits problems where both solutions are built in a natural order, so you can compare their first k choices, as with interval scheduling or the frog crossing lily pads. An exchange argument suits problems where any optimal solution can be rearranged, such as ordering files on a tape, by swapping adjacent elements that are out of the greedy order.
Why does shortest duration first fail for interval scheduling?
A short job can overlap two longer jobs that are compatible with each other. With jobs from 0 to 5, 6 to 10 and 4 to 7, the shortest one overlaps both of the others, so the rule schedules only one job while two are possible. Earliest finish time avoids this by leaving the most room for later jobs.
Are greedy algorithms ever optimal for coin change?
For many real coin systems the largest coin first rule gives the fewest coins, but not for every system. With coins of 1, 5, 6 and 9, the amount 11 needs three coins under the rule but only two as 5 plus 6. Because correctness depends on the denominations, a proof or a counterexample is always required.
Exam move
For each greedy rule you meet, spend two minutes trying to break it with a three-item instance before trying to prove it. Write one stays-ahead proof and one exchange proof in full, labelling the measure or the swap and the inequality it gives. Keep a list of standard traps, such as coin systems and ratio-based knapsack choices, with a counterexample for each.
When revising, sort your counterexamples by the greedy rule they break, so in the exam you can reach for a ready-made instance and adjust its numbers. Add one interval edge case to your notes each time you meet it, such as touching endpoints or identical intervals.
Working through Greedy Algorithms and Exchange Arguments in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Greedy Algorithms and Exchange Arguments question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
