Counting the Steps: What Your Loop Actually Costs
Before any algorithm makes sense you need one habit: counting how many times a line runs. Here is that habit, built from four small C++ programs and a stopwatch.
Problem Solving From Zero01
Series · 21 parts · 2,016–2,021
Problem Solving From Zero
Twenty parts, written between 2016 and 2021, from counting the steps in a loop to implementing machine learning by hand. Greedy, graphs, dynamic programming, game theory, number theory, strings, segment trees, and what the memory hierarchy does to all of them. Every part assumes only the part before it.
Big-O Without the Maths: Naming the Shape of a Curve
Big-O is not a speed and not a stopwatch. It is a claim about the shape of a curve. Six shapes, where each one comes from, and the four rules for reading them.
Problem Solving From Zero02
Prefix Sums and Two Pointers: The Array Tricks You Will Use Forever
Two techniques that turn a quadratic loop into a linear one, on the humblest data structure there is. Range sums in constant time, and the sliding window.
Problem Solving From Zero03
Sorting: What to Know, What to Call, and What to Sort By
You will almost never write a sort. You will constantly decide what to sort by, and that decision is where the problems are actually solved.
Problem Solving From Zero04
Pointers and Linked Lists: Addresses, and the Data Structure Made of Them
A pointer is the address of a box, not the box. Once that clicks, dynamic memory, references and the linked list all fall out of the same idea. In C and C++.
Problem Solving From Zero05
Binary Search, and Binary Search on the Answer
Searching a sorted array is the easy half. The useful half is guessing the answer and asking a monotone yes-or-no question, with no array in sight.
Problem Solving From Zero06
Greedy: When Taking the Best Now Is Provably Right
A greedy rule that passes the samples and fails the tests is the most common way to lose a contest. Here is how to tell a correct greedy rule from a plausible one.
Problem Solving From Zero07
Recursion and Backtracking: Trusting a Function You Have Not Finished Writing
Recursion is hard because everyone traces it. The habit that makes it mechanical: write the contract, trust the smaller call, never trace the stack.
Problem Solving From Zero08
Memoisation: Paying Once for an Answer
The cheapest optimisation in programming: remember what you already worked out. One dictionary turns an exponential recursion into a linear one.
Problem Solving From Zero09
Dynamic Programming Is a Table You Fill In
Four questions turn a problem into a dynamic program: what is the state, what is the answer for a state, what is the base, and in what order do you fill it.
Problem Solving From Zero10
The Knapsack Family, and When the State Is a Set
Knapsack is one recurrence with a dozen disguises. Learn the family, then learn to put a set of items in the state with a bitmask when n is small.
Problem Solving From Zero11
Graphs: How to Store One, and Breadth-First Search
Half of all algorithm problems are graph problems in disguise. Here is how to represent a graph, and the search that finds shortest paths for free.
Problem Solving From Zero12
Depth-First Search: Cycles, Components, and Topological Order
BFS goes wide, DFS goes deep, and the difference is not stylistic. DFS answers questions about structure that a queue simply cannot see.
Problem Solving From Zero13
Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall
Three algorithms, three different jobs. Which one to reach for depends on negative edges, on how many sources you have, and on nothing else.
Problem Solving From Zero14
Disjoint Sets, and the Cheapest Way to Connect Everything
Twelve lines of code, two operations, and a running time so close to constant that nobody bothers with the difference. Then minimum spanning trees for free.
Problem Solving From Zero15
Game Theory: Nim, Losing Positions, and the Grundy Number
Two players, perfect information, no luck. Who wins? The answer comes from labelling positions, and one theorem collapses any such game into a single number.
Problem Solving From Zero16
The Number Theory You Actually Need
Sieves, greatest common divisors, modular arithmetic and inverses. Five tools, each about ten lines, that cover almost every number theory problem you will meet.
Problem Solving From Zero17
Strings: Hashing, KMP, and the Z-Function
Where does this pattern occur? Three answers in linear time, each with a different trade: one is easy and probabilistic, two are exact and need a table.
Problem Solving From Zero18
Fenwick Trees and Segment Trees: When Updates and Queries Interleave
Prefix sums break the moment an element changes. Two structures answer range questions and point updates in logarithmic time, and one of them is twenty lines.
Problem Solving From Zero19
Machine Learning Algorithms by Hand
Four algorithms in forty lines each, with no library. k-nearest neighbours, linear and logistic regression, k-means, and a decision tree, plus what each one assumes.
Problem Solving From Zero20
Memory: Why the Array Wins Even When the Step Count Says Otherwise
Big-O counts steps and assumes every step costs the same. It does not. A cache miss costs a hundred steps, and that is why a linked list loses to an array.
Problem Solving From Zero21