An O(ND) Difference Algorithm and its Variations, Eugene W. Myers. Describes an O(nd) (where n is the input length and d is the edit distance) algorithm for finding the longest common subsequence (LCS)/shortest edit script (SES, or what people usually mean when they say “diff”) of two sequences. Intricate & subtle, and with some historical quirks (e.g. 1-indexing), but defines the problem exceptionally well. The algorithm’s efficiency hinges crucially on a very deep understanding of the problem, making it an interesting case study in optimization.