Algorithms & Data Structures

Getting Sorted & Big O Notation

Computerphile

Shows why the choice of sorting method, not raw processor speed, is what determines whether a program finishes in seconds or in centuries.

MIT 6.006 Introduction to Algorithms

Erik Demaine and Srini Devadas (MIT OpenCourseWare)

Works through the standard algorithm curriculum by deriving each data structure from the problem that forces it, so the choice of structure is argued rather than catalogued.

The Design of Approximation Algorithms

David P. Williamson & David B. Shmoys

Organises approximation algorithms by the proof technique that bounds their distance from optimal — LP rounding, primal-dual, and the greedy method — rather than by problem.

Algorithms

Jeff Erickson

Derives each standard algorithm from the problem that forces its invention, and insists a formal correctness argument accompany every method taught.

On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem

Joseph B. Kruskal

Proves that repeatedly adding the cheapest edge that does not create a cycle always produces a graph's minimum spanning tree, establishing this greedy choice as provably optimal.

A Note on Two Problems in Connexion with Graphs

E. W. Dijkstra

Gives an algorithm for the shortest path between two nodes and for a minimum spanning tree, both in time proportional to the square of the number of nodes.

Assumes graphs, and nothing else — under three pages, and it predates the notation now used to teach it

Quicksort

C. A. R. Hoare

Introduces an in-place, divide-and-conquer sorting method whose average running time beats existing comparison sorts despite a quadratic worst case.

A Dynamic Programming Approach to Sequencing Problems

Michael Held & Richard M. Karp

Applies dynamic programming to the travelling salesman problem, cutting the search from a factorial number of tours to one exponential in the number of cities by remembering subsets already solved.

Gaussian Elimination is Not Optimal

Volker Strassen

Gives a way to multiply two matrices using fewer multiplications than the schoolbook method, by recursively combining seven sub-products instead of eight.

Depth-First Search and Linear Graph Algorithms

Robert E. Tarjan

Shows that depth-first search, run once, reveals a graph's biconnected components and strongly connected components in time proportional to its size.

A Fast String Searching Algorithm

Robert S. Boyer & J Strother Moore

Shows that scanning a pattern against text from right to left, and skipping ahead on a mismatch using precomputed tables, finds matches in sublinear expected time.

A Dichromatic Framework for Balanced Trees

Leo J. Guibas & Robert Sedgewick

Recasts several balanced tree schemes, including red-black trees, as instances of one framework that colours nodes to bound rebalancing cost.