Introduction to Algorithms

A hash table is a container built for one question: have I seen this before? It turns the thing you hand it into a slot number by arithmetic, then goes straight to that slot instead of searching.

Asking and storing each cost about one step, however many IDs are already in there. That is why the second method can afford one lookup per ID and then stop.

Compare the first ID with every other one: n−1 comparisons. The second with everything after it: n−2. Keep going and the total is (n−1) + (n−2) + … + 1, which adds up to n(n−1)/2.

The halving is there because comparing A with B is the same test as comparing B with A. With 2,000 IDs it is 2,000 × 1,999 / 2, a little under two million.

You can skip every code block in this course and lose nothing. The prose always says in words what the code says in symbols. If you want to read them, here is the whole of what you need for this one. A line starting with def gives a name to a job and lists what you hand it, so def has_repeat_pairs(ids) means "here is a job called has_repeat_pairs, and you hand it a list of ids". A named job like that is called a function, and running one is called calling it. Anything after a # is a note to the human reader and the machine ignores it. Lines that belong inside something are pushed to the right, so the two indented lines under the for are the ones that get repeated.

A for line repeats what is under it once for each value. for x in ids means "do this once with x set to the first id, once with x set to the second, and so on". A single = puts a value into a name; a double == asks whether two things are equal, and the doubling is there so the two can never be confused. return hands an answer back and stops the job there and then. That is the whole vocabulary of both functions below: one walks every pair and returns as soon as two match, the other keeps a set of what it has already seen and returns as soon as something turns up twice.

Work both formulas out at a few sizes and watch the lead change hands. At n = 100, A takes 3 × 100 + 400 = 700 steps and B takes 10,000 ÷ 100 = 100 steps, so B is seven times better. At n = 400, A takes 1,600 and B takes 160,000 ÷ 100 = 1,600 as well. Dead level. At n = 1,000, A takes 3,400 and B takes 10,000, so now A is three times better, and it stays better forever after.

That is the crossover: 400. You can find it by hand, by trying sizes until the two columns cross, and that is a perfectly good way to find it. If you have met quadratic equations, setting 3n + 400 = n²/100 and solving gives exactly 400 as well. If you have not met them, nothing later in this course needs them. The point to keep is the shape of what happened, not the arithmetic: B started ahead because of its small constant, A finished ahead because of its gentler growth, and there is always a size where they swap.

Linear means straight line. Plot looks against list length and that is the graph you get: a list twice as long takes twice as many looks. The name describes the shape of the cost, not the shape of the code.

Sorted needs only a rule that, given any two items, says which comes first. Numbers have one. So do words, by dictionary order, and dates, by which came earlier. Anything with such a rule can be put in order and hunted by halving.

Most languages let you hand that rule in yourself, which is how a list of people ends up sorted by surname rather than by whatever the computer would have picked.

Twenty is how many times you can halve a million before you are down to one: 1,000,000 then 500,000 then 250,000, twenty steps in all. Step 3 turns that count into a search.

Twenty million is a million items times those twenty levels, which is what a good sort costs. Step 5 builds it. Both numbers are worked out properly later; here they are only being used to compare two plans.

log₂ n is the number of times you can halve n before you reach 1. Halve 16 and you get 8, 4, 2, 1: four halvings, so log₂ 16 = 4. Doubling n adds exactly one to it, which is why a thousand items need ten looks and a million need twenty.

When people write "log n" about an algorithm they nearly always mean this halving count, and leave the small 2 off.

Three numbers do all the work, and they are the three you will drive in the lab below. lo is the lowest slot still worth looking at and hi is the highest, so together they fence off the part of the list the target could still be hiding in. mid is the slot halfway between them, the one you are about to turn over. At the start lo is 0 and hi is the last slot, so the fence holds everything. Each look moves one of the two fenceposts inward, and when they cross, the fenced-off part is empty and the target was never there.

In the code, int just says these three names hold whole numbers. The while line is the loop: everything inside the braces repeats as long as the test in the brackets is true. lo <= hi means "as long as lo is less than or equal to hi", which is the same as "as long as at least one slot is still fenced in". A single = puts a value into a name, a double == asks whether two things are equal, and a[mid] means the value sitting in slot mid. Anything between /* and */ is a note to the human reader. return hands the answer back and stops, and returning −1 is the usual way of saying "not here", since there is no slot numbered −1.

A whole number in many languages is kept in 32 bits, and one bit records the sign, so the largest value is 2,147,483,647. Add one and the bits roll over the way an odometer rolls from 999999 to 000000, except that here the result comes out as the most negative number instead.

An index of −2,147,483,648 is not a position in your array, so the program reads whatever happens to be there, or stops.

An array keeps its items side by side, so item 500 sits at a known distance from item 0 and one multiplication gets you there. A linked list keeps each item wherever there was room, and each item holds the address of the next one.

The only way to reach the 500th is to follow 500 arrows from the front. Same items, same order, and a completely different price for "go to the middle".

Take 5, 2, 9, 1, 6. Selection sort scans all five and finds 1, so 1 goes first. It scans the remaining four and finds 2. Then 5, then 6, then 9. Five scans, each one shorter than the last, and the scan happens whatever order the cards were in.

Insertion sort takes 2 and slides it past 5. Takes 9 and leaves it alone. Takes 1 and slides it past 9, 5 and 2. Takes 6 and slides it past 9. The work depends on how far each card has to travel, which is why tidy input is cheap.

Selection sort scans n items, then n−1, then n−2, all the way down to 1. That sum is n(n−1)/2, the same total as the all-pairs count in Step 1, which is a shade under half of n².

Insertion sort has the same worst case: if every item must slide past everything before it, item number k costs k−1 comparisons. On random data it averages about half of that, so the shape stays n² and only the constant changes.

A method recurses when it calls itself on a smaller piece of the same problem. Steps 5 and 6 both do it, and Step 8 takes the idea apart properly.

For this sentence the picture is enough: the fast sorts keep cutting the list into smaller lists, and stopping that cutting early to finish with insertion sort is cheaper than cutting all the way down to single items.

There are log₂ n levels of merging, and each level does about n comparisons, because each level touches every item once. Adding n up once per level is n × log₂ n.

A thousand items: 1,000 × 10. A million items: 1,000,000 × 20. The list got a thousand times longer and the cost per item only doubled.

Merging reads the front of each pile and writes the smaller one out. If it wrote back over the input it would land on an item it has not read yet, so the output goes into a second array and is copied back afterwards.

Merges that work in place do exist. In place means rearranging the items inside the array you were given, using no second array to hold the result. They cost more comparisons and moves than the spare array does, so almost nobody uses them.

A million squared is a million million, and half of that is five hundred billion. That is the n²/2 count for selection sort on a million items.

n log n on the same list is a million times twenty, which is twenty million. Divide one by the other: five hundred billion over twenty million is twenty-five thousand.

After the pass, everything left of the pivot is smaller than it and everything right of it is bigger. Sorting those two sides only shuffles items inside them, so nothing ever crosses the pivot.

Its position is therefore the position it has in the finished list. Each partition nails down one item for good, which is why quicksort needs no merging step at the end.

Quicksort partitions a list, then does the same to each side, and those sides do the same again. Depth is how many of those rounds are stacked up at the deepest point.

An even split halves the list every time, so the depth is about log₂ n: twenty for a million items. A split that peels off one item leaves depth n, and every one of those rounds is a real function call the machine has to hold on to.

Not a break-in. The attacker sends requests that are expensive for you to answer, until the machine has nothing left for anyone else. A search box that takes a tenth of a second normally and forty seconds on one carefully chosen list is enough.

Anything whose cost depends on the shape of its input is worth checking for this, and the usual fix is to add a choice the attacker cannot predict.

Walk the list comparing each item with its neighbour and swapping the two if they are the wrong way round. One pass drags the largest item to the end. Repeat until a pass makes no swaps at all.

It does about n²/2 comparisons, like selection sort, but far more moves, because it only ever swaps neighbours. It is in the race as the slow end of the scale.

A heap is a pile that always knows its largest item, and costs about log n steps to add one or take the top one off. Pour every item in, then pull them out one at a time and they come out in order. n items times log n each is n log n, with no second array.

It is slower than quicksort in practice because it jumps around in memory rather than walking through it, which is why libraries keep it as the safety net rather than the first choice.

16 × 16 is 256, and half of that is 128. log₂ 16 is 4, so n log n is 16 × 4 = 64. The n² method does about twice the comparisons of the n log n one, not thousands of times more, and twice as many cheap steps can easily beat half as many dear ones.

Put a million into the same two formulas and you get five hundred billion against twenty million. The growth rate only takes over once n is big.

Every call sets aside a small block: the arguments, the local variables, and the place to return to. The arguments are the values you handed the function when you called it, so in fib(30) the argument is 30. The local variables are the scratch values that call is using and no other call can see. And the place to return to is where the machine should carry on once this call has an answer. Those blocks are stacked up, the top one being the call running right now, and each one is thrown away when its call returns.

A base case is a size answered outright with no further call, like "a list of one item is already sorted". Without one the stack keeps growing until the space set aside for it runs out, and the program stops with a stack overflow.

Start with 0 and 1. Every number after that is the two before it added together: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. So fib(6) is 8.

They turn up here because the definition is two lines long and becomes a recursive function without any thought at all, which is exactly how the trouble starts.

Each call makes two more, and those make two more, until the branches hit the base cases. Adding one to n adds another level to the tree, which roughly doubles the number of nodes. Doubling per step is what 2ⁿ means.

The true count grows slightly slower than doubling, by a factor of about 1.6 per step, because the two branches are not the same height. Skip that detail if you like; nothing later needs it.

memo={} hands the function a notebook to write in, empty to begin with. A notebook of that kind is a dictionary. You look things up in it by a key rather than by position, the way you look up a word instead of counting to the four-hundredth word. n in memo asks "is there anything filed under n", memo[n] is whatever is filed under n, and memo[n] = … files something new there.

So the four lines read: if n is 0 or 1, answer outright; if the answer is already filed under n, hand that back and stop; otherwise work it out the slow way, file it under n, and hand it back. All of the saving is in the second of those, because handing an answer back stops a whole subtree of calls before it starts.

A queue is a supermarket line: items come out in the order they went in, first in first out. A stack is a pile of plates: the last one you put down is the first one you pick up, last in first out.

Both add and remove in about one step. The only difference is which end you take from, and here that single choice decides the whole behaviour of the search.

V is the number of places, called vertices or nodes. E is the number of links between them, called edges. So "about V + E steps" means the search touches each place once and each link once.

Which of the two dominates depends on the graph. A road map has a few roads per junction, so E is a small multiple of V. A group where everybody knows everybody has E close to V², and that is where a search starts to hurt.

Depth-first suits any question where you want a route rather than the shortest route: getting out of a maze, checking whether a graph contains a cycle, or visiting everything with almost no memory. It also writes itself as a recursive function, since the call stack is already a stack.

None of the later steps need this. It is here so that depth-first does not look like the losing option.

Infinity here means "no route known yet". It is stored as a value larger than any real total, so the first route found is always an improvement on it and the comparison needs no special case.

A place still sitting at infinity when the run finishes is a place you cannot reach at all.

A heap is a pile that always knows its smallest item. Taking that item out, or adding a new one, costs about log n steps instead of a scan through everything.

Dijkstra asks "which unsettled place is nearest" once for every place, and without the heap each of those questions means looking at every place. With it, the whole run costs about (V + E) log V rather than about V². On a road map of a million junctions that is the difference between roughly eighty million steps and a million million.

A place's tentative distance can improve more than once while it waits. When it does, the tidy thing would be to hunt down its old entry in the heap and correct it, but hunting costs more than the alternative: push a second entry with the better distance and leave the old one where it is. So the heap panel will sometimes show the same place twice, once at 9 and once at 7.

That is safe because the better entry is smaller, so it always comes out first. When the stale one finally surfaces, the place has already been settled and the method simply drops it and takes the next. The line under the lab tells you when this happens. Doing the cheap wrong-looking thing and cleaning up later is a common trade, and it is worth noticing here rather than being puzzled by it.

It gives up on settling places in a clever order. Instead it relaxes every link in the graph, then does that again, V−1 times over, because a shortest route can pass through at most V−1 links.

That costs V × E rather than about E log V, and in exchange it copes with negative lengths. Run one extra round: if any distance still improves, there is a loop you can go round forever getting shorter, so no shortest route exists. Nothing later needs this.

Optimal means no other answer scores better on the measure you picked. For change it means no set of coins makes that amount with fewer coins. For Dijkstra it means no route is shorter.

Which is why the measure has to be said out loud. Fewest coins and lightest pocketful of coins are different questions, and they have different best answers.

By trying every combination: every way of making the amount out of that coin set, keeping whichever used fewest coins. It is slow, and on small amounts it still finishes instantly, which is all you need in order to catch a greedy rule out.

Step 12 does the same job with a table and no wasted work. Here the slow answer exists only to disagree with the fast one.

A minimum spanning tree is the cheapest set of links that still connects everything, with no loops. Repeatedly taking the cheapest link that joins two so-far separate pieces gives the best answer, and that can be proved.

A Huffman code gives short bit patterns to common letters and long ones to rare ones, by repeatedly merging the two rarest items. It is inside every zip file and every JPEG. Both are greedy, both come with proofs, and neither is needed for the rest of this course.

Richard Bellman named it in the 1950s at a research company living on defence money, whose paymasters disliked anything that sounded like mathematical research."Programming" then meant planning rather than code, and "dynamic" was picked because it sounded impressive and hard to argue with.

The name tells you nothing about the method. Nothing later depends on knowing where it came from.

Three moves can produce the first i letters of one word from the first j letters of the other, and each one reuses a cell you have already filled: delete a letter, which is the cell above plus 1; insert a letter, which is the cell to the left plus 1; or line the two letters up, which is the cell above-left, plus 1 if the letters differ and plus 0 if they match.

The cell takes the smallest of those three. That is the whole method. The table is bookkeeping for it.

A recurrence gives an answer in terms of smaller answers of the same kind: fib(n) = fib(n−1) + fib(n−2) in Step 8, or the three-neighbour rule here.

Finding the recurrence is the hard part of dynamic programming. Once you have it the loop order is decided for you: fill the cells in any order that reaches a cell only after the cells it names.

Say it "oh of n", or "order n". The O is not a number and not a function. It is shorthand for "the count grows like this, give or take a fixed multiplier".

So O(n) covers a method taking 3n steps and one taking 100n steps, because both double when n doubles. Throwing that difference away is what makes it useful for picking a shape, and useless for choosing between two methods of the same shape.

Halving gives log₂ n. Splitting into ten pieces gives log₁₀ n. The two differ by a fixed multiplier of about 3.32 whatever n is, and big-O has already thrown fixed multipliers away, so the base is left off.

When you want an actual count of levels rather than a shape, the base matters again, and it is whatever you are dividing by. Nothing else in this course turns on it.

If a method really takes about c × n² steps, then dividing the measured count by n² leaves roughly c whatever n is, so that column sits still while n doubles.

Divide the same count by n instead and you are left with c × n, which doubles every time. Divide it by n³ and it halves every time. The flat column names the shape, and the drifting ones rule the others out.

Show three things. First, the invariant is true before the loop. Second, one round keeps it true. Third, when the loop stops, the invariant plus the stopping condition gives the postcondition.

Then prove termination separately with the variant. Correctness has two halves: if the method stops its answer is right, and the method really does stop.

A property-based test generates many valid inputs and checks a property or oracle. When one fails, shrinking removes pieces until the smallest useful counterexample remains. “Fails on [-3]” is easier to diagnose than a page of random numbers.

Random cases are not enough. Add inputs chosen to hurt the method: sorted data for a first-pivot quicksort, hash collisions for a table, a long thin graph for recursion, or values at integer limits. Measure time, memory and recursion depth as well as the returned answer.