Computer Science Foundations

Computer science foundations study the cost and structure of computation. The useful mental model is: algorithms transform inputs into outputs, data structures control access patterns, and complexity tells you which ideas survive when problem size grows.

Core sequence:

1. Big-O and Complexity Analysis - describes how time and memory scale with input size.
2. Sorting and Selection - canonical problems for comparison, divide-and-conquer, and order statistics.
3. Hash Tables - trade memory and hashing assumptions for expected constant-time lookup.
4. Graphs and Traversals - models pairwise relationships and search over connected structure.
5. Dynamic Programming - solves problems by reusing overlapping subproblem solutions.
6. P vs NP and Intractability - separates efficiently solvable problems from problems where verification may be easier than search.
7. Randomized Algorithms - uses randomness to simplify algorithms or improve expected performance.
8. Floating Point and Quantization - explains numerical approximation in real hardware.

How the pieces fit:

• Big-O gives the scale model for computation.
• Sorting, selection, hash tables, and graph traversal are basic algorithmic tools.
• Dynamic programming exploits repeated structure instead of recomputing.
• Complexity theory warns when exact search is likely to be infeasible.
• Randomization trades deterministic guarantees for simpler or faster expected behavior.
• Floating point and quantization connect abstract algorithms to finite machine arithmetic.

Core equations to keep active:

• Complexity comparison: $O(n) < O(n\log n) < O(n^2) < O(2^n)$ asymptotically.
• Graph traversal cost: BFS/DFS run in $O(|V| + |E|)$.
• Dynamic programming recurrence pattern: $D[s] = \min_a \{c(s,a) + D[T(s,a)]\}$.
• Hash table expected lookup: $O(1)$ under a good hash function and controlled load factor.
• Verification view of NP: a proposed solution can be checked in polynomial time.
• Floating point relative error pattern: $\mathrm{fl}(x \circ y) = (x \circ y)(1+\delta)$ for small $\delta$.

See also: Computational Complexity of Attention, Memory Hierarchy and IO-Awareness