Learning objectives
By the end you can:
- State a cost model and reason inside it. Given a code fragment, name the dominant operation, count it against input size, and state time and space complexity, and say what the constant factor and the memory hierarchy do to that claim in practice.
- Implement, from scratch and correctly, the seven core structures: dynamic array, hash map with collision resolution, stack, queue (ring buffer) and deque, linked list, binary search tree, and binary heap, each with its full operation set and its per-operation cost justified, not asserted.
- Prove amortised bounds. Show by the aggregate and the accounting method that append on a doubling array is O(1) amortised, that the monotonic-deque sliding window is O(n) despite an inner loop, and why the shrink threshold must be a quarter rather than a half.
- Analyse hashing honestly: expected O(1) under simple uniform hashing with expected chain length equal to the load factor α, worst case O(n), and the adversarial and clustering cases that turn one into the other.
- Reason about trees by height: derive the O(height) bound, show that a randomly built BST has expected height Θ(log n) while sorted insertion gives exactly n − 1, and state what a self-balancing tree (AVL, red-black, B-tree) buys and costs.
- Prove Floyd's O(n) heap construction and use a bounded heap for top-k in O(n log k) time and O(k) space.
- Traverse and search graphs: adjacency list versus matrix, BFS/DFS at O(V + E), topological sort by Kahn's algorithm with free cycle detection, Dijkstra, Bellman-Ford with negative-cycle detection, and union-find with path compression.
- Search and sort with the bounds proven: binary search's O(log n) and its loop invariant; insertion, merge, quick and heap sort with recurrences solved; the Θ(n log n) comparison lower bound proven by decision tree; and the linear-time non-comparison sorts and when they apply.
- Apply the three paradigms: divide and conquer (with the master theorem), greedy (with an exchange-argument proof and a counterexample where greedy fails), and dynamic programming (optimal substructure plus overlapping subproblems, then memoisation or tabulation).
- Choose the right structure for a stated operation profile and defend it out loud at interview standard, including the second-order considerations (stability, cache behaviour, memory, worst versus expected case) that separate a correct answer from a good one.
- (Productivity objective: R10 duality.) Use a coding copilot on this material the way a working developer does, after you can do it by hand, and review its output for the failure modes specific to algorithmic code: plausible-but-wrong boundary conditions, silently quadratic "optimisations", and hallucinated standard-library APIs.
The duality, stated once (R10). The gated skill is objectives 1–10, and the gate is deliberately hostile to shortcuts: the code-pack hidden tests check array layouts, exact resize ladders and closed-form invariant counts that a generated answer will not reproduce by luck, and they run at sizes where a wrong-complexity answer simply does not finish. Objective 11 is the payoff you keep. The app never calls an AI at runtime, the callouts below ask you to generate something in your own tool, paste it back, and let the local hidden tests grade it. The machine drafts, the tests judge, and you are the one who has to know why it failed.
Prerequisites & connections
Builds on. CS1.01 and CS1.02 for Python itself, functions, classes, dunder methods, and the built-in list/dict/set you are about to build from scratch. CS1.03 for what memory actually is: stack versus heap, pointers and indirection, and why a contiguous block behaves differently from a chain of scattered nodes. And above all CS1.04, which owns Big-O notation, recursion and the mechanics of asymptotic analysis. This node does not re-derive what Big-O means or how to unroll a recursive call; if T(n) = T(n−1) + O(1) is not yet an automatic read, go back, one clean hour there makes this node twice as fast. What CS1.05 adds is the hard analysis CS1.04 deliberately left alone: amortised argument, the master theorem, expected-case analysis, and information-theoretic lower bounds.