Computer Science Deep Dive
by Sergey Okinchuk
Connectivity and Spanning TreesDivide and Conquer

Chapter Nine · Designing Algorithms

Designing Algorithms

Chapters 7 and 8 met a handful of techniques inside particular algorithms; this chapter names them and prices each one as a way of thinking. Five topics: splitting a problem, committing to the best local step, answering each repeated subproblem once, trying and undoing, and algorithms that flip coins or are allowed a bounded error.

5 topics

Merge sort, Dijkstra's algorithm and a spell-checker look like three unrelated pieces of code. They are three answers to one question: how should the work of solving a problem be organized? Merge sort splits the problem in half and trusts the halves. Dijkstra commits to the closest node and never looks back. The spell-checker notices that it keeps asking the same small questions and writes the answers down. Each choice of organization has a cost that can be read off before any code runs.

This chapter reads those costs. Divide and conquer is priced from a picture of its recursion. Greedy algorithms are fast, and correct only when a short swap argument says so. Dynamic programming trades a table of memory for exponential time, and it is how Lantern, the library search service, forgives a typo within two edits. Backtracking searches spaces too large to list by refusing to enter most of them. The last topic accepts a small, known error in exchange for enormous savings, with Lantern's Bloom filter as the example.

The problems that none of these techniques can tame, where the best known method is still exponential, are named here and left for Chapter 14.

Five ways to organize the work, and what each one costs
Divide and conquer: split, solve, combine→work per level × levels
Greedy: best local step, never undone→often n log n; exact only with a proof
Dynamic programming: each subproblem once→the size of the table
Backtracking: try, check, undo→exponential at worst; pruning sets the rest
Randomness: coins and bounded errors→tiny and fast, with an error bar

Topics in This Chapter

Topic 01
Divide and Conquer
Split, solve, combine: reading log n, n log n and n off a recursion tree, Karatsuba and fast powers, the uneven split that turns n log n into n², and where recursion stops paying.
Algorithms
Topic 02
Greedy Algorithms
The best local step and the swap argument that proves it: meetings by earliest finish, coins of 1, 3 and 4, heuristics with and without a bound, and LRU as a greedy guess.
Algorithms
Topic 03
Dynamic Programming
Answer each repeated subproblem once: memo against table, edit distance cell by cell, and how Lantern finds terms within two typos without filling 75 million cells per keystroke.
Algorithms
Topic 04
Backtracking and Search
Try, check, undo: a 50-blank sudoku's 48-digit search space, pruning on partial answers, most constrained first, version resolvers, and why every production search needs a budget.
Algorithms
Topic 05
Randomness and Probabilistic Structures
Random pivots and seeds against crafted input, always-right against always-fast, Lantern's 1.8 MB Bloom filter, its error past the design count, and HyperLogLog in 12 KB.
Algorithms