Overview
This is the root index for the Algorithms area of the vault — foundational definitions and cost models that apply across every algorithm family below, plus links to each family’s own index.
Foundational Concepts
What is an Algorithm?
Definition A procedure for performing a computation, broken into well-specified steps.
- Input: , an instance
- Output: , a solution
Both and should be finitely describable.
A good algorithm must produce the correct answer, in a reasonable amount of time and space, using the least energy.
Hierarchy of Obviousness
- Obvious algorithms: implicit in the problem statement — brute force, exhaustive search.
- Methodical algorithms: applying general principles and paradigms that improve algorithms across a wide variety of problems (e.g. the design paradigms this vault is organized around).
- Clever algorithms: stretching those general paradigms in a way that best fits one particular problem — usually where the real insight and difficulty of a course lives.
Time for Arithmetic
The CPU is designed to process instructions on word-sized inputs.
- Inputs less than word size: performed on the CPU in a single access.
- Inputs greater than word size: must be broken down into word-sized chunks.
| floating point | arbitrary | ||
|---|---|---|---|
| Addition | |||
| Subtraction | |||
| Comparison | |||
| Multiplication |
Categories in This Vault
| Category | Index | One-line description |
|---|---|---|
| Graph Algorithms | Graph Algorithms | Traversal (DFS/BFS), shortest paths (Dijkstra’s), and MSTs (Prim’s/Kruskal’s) — all specializations of the generic Graph Search procedure |
| Greedy Algorithms | Greedy Algorithms | Locally-optimal-choice algorithms, plus the three general techniques for proving one actually is optimal |
| Divide and Conquer | Divide and Conquer | Break into smaller similar subproblems, solve recursively, combine — sorting, selection, and the Master Theorem that analyzes them all |
| Dynamic Programming | Dynamic Programming | Identify overlapping subproblems and solve smallest-first — often the fix for an exponential Backtracking algorithm |
| Backtracking | Backtracking | Exhaustive search that prunes dead-end branches using the problem’s constraints — usually exponential, but much better than brute force |
| Linear Programming | Linear Programming | Optimization with linear constraints and objective — no local optima, global optimum always at a vertex of the feasible region |
Related Notes
- Levels of Algorithm Design — the High/Mid/Low-Level Design framework used throughout this vault’s individual algorithm notes.
- Algorithm Base ― A structured, filterable, sortable database view over the algorithm notes