Algorithm Design
Some problems fight back. A fixed rule can have a carefully arranged worst case, and an exact search can grow beyond any practical budget. This course develops several responses: randomise the exposed choice, prove a useful approximation, model the task as flow or linear programming, prune an exact search, isolate a small parameter, and return evidence that lets someone else check the answer.
Nothing here is quoted from a table. Every count, every average, every rate of being wrong is produced by code running in front of you while you watch, on the data you chose. When a widget says a method was wrong 3.1 percent of the time, it ran the trials and counted.
The course Introduction to Algorithms comes before this one. From it you need: counting steps rather than timing them, what O(n) and O(n²) mean as shapes, sorting, and walking a graph. Each idea is taught in one step there, so you can fetch just the piece you are missing. Counting operations instead of reading a clock is Step 1 there. The halving count written log n is Step 3. The pivot and the partition inside quicksort are Step 6. Breadth-first search, which finds every place reachable from a starting point and gets to each by the fewest hops, is Step 9. O(n) and O(n²) as names for growth shapes are Step 13. Everything else is introduced here, including every word that might be new. No maths beyond arithmetic, fractions and percentages is assumed.
The steps
Find the median without sorting the list
Here is a task that sounds easy. You have a list of numbers and you want the median: the value that would sit in the middle if the list were sorted. Not the biggest, not the smallest, the middle one. You could sort the whole list and look at the middle. That works, and it does far more work than the question needs, because you asked for one number and sorting delivers all of them in order. Work here means a count of operations, never seconds on a clock. The unit in this step is one comparison of two values. A count is used rather than a stopwatch because a count comes out the same on every machine.
There is a faster way, and it is the sorting method you already met, quicksort, stopped halfway. Pick one value from the list and call it the pivot. Walk the list once and throw every value into one of two piles: smaller than the pivot on the left, bigger on the right. That single pass is called a partition. Now count the left pile. If the middle position you want falls inside the left pile, the right pile can be thrown away entirely. You repeat on what is left.
What is quicksort? I have never met it
Quicksort puts a whole list in order using that partition step and nothing else. Pick a pivot and partition the list around it. The pivot is now sitting in its final place, with everything smaller to its left and everything bigger to its right, so it never has to move again. Then do the same to the left pile and to the right pile, and keep going until the piles hold one value each.
The method in this step is quicksort with one change. It partitions, works out which of the two piles holds the position it is hunting for, and follows only that pile. The other pile is thrown away unsorted, which is why the answer arrives so much sooner than a full sort.
What a list is, and what "position 4" means
A list, also called an array, is a row of values kept in order, one after another, so that each has a position. The positions are counted from 0 in almost all programming, so the first value sits at position 0, the second at position 1, and so on. That position number is called an index. Asking for "the value at index 4" means the fifth one along.
Counting from 0 looks like a mistake for about a week and then stops bothering you. It exists because an index is really a distance: index 4 means "four steps past the start", and the first value is zero steps past the start.
What "the k-th smallest" means, and why the median is a case of it
Line the values up smallest to largest. The 1st smallest is the minimum. The 2nd smallest is the next one along. The k-th smallest is whatever lands in position k of that line-up. The median is the k-th smallest where k is halfway, so in a list of 99 values the median is the 50th smallest.
The method in this step answers the general question,"give me the k-th smallest", and the median is just one choice of k. It has a name: quickselect, because it is quicksort that only follows one of the two halves.
Everything now depends on which value you choose as the pivot. Choose well and each round throws away about half the list, so the total work adds up to roughly one and a bit passes over the data. Choose badly, so the pivot is the smallest value every time, and each round throws away exactly one value, which means n rounds over a shrinking list, which is the shape of a sort again. Here and throughout, n means how many values there are.
Where does a computer get randomness from
A computer does not really flip coins. It runs a small piece of arithmetic that turns one number into another in a scrambled-looking way, then uses that as the next "random" number, then scrambles again. The numbers that come out pass every everyday test for being unpredictable, and the whole sequence is decided by one starting number called the seed. This is called a pseudorandom generator, where pseudo just means "acting like".
That has a useful side effect used all over this course: give it the same seed and you get the same sequence, so a run can be repeated exactly. The widgets here take a seed so that "run it again and see" means something, and so that a surprising result can be shown to someone else.
Why the adversary cannot beat a coin flip
Think of it as a game with two moves. With a fixed rule, you move first by publishing the rule, and the adversary moves second knowing everything. Second player wins.
With a random pivot, the adversary still moves second on the arrangement, but the arrangement no longer decides anything, because the pivot is chosen after the input is fixed and by a process the arrangement cannot touch. Every arrangement becomes equally fine. That is the whole trick, and it is worth saying plainly: the randomness is not there to make the method faster on nice inputs, it is there to remove the idea of a nasty input.
So randomised quickselect has no bad input. It still has bad luck: it is perfectly possible to flip badly ten times in a row. What we can say is what happens on average, and the average is a real measurable thing, not a hope. Run the same list many times with different coin flips, keep a running average of the comparisons used, and watch where it settles.
What an average is here, and why a running one is worth watching
An average of some numbers is their total divided by how many there are. Five runs costing 10, 12, 9, 14 and 15 comparisons average to 60 divided by 5, which is 12.
A running average is that same sum kept up to date as each new run finishes, so after run 1 it is that run, after run 2 it is the mean of two, and so on. Early on it jumps about, because one unlucky run moves it a lot. Later each new run is one voice among hundreds and the line goes flat. Watching it go flat is watching an average stop being a guess.
Check two huge files match, and choose your own odds
Two files are supposed to be identical copies. Checking properly means reading both from end to end. If they are a billion characters long, that is a billion comparisons, and you may want an answer sooner than that.
So do something that looks lazy. Pick one position at random and compare just that one character. If they differ there, you have proof: the files are different, and you are finished. If they match there, you have learned almost nothing, so pick another random position and try again.
What a probability is, and how to read"1 in 1000"
A probability is a way of saying how often something happens out of all the times it could. It is written either as a fraction between 0 and 1, or as a percentage, or as"1 in something". A probability of 0.25 is the same as 25 percent and the same as 1 in 4: do it four times and expect it about once.
Small probabilities are easiest to read in the"1 in something" form. A miss chance of 0.001 is 1 in 1000. If a check with that miss chance runs every second, it slips up about once every seventeen minutes. If the miss chance is 1 in a billion, it slips up about once every thirty years. The number only means something once you say how often you are going to ask.
Multiplying a chance by itself, and what a power is
If two things are unrelated, the chance of both happening is the two chances multiplied. One coin landing heads is 1 in 2. Two coins both heads is 1/2 × 1/2, which is 1 in 4. Ten coins all heads is 1/2 multiplied by itself ten times, which is 1 in 1024.
Writing"1/2 multiplied by itself ten times" gets tiring, so it is written 0.510, said as "nought point five to the power ten". The small raised number counts how many copies are being multiplied together, and that is all a power is. The important behaviour: each extra copy halves the result, so ten more probes do not make the miss chance a bit smaller, they make it about a thousand times smaller.
This test has a lopsided kind of honesty, and the shape of it turns up again and again. When it says "different", it is never wrong, because it is holding two characters that disagree. When it says "same", it might be wrong. Errors only go one way, which is called one-sided error. It is what makes such a cheap test usable: you know exactly which of the two answers you are allowed to doubt.
Why measured and predicted do not agree exactly
The formula gives the long-run truth. The measurement is 2000 actual trials, and 2000 tosses of a fair coin do not give exactly 1000 heads either. The gap between them shrinks as trials go up, in the same way the running average in Step 1 went flat.
This is worth keeping straight, because it is easy to see a small gap and conclude the formula is wrong. Raise the trial count and watch the gap close. If it does not close, then the formula is wrong.
Now the point of the whole step. You do not have to accept whatever error rate the test happens to give. You choose it. Each extra probe multiplies the miss chance by the same factor, so the error falls off a cliff while the work only creeps up one probe at a time.
Find a word in a page without re-reading it
Find every place the word the appears in a page of text. The obvious method lines the
pattern up at position 0, compares character by character, then slides along one and compares again. For
a short pattern that is fine. For a pattern of 500 characters against a document of a million, it is
500 million comparisons, most of them re-reading characters that were compared a moment ago.
Here is another idea. Turn the pattern into one number. Turn each window of the text into one number the same way. Now comparing a window with the pattern is comparing two numbers, which is one operation instead of 500. A short number that stands in for a longer piece of data is called a hash, and when it is used as an identity check like this it is often called a fingerprint.
How a character becomes a number, and what a byte is
Computers store everything as numbers, so every letter has a number agreed in advance. In the oldest and most common agreement, capital A is 65, lower-case a is 97, and a space is 32. Nothing about 65 is special: someone chose it, wrote it down, and everyone followed.
A byte is a number in the range 0 to 255, and it is the standard sized lump that computers move data around in. One byte is exactly enough for one letter in that old agreement, which is why text sizes and file sizes are quoted in bytes. A thousand bytes of plain English is about a thousand letters, or a short paragraph.
What the remainder is, and why every hash takes one
Divide 17 by 5 and you get 3 with 2 left over. That leftover, 2, is the remainder. In code
it is written 17 % 5, and the % symbol is read "modulo" or just "mod". The
remainder is always smaller than what you divided by, which is the whole reason it is used.
A fingerprint built by multiplying character codes together grows to an enormous number within a dozen characters, far too big to hold or compare quickly. Taking the remainder after dividing by some chosen number, say 1000003, keeps it inside a fixed range for ever, at the price of squashing many different texts onto the same number. That chosen number is called the modulus, and a bigger one means more room and fewer texts squashed together. Handling that price is the last part of this step.
Building each window's number from scratch would cost 500 operations per window, which saves nothing. The move that makes this work is that consecutive windows overlap almost completely. Slide one step and one character leaves the front, one arrives at the back, and everything between is unchanged. So the new number can be worked out from the old one with a subtraction, a multiplication and an addition, no matter how long the pattern is. A hash that can be updated like that is called a rolling hash.
Two different texts, one fingerprint: collisions
There are far more possible texts than possible fingerprints, so some texts must share. Two different pieces of data with the same hash is called a collision, and no cleverness removes them; the counting argument alone settles it. All you get to choose is how rare they are, by choosing how many different fingerprints exist.
Which is why the match is confirmed character by character before being reported. The fingerprint is a filter that throws out almost every window cheaply, and the expensive full comparison runs only on the few survivors. That two-stage shape, cheap filter then exact confirmation, is one of the most reused ideas in the subject, and Step 4 builds a whole structure out of it.
Why multiply by a base at all
The fingerprint here is built the way you build a number out of digits. In an ordinary number, 472
means 4×100 + 7×10 + 2. The rolling hash does the same with character codes instead of digits and a
different base instead of ten, then takes a remainder. Choosing a base bigger than the alphabet is
what makes position matter, so that abc and cba get different
fingerprints.
Add the codes instead of building a number and every anagram collides, which for text search would be a disaster. You can see this by choosing the just add the codes option in the lab above.
roll and check again.Remember 300 million addresses in a few megabytes
A web crawler visits pages and must not visit the same one twice. It has seen 300 million addresses so far. Keeping them all so it can ask "seen this one?" costs many gigabytes, and the question it actually needs answered is only ever yes or no.
So keep no addresses at all. Keep a long row of bits, every one starting at 0. To record an address, run it through three different hash functions, which gives three positions in the row, and set those three bits to 1. To ask about an address later, hash it the same three ways and look: if any of the three bits is 0, that address was definitely never added, because adding it would have set that bit.
What a bit is, and how small this really is
A bit is the smallest piece of information there is: one thing that is either 0 or 1. A byte, from Step 3, is eight bits bundled together, which is why a byte holds 256 different values, since eight yes-or-no answers can be combined in 256 ways.
Now the sizes. A web address is perhaps 60 characters, so 60 bytes, which is 480 bits. The structure in this step typically spends about 10 bits per address, whatever the addresses look like. That is roughly one fiftieth of the space, and it is why this structure gets used at all.
What a hash function is doing here, and why three of them
In Step 3 a hash turned text into a number that stood in for it. Here it turns text into a position in the row of bits, by taking the remainder after dividing by the row length. A good hash spreads unrelated inputs evenly across the row, so two different addresses rarely land in the same place.
Rarely is not never, so one bit is a weak claim. Three separate hash functions, each landing somewhere different, make the claim three times over. For a stranger to be mistaken for a member, all three of its bits must already have been set by other members, which is much less likely than one being set. The lab below lets you set the number of hash functions and see the effect.
Notice the shape of what you can conclude. When the structure says "never seen it", it is telling the truth, always. When it says "possibly seen it", it might be wrong, and that mistake is called a false positive. This is the one-sided error from Step 2 in a different costume, and once again the useful part is knowing exactly which answer to doubt. The structure is called a Bloom filter, after Burton Bloom, who described it in 1970.
Why more hash functions eventually make things worse
Each extra hash function adds another bit that a stranger has to be unlucky in, which pushes the false positive rate down. It also sets another bit per member, which fills the row faster, which pushes the rate up. Those two effects pull in opposite directions, so there is a best number of hash functions for a given row length and a given number of members, and going past it is worse than stopping short.
The best value works out to about 0.7 times the row length divided by the number of members. You do not have to take that on trust: the next lab measures the rate for every setting, so you can find the low point by looking.
Work out the real cost of one push onto a growing list
A list in most languages can grow. You add an item on the end and it just fits, for ever, however many you add. Underneath, memory does not work like that. The list owns a block of a fixed size, and when that block is full there is nowhere to put the next item.
What actually happens is: ask for a bigger block, copy every existing item into it, throw the old block away, then put the new item in. So most additions cost one small step, and occasionally one costs as much as the entire list length. A cost that grows in step with the number of items like that is written O(n) and said "order n". Adding an item on the end is called a push, and the size of the block is called the capacity, which is not the same as the number of items in it.
Why a block of memory cannot simply be extended
Memory is one enormous row of numbered slots, and a list lives in a run of neighbouring slots so that reaching item 5000 is one piece of arithmetic rather than a search. Neighbouring is the important word. The slot just past the end of your block is not spare; it very likely belongs to something else already.
So growing means finding a free run that is long enough somewhere else, and moving. The copy is not clumsiness that a better language would avoid. It is what the shape of memory costs.
What "cost" means when nobody is timing anything
Throughout this course, cost is a count of operations, not a stopwatch reading. In this step one unit of cost is one item copied, or one item written into a slot. Counting is used rather than timing because a count is the same on every machine, on a busy laptop and a quiet one, in ten years' time. This is the habit from Introduction to Algorithms, and it is why the widgets show counts.
A stopwatch is not useless, it just answers a different question: how fast is this machine today. A count answers how much work the method demands, which is the part you get to design.
What is O(n), and what does "quadratic" describe?
O(n) names the shape of a count rather than the count itself, and is said "oh of n" or "order n". Describing costs with that letter O is called big-O notation, which is the name you will see elsewhere. It means the count grows in step with n: double the number of items and the count doubles. It throws fixed multipliers away on purpose, so a method doing 3n steps and one doing 100n steps are both O(n). That makes it useful for picking a shape and useless for choosing between two methods of the same shape.
O(n²) means n multiplied by itself, so doubling the number of items makes the count four times as large. That shape has a name of its own, quadratic, and it is the difference between a method that copes with a thousand items and one that cannot cope with a million.
Now the question that matters. If one push in a thousand costs a thousand, is pushing cheap or expensive? Add up the whole run and divide by the number of pushes. That number, the total cost of a sequence divided by the length of the sequence, is called the amortised cost, and amortised is an accountant's word for spreading a lump sum over the period it covers.
Amortised is not the same as average from Step 1
In Step 1 the average was over luck: run the same input many times with different coin flips and the cost varies. Amortised cost has no luck in it at all. It is a promise about one single run: any sequence of n pushes costs at most a fixed amount times n, every time, guaranteed.
The two get confused because both end in a division. The difference matters when something goes wrong: a bad random run is unlucky and the next one will probably be fine, while an amortised bound that fails is simply false.
There is a way of proving that flatness that needs no algebra, and it is where the step's name comes from. Charge each push more than it costs. Spend part of the charge on the actual work, and put the rest in a bank. When the expensive copy arrives, pay for it out of the bank. If the bank balance never goes negative, the charge you invented is an honest upper bound on the real average cost, because you never spent money you did not collect.
Cover every corridor with cameras, within twice the best
A museum has corridors, and cameras can be placed at the junctions. A camera at a junction watches every corridor that touches it. You want every corridor watched, using as few cameras as possible. Draw the junctions as dots and the corridors as lines between them, and this is a graph: the dots are called nodes and the lines are called edges. A set of nodes that touches every edge is called a vertex cover, vertex being another word for node.
Nobody knows a method that finds the smallest cover quickly on every graph. Not "nobody has bothered": this problem is one of a large family, all provably equivalent to each other, and a fast method for one would give a fast method for thousands of famous problems at once. Several decades of serious effort have produced neither a method nor a proof that none exists.
Graph words, in one place
A graph is dots and lines: nodes joined by edges. It is a shape for relationships, not a picture of anything physical, so the same graph can be drawn a hundred ways and still be the same graph. Junctions and corridors, people and friendships, cities and roads, web pages and links are all graphs.
The number of edges touching a node is its degree. An edge is covered by a set of nodes if at least one of its two ends is in the set. Introduction to Algorithms used graphs for searching and shortest paths; here the graph is the problem itself rather than a map to walk.
Why not just try every possibility
You can, and for a graph of 20 nodes it is instant. Each node is either in the cover or out, which is 2 choices per node, so 2 multiplied by itself 20 times, which is about a million sets to test. Fine.
At 60 nodes it is 2 multiplied by itself 60 times, which is about a billion billion sets. At a million tests per second that is thirty billion years. The graphs in the lab below are deliberately small enough that the exact answer can be found by trying everything, which is what lets the widget show you the true optimum to compare against.
So change the question. Instead of the smallest cover, ask for a cover that is never worse than twice the smallest, found quickly, on every graph, guaranteed. That factor is called the approximation ratio, and a method carrying one is worth far more than a method that is usually good: usually good has no worst case you can quote to anybody.
Why taking both ends of an edge, which looks wasteful, is the whole proof
The method with the guarantee is almost embarrassing. Find any edge that is not yet covered, take both of its ends into your cover, cross out every edge those two nodes touch, and repeat. Half of every pair you take may well be pointless.
Look at the edges you picked. No two of them share a node, because after picking one you crossed out everything touching it. So any cover at all, including the smallest possible one, must contain at least one end of each of those edges, and those ends are all different nodes, so the smallest cover has at least as many nodes as you picked edges. You took exactly two nodes per picked edge. Twice at most, and the argument never once mentions what the graph looks like.
Get a delivery round within twice the shortest
A delivery van must visit twenty stops and come back to the depot. Which order makes the shortest round trip? This is the travelling salesman problem, and it belongs to the same family as Step 6: no fast exact method is known for it either.
Trying every order is worse than trying every subset. With 20 stops there are 19 × 18 × 17 and so on down to 1 different tours, which is about 120 million billion. Multiplying every whole number from 1 up to some n like that is written n! and called a factorial, and it grows faster than any power.
How far apart are two stops on a map
Give every stop two numbers, how far right it is and how far up it is, which are called its coordinates. Two stops make a right-angled triangle: the difference in the across numbers is one short side, the difference in the up numbers is the other, and the straight-line distance is the long side.
The rule for the long side is Pythagoras: square each short side, add them, then take the square root. If one stop is 3 across and 4 up from the other, that is 9 + 16 = 25, and the square root of 25 is 5. Every distance in this step and in Step 12 is worked out that way, in code, as you watch.
What a tour is, exactly
A tour is an order for visiting all the stops that starts at one of them, visits every other exactly once, and returns to the start. Its length is the sum of the distances between consecutive stops, including the hop from the last one back to the first.
Because the tour comes back to where it began, where you start makes no difference to the length, and neither does going round it the other way. That is why 20 stops give 19! tours rather than 20!, and it is the first hint that a lot of the apparent difficulty is bookkeeping rather than substance.
So we settle again, but differently from Step 6. Here there are two moves. First build any tour quickly: stand at the depot, go to the nearest stop you have not visited, repeat. That is nearest neighbour, and it produces a decent tour with one dreadful habit, which you can see the moment you run it. Then improve what you have, by looking for two edges that cross and swapping them.
What a local improvement is, and where it stops
A local improvement is a small change you can test cheaply: swap two things, and keep the swap only if the total got smaller. Repeat until no single swap helps any more. The tour you end on is called locally optimal, meaning no small change improves it, which is not at all the same as being the best tour.
Picture standing on a hillside in fog and always walking downhill. You will reach somewhere flat. Whether it is the bottom of the valley or a dip halfway up depends entirely on where you started, which is why the lab lets you rerun from a different starting tour and get a different ending.
Push as much water through the pipes as they will carry
A network of pipes runs from a reservoir to a town. Each pipe has a direction and a limit on how many litres a second it can carry, which is its capacity. Water cannot pile up at a junction, so whatever arrives must leave. How much can reach the town per second?
The starting point is the reservoir, called the source. The destination is the town, called the sink. Every other junction obeys the rule that what comes in goes out, which is called conservation. The amount arriving at the sink is the value of the flow, and the largest value any legal arrangement achieves is the maximum flow.
A directed graph, and why direction matters here
The graphs in Step 6 had plain edges: an edge between A and B works both ways. A directed edge points, drawn as an arrow, and it can only be used in the direction it points. A one-way street, a pump that only pushes one way, a job that can be given to a person but not the reverse.
An edge here carries two numbers: how much it is currently carrying, and the most it could carry.
They are drawn as 2/5, meaning two litres flowing through a pipe that could take five.
When those two numbers become equal the pipe is saturated and nothing more fits.
Why this problem is worth a whole part of the course
Almost nothing that uses maximum flow involves water. Assigning workers to shifts, matching students to schools, choosing which projects to fund, separating an object from the background in a photograph, and working out which roads to cut to divide a city are all maximum flow underneath. Step 10 does one of these conversions in full.
Pipes are the picture that makes the rules obvious. Conservation is just "nothing appears or vanishes at a junction", and everybody already believes that about water. Keep the picture, and remember that the pipes are usually a costume.
How would I find a route from the source to the town in the first place?
By walking outwards from the source. Mark the source. Look at every pipe leaving a marked junction that still has room in it, and mark the junction at its far end. Repeat until a round of looking marks nothing new. Every junction marked this way is reachable from the source. If the sink ends up marked, a route to it exists: note which pipe marked each junction and you can trace it back.
Which marked junction you look at next decides which route you find. Take them in the order they were marked and the search spreads outwards in rings, so it arrives at the sink using the fewest pipes any route could use. That is what "shortest path" means when every pipe counts as one step, and it is the fewest-hops search Introduction to Algorithms called breadth-first.
The method is one idea repeated. Find any route from source to sink whose every pipe has room left. Push as much as the tightest pipe on that route allows, which is that route's bottleneck. Repeat until no such route exists. A route with room left is called an augmenting path, and the whole method is called Ford-Fulkerson after the two people who wrote it down in 1956.
The residual edge: why you are allowed to take flow back
Push 3 litres along a pipe with capacity 5 and two things become true. There is room for 2 more in the forward direction, and there are 3 litres already there that a later path is allowed to cancel. That second option is drawn as a faint backward arrow of size 3, and it is called a residual edge. Residual just means what is left over, and here it means what is still possible.
Without it the method gets stuck. A path chosen early can be exactly the wrong commitment, and the backward arrow is how a later path says "send that water somewhere else and I will take over your route". Nothing physically flows backwards; it is bookkeeping that lets the method change its mind without starting again. Press Load the cancellation example in the lab. Four early paths are already filled in. The purple fifth path uses one bright backward arrow to undo part of the third path, which lets three more litres reach T.
Does the order of the paths change the answer
No. Different orders produce different arrangements of water, sometimes very different ones, and the total arriving at the sink at the end is always the same number. Step 9 explains why and the explanation is the best part of this whole subject.
The order does change how much work it takes. The lab offers a shortest-path chooser, which always
takes the path with fewest pipes, and that choice puts a firm limit on the number of rounds no matter
how large the capacities are. The network as it loads is too small to tell the two apart: both need
three rounds. Raise the capacity of A→C from 5 to 8 and run each chooser again and the
shortest-path one takes three rounds where the other takes four, for the same 17 litres a second.
Prove nothing more can get through, by finding the bottleneck
Step 8 left a gap. Every augmenting path proves the maximum is at least something. Nothing so far ever proves it is at most something, so when the paths run out you have a number and no reason to believe it is the best possible rather than the best you happened to find.
Here is the missing half. Split the junctions into two groups: one containing the source, the other containing the sink. Every junction goes in exactly one group. That split is called a cut. Now add up the capacities of the pipes that run from the source's group to the sink's group. That total is the capacity of the cut, and no arrangement of water can beat it, because every litre reaching the town has to cross from one group to the other somewhere.
A cut, carefully: which pipes are counted
Draw a line separating the two groups. Only pipes pointing from the source side to the sink side are counted. Pipes pointing the other way, from the sink side back to the source side, are not counted, and this is the part everybody gets wrong first.
The reason is that a backward pipe cannot help water get across; it can only carry water back the way it came, which has to cross forwards again somewhere to be useful. So the forward capacities alone are the ceiling. Counting the backward ones too would give a larger, weaker ceiling that is still true and no longer tight.
Why every cut is a ceiling, in one picture
Take any legal flow and any cut. Every litre starts at the source, on the source side, and finishes at the sink, on the other side. It cannot teleport. Somewhere along its route it crosses from one side to the other, and the only way across is a pipe pointing that way.
So the total crossing forwards is at least the flow value, and each pipe can carry no more than its capacity. Hence flow value is at most the cut capacity. This holds for every flow and every cut at once, so the largest possible flow is at most the smallest possible cut. That inequality is free. The surprise, coming next, is that it is never slack.
Now the result that ties Part 3 together. When Ford-Fulkerson stops, it has not merely run out of ideas. Take the set of junctions you can still reach from the source using pipes that have room left, counting the backward residual arrows from Step 8 as usable. Reaching means walking outwards: mark every junction a usable pipe leads to, and keep going until nothing new gets marked. Call that set the source side. That is a cut, and its capacity is exactly the flow you achieved.
What this theorem is worth outside pipes
Two quantities defined in completely different ways, the largest flow and the smallest cut, are always the same number. One is a maximum over arrangements of water, the other a minimum over ways of splitting a set of junctions. Results of that shape are called duality, and they turn up everywhere: Step 11 meets the general version.
Practically, the cut is often the answer people actually wanted. Which links must fail before a network is severed. Which pixels are object and which are background, in a photo editing tool where capacities encode how similar neighbouring pixels are. Which set of teams is over-subscribed in a rota. The flow computes it; the cut explains it.
Match six people to six jobs with the flow machine
Six people, six jobs. Each person is willing to do some of the jobs and not others. Each person takes one job, each job goes to one person. How many can be given work at the same time?
Draw people as dots on the left, jobs as dots on the right, and an edge wherever a person is willing to do a job. A graph whose nodes fall into two groups, with every edge crossing between the groups and none inside a group, is called bipartite, which means two parts. A set of edges no two of which share a node is a matching: nobody is asked to do two jobs and no job goes to two people.
Why "no two share a node" is the whole definition
Every restriction in the problem comes from that one sentence. Two chosen edges touching the same person would mean that person doing two jobs. Two chosen edges touching the same job would mean two people doing it. Forbid shared nodes and both are handled at once.
A matching that uses every node on one side is called perfect for that side. The interesting question is usually not whether a perfect matching exists but how large the best matching is, since that is the number of people who get work.
Why the obvious greedy method is not enough
Go down the list of people and give each the first free job they are willing to do. Fast, and wrong. If Ana is willing to do only job 1, and Ben is willing to do job 1 or job 2, then handling Ben first may hand him job 1 and leave Ana with nothing, when both could have worked.
Fixing it means being willing to take a job back off someone and move them, which is precisely the backward residual arrow from Step 8. That is not an analogy: once the problem is converted to flow, the residual arrows do exactly this reshuffling for you, and you never write that logic at all.
The conversion is three lines. Add a source with an arrow into every person, capacity 1. Keep every willingness edge, pointing from person to job, capacity 1. Add an arrow from every job to a sink, capacity 1. Run maximum flow. Every whole litre that gets through has used exactly one person and one job, so the flow value is the size of the largest matching, and the pipes carrying water are the pairs.
Why capacity 1 on the source arrows is doing so much work
Capacities are the only place the rules live. A capacity of 1 into a person means at most one litre can ever be inside that person's dot, so at most one willingness edge out of them can carry anything. That single number is the sentence "one job each".
Change it to 2 and you have said each person may take two jobs, and the same solver answers the new question with no other change. That is what makes flow such a widely used tool: a surprising amount of real-world fussiness is expressible as capacities and the solver never needs to know what the capacities mean.
Work out how many chairs and tables to make
A workshop makes chairs and tables. Each chair takes 2 hours of work and 1 plank; each table takes 3 hours and 4 planks. There are 24 hours and 20 planks in a week. Chairs sell for 30 and tables for 50. How many of each should be made?
Every sentence there is the same shape: some amounts multiplied by fixed numbers, added up, and required to stay under a limit. A requirement of that shape is a constraint, and the thing you are trying to make as large as possible is the objective. A problem made only of those pieces is a linear program, and "program" here means a plan or schedule, a word older than computers.
Reading an inequality, and drawing one
The symbol ≤ means "is less than or equal to". Writing 2c + 3t ≤ 24 says: two hours for each chair plus three for each table, added up, must not exceed 24. It is not an equation to solve, it is a filter that some pairs of numbers pass and others fail.
Draw chairs across and tables up. Every pair of amounts is a point. The pairs that use exactly 24 hours form a straight line, and the pairs that use fewer are everything on one side of it. So one constraint cuts the picture in half, and several constraints together leave a shape with straight sides.
The feasible region, and what a corner is
The shape left after all the constraints have had their say is the feasible region: every point inside it is a plan you could actually carry out. Outside it you have run out of hours, or planks, or you are making a negative number of chairs.
A corner of that shape is a point where two of the constraint lines meet, and where both are exactly used up: all 24 hours and all 20 planks, with nothing spare. Corners are special because there are only a few of them and one of them is always the answer.
The value of a plan is 30 chairs plus 50 tables, and the plans worth exactly 600 also form a straight line. Sliding that line outwards raises the value and the best plan is the last point of the region the line touches on its way out. A straight line leaving a straight-sided shape leaves through a corner, which is why an optimum is always at a corner, and why checking a handful of corners is enough.
Why the best plan is never strictly inside the region
Suppose the best plan sat somewhere in the middle, not touching any constraint. Then you have hours spare and planks spare, so you can make one more chair and be better off. That contradicts it being best.
The same argument pushes you along an edge until you reach a point where you cannot move in any improving direction without breaking something, and that point is a corner. This is the reason the standard method for solving these, the simplex method, walks from corner to corner rather than searching the interior.
Flow was a linear program all along
Give every pipe in Step 8 an amount. The constraints are "each amount is between zero and that pipe's capacity" and "at each junction, in equals out". The objective is the total arriving at the sink. Every one of those is amounts multiplied by fixed numbers and added, so max flow is a linear program with one variable per pipe.
The min cut is its dual, which is the general version of the pairing in Step 9: every maximisation of this shape has a matching minimisation whose answer is the same number. Ford-Fulkerson is faster than a general solver because it exploits the pipes, and it is solving an instance of the same thing.
Find the closest two aircraft without checking every pair
A thousand aircraft on a radar screen. Which two are closest together? Compare every pair and that is 499500 distance calculations, and it has to finish before the picture updates.
Splitting the problem in half is the obvious first move, and it is the move that seems to fail. Sort the points left to right, cut down the middle, and find the closest pair in each half. Now you have two answers and a hole: the closest pair overall might be one point from the left half and one from the right. Nothing you have computed says anything about those.
Divide and conquer, briefly recalled
Solve a big problem by cutting it into smaller copies of itself, solving those the same way, and combining. Mergesort in Introduction to Algorithms did this: sort each half, then merge. A method that calls itself on smaller inputs is recursive, and the smallest case, where it answers directly instead of splitting, is the base case. Here the base case is three points or fewer, which you just compare directly.
Whether divide and conquer helps depends on the combining cost. If splitting creates smaller easy cases but recombining them repeats the original amount of work at every level, the method gains little. This step derives a linear-time combine for the closest-pair problem.
Why the hole in the middle is not as big as it looks
Call the better of the two half answers d. A crossing pair only matters if it is closer than d. Both of its points must therefore be within d of the dividing line, because anything further away is already more than d from everything on the other side. So only points in a narrow strip of width 2d need considering at all, and usually that is a handful.
That alone is not enough, because someone could arrange every point inside the strip. The second idea is what saves it: sort the strip's points bottom to top, and for each one, only compare it with the next few above it. Points further up than d cannot be within d, and the strip is only 2d wide, so no more than a fixed handful can be packed into that region without two of them being closer than d to each other, which cannot happen since d was the best in each half.
What is log n, and what does "a log factor" cost me?
log n counts how many times you can halve n before you are down to 1. Halve 16 and you get 8, then 4, then 2, then 1: four halvings, so log 16 is 4. Doubling n adds exactly one to the count, which is why a thousand points give about ten and a million give about twenty.
It turns up here because a method that cuts its input in half over and over has about log n levels of cutting. A method described as slower "by a log factor" pays some cost once per level instead of once in total. On a million points that is about twenty times the work: a real penalty, and still nothing like the gap between the two methods raced below.
What the first twelve steps gave you
- Use randomness as a design tool, not a last resort: remove the worst case by removing the thing an opponent could aim at.
- Choose an error probability the way you choose any other budget, and know which of the two answers a one-sided test allows you to doubt.
- Build a rolling fingerprint, and pair a cheap filter with an exact confirmation.
- Size a Bloom filter for a target false-positive rate and defend the memory it saves.
- Argue that a sequence of operations is cheap on average even when one of them is expensive.
- Tell an approximation with a guarantee from a heuristic that usually works, and say why the difference matters.
- Model a problem as maximum flow, run Ford-Fulkerson, and read the minimum cut back as an explanation someone can act on.
- Recognise a linear program when you see one, and know why its answer sits at a corner.
Connections from the first twelve steps
- Advanced Data Structures. The amortised argument from Step 5 is the everyday tool there: splay trees, union-find and Fibonacci heaps are all cheap only when you average over a run.
- Computational Complexity. The family of problems in Steps 6 and 7 has a name and a theory, including why a fast method for one would be a fast method for all of them.
- Optimisation. The simplex method walked over in Step 11, integer programming, and what happens when the corners are too numerous to visit.
Write the problem contract before choosing an algorithm
A problem statement needs an input, valid outputs, an objective and limits. “Plan the deliveries” is not enough. May a vehicle revisit a street? Are capacities hard limits? Is the goal shortest distance, earliest completion, fewest vehicles, or a weighted mixture? Two versions that sound alike can require different algorithms and prove different things.
Also name the output type. A decision problem asks yes or no. A search problem asks for a witness. An optimisation problem asks for the best feasible witness. A counting version asks how many witnesses exist. A solver cannot be tested until those contracts and boundary cases are explicit.
Constraints are not cleanup
Release times, negative weights, duplicate objects, disconnected graphs and integer-only variables can invalidate an otherwise correct method. Put each one in the instance model before proving anything.
Reduce a new problem to a solver you already trust
A reduction translates instances and answers while preserving the question that matters. Job assignment became flow earlier in this course. Difference constraints become shortest paths. Boolean choices can become SAT clauses, and linear objectives with linear constraints can become LP or integer programming models.
The translation needs two proofs. Every original solution must map to a legal target solution, and every target answer you accept must decode to a legal original answer with the promised value. Include the encoding size: a translation that expands n items into 2n clauses is not a polynomial-time reduction.
Reductions can preserve approximation too
An approximation-preserving reduction tracks how target-solution quality becomes source-solution quality. A yes/no reduction alone may lose the objective information needed for that claim.
Branch and bound searches exactly while proving branches useless
Backtracking explores a tree of partial choices and rejects a branch as soon as it violates a constraint. Branch and bound adds an optimistic bound on the best answer any completion of that branch could reach. If the bound cannot beat the best complete solution already found, prune the whole branch.
The bound must be optimistic in the correct direction. A minimisation lower bound may be smaller than the true completion cost, never larger. Better starting solutions and tighter bounds reduce the tree, but the worst case can remain exponential. Report timeout and optimality gap rather than calling an interrupted incumbent “optimal”.
Node order changes when a good incumbent arrives
Exploring promising branches first can find a strong incumbent early. That does not change correctness, but it lets the same lower bound prune more of the remaining tree.
Move the explosion into a small parameter
An algorithm with running time nk is polynomial for every fixed k, but it becomes unusable quickly as k grows. A fixed-parameter tractable algorithm has the form f(k)·nc, where c does not depend on k. If k stays small in the intended workload, 2kn can beat nk by an enormous margin.
Choose a parameter that describes the difficult structure: solution size, treewidth, number of errors, or distance from an easy case. Kernelisation safely shrinks the instance to a size bounded by k before the expensive phase. A large or uncontrolled parameter gives no practical rescue.
XP is not FPT
Running time nf(k) belongs to the class XP. It is polynomial for each fixed k, but the polynomial degree grows with the parameter. FPT keeps that degree constant.
Heuristics need baselines, restarts and honest claims
Local search starts from one feasible answer and moves to a neighbour that improves it. It can find good routes, schedules and layouts quickly, then stop at a local optimum that is not globally best. Random restarts, tabu memory, simulated annealing and larger neighbourhoods change the exploration; none creates an approximation guarantee by itself.
Evaluate a heuristic against a simple baseline, exact optima on small cases and the best valid lower or upper bound on larger cases. Publish the seed, time budget, machine-independent work budget and full distribution across instances. One best run hides instability.
Keep tuning and evaluation instances separate
If parameters are chosen on the same cases used for the final score, the benchmark becomes part of the training process. Hold out evaluation cases and report every failure.
Return a solution, its value and evidence
Recompute feasibility and objective value from the returned object instead of trusting cached totals. Then seek independent evidence: a cut matching a flow, dual variables matching a linear-program value, a lower bound matching a branch-and-bound incumbent, or a witness that a decision answer is yes.
Small exhaustive oracles catch modelling and implementation errors. Metamorphic tests transform an input while predicting how the answer changes. Keep solver version, random seed, limits and status with every run so “optimal”, “feasible”, “infeasible” and “timed out” never collapse into one vague success flag.
No answer and proved infeasible are different
A failed search may mean timeout, memory exhaustion or a bug. Infeasible is a mathematical claim and needs a complete proof procedure or a separately checkable certificate.
What you can do now
You can formulate a problem, classify the requested output, choose exact, randomised, approximate, parameterised or heuristic work, model flow and linear programs, and state what the returned evidence proves. Continue with Computability and Complexity, Optimisation, or Online Algorithms for the corresponding limits and extensions.