Git’s diff (Myers’ algorithm) - the case study

Every time you run git diff, something underneath is solving a puzzle: what is the fewest line changes that turn the old file into the new one. It looks like matching text side by side. It is really a shortest-path search, and by the end of this lesson you will see that path every time you read a patch.

Boards

• The Map
• Two Files, One Question
• The DP Table and Why It Dies
• The Edit Graph
• Myers Greedy BFS
• Reading the Trace Back
• Linear Space
• What Git Actually Ships
• Everything

Before you start. Two things from earlier in this track carry the whole idea: a graph is dots joined by one-way streets, and the cheapest route between two dots is a shortest-path question (Graphs (BFS, DFS, Dijkstra, topological sort)); a dynamic-programming table answers a big problem by filling in every smaller version of it first, cell by cell (Recursion & Dynamic Programming). Hashing, turning a chunk of text into one number so two chunks compare instantly (Hashing), is what makes checking a huge file cheap, and it comes back in the second read.