Concepts
These small representations appear repeatedly in the algorithm chapters. Practice converting them by hand until the place values and invariants feel automatic.
Number representation
To convert binary to decimal, multiply each bit by its power of two and add the results:
To convert decimal to binary, repeatedly divide by two and read the remainders from bottom to top.
Algorithm concepts
- Invariant — a property that remains true before and after each loop iteration.
- State — the information an algorithm must retain to continue correctly.
- Base case — the smallest input a recursive definition solves directly.
- Recurrence — an equation that describes a problem in terms of smaller instances.
- Greedy choice — a locally best choice that is safe under the problem’s proof conditions.
- Amortized cost — the average cost over a sequence of operations, even when individual operations vary.
- Stable sort — a sort that preserves the relative order of equal keys.
- Idempotent operation — an operation that can be applied repeatedly without changing the result after the first application.