Algorithms and Data Structures

Why a correct program can still be useless, and how to measure what one costs without measuring the machine it happened to run on.

Big O, Omega and Theta defined with witnesses you can actually produce, the growth hierarchy priced in seconds, and the four things the notation hides.

Why an index costs the same whatever its value, why an insertion in the middle does not, and why a growable array has to double rather than grow by a fixed number of slots.

What you buy by letting each element name its successor, what you give up, and the three restricted interfaces (stack, queue, deque) that the trade produces.

Binary search derived from its invariant, counted exactly, proved optimal by a decision-tree argument, and the two boundary errors that shipped in real libraries for years.

Selection, insertion and bubble sort with exact counts, inversions as the real measure of disorder, why stability matters, and the quadratic wall in seconds.

The recurrence that describes a self-calling algorithm, two ways to solve it, mergesort derived and counted exactly, and the same idea applied to multiplying large numbers.

Partitioning in place, why the average is about 39 per cent worse than mergesort and the algorithm still wins, what makes the worst case quadratic, and the same partition used to find a median in linear time.

A counting argument that no comparison sort can beat {n}{{log}}_{{2}}{n}, what the bound does and does not forbid, and two sorts that finish in linear time by looking at the keys instead of comparing them.

Making a key compute its own address, why collisions cannot be avoided, chaining against open addressing, the expected probe count as a function of load factor, and what constant-time lookup costs.

An ordering property that lets a linked structure halve its search space, the three cases of deletion, and why the height that costs {1.39}{{log}}_{{2}}{n} on random input becomes {n} on sorted input.

The constant-time rotation that restructures a tree without disturbing its order, the AVL rule whose height bound comes from Fibonacci numbers, the looser red-black rule that real libraries ship, and the wide nodes that put a billion keys three reads deep.

A weaker ordering that costs nothing to keep, a tree stored in a plain array with no pointers, a build step that is linear rather than {n}{log}{n}, and the queue that the graph algorithms will run on.

The structure whose contents are its relationships, why a list beats a matrix by five orders of magnitude on a road network, and the two systematic walks that answer most questions about connection.

Replacing the queue with a heap to get cheapest routes rather than shortest ones, the exact assumption that makes it correct, what to do when that assumption fails, and connecting every vertex for the least total cost.

Taking the locally best option and never reconsidering, the exchange argument that has to be supplied before it can be trusted, Huffman codes computed and their saving measured, and the one-word change to a problem that makes greed fail.

Recursion that revisits the same subproblem exponentially often, the two ways to solve each one once, tables filled by hand for rod cutting, knapsack and edit distance, and reading the answer back out of the table.

Why the knapsack table is not polynomial, what P and NP actually say, the difference between finding an answer and checking one, what to do when a problem is genuinely hard, and the decision procedure the whole course has been assembling.