Part IV: Algorithms and systems
From data structures and proofs of correctness to machines, operating systems, databases, networks, and distributed systems.
- C06Data structures, representation, and amortized cost5 exercisesChoose between contiguous and linked representations, trace stacks and queues, explain hash collisions, and distinguish worst-case, expected, and amortized costs.
- C07Algorithm design, correctness, and complexity5 exercisesChoose among divide-and-conquer, greedy, dynamic programming, and backtracking; prove a recurrence-based algorithm correct; and analyze the operations of a specific implementation.
- C08Trees, heaps, graphs, and shortest-path reasoning5 exercisesTrace BFS, DFS, and Dijkstra; distinguish a heap from a search tree; justify a spanning-tree choice; and select graph representations under explicit constraints.
- W02From invariants to algorithm design5 exercisesDerive a dynamic program from a dependency order; prove a search boundary; separate a valid algorithm from a tempting method whose assumptions fail.
- Cumulative checkpoint: algorithms and data structures6 exercisesUse after C06–C08 and J02’s first independent attempt. For every complexity claim, identify the operation counted, input size, and worst-case/expected/amortized meaning. Allow roughly 60–90 minutes or split the set across two…
- C09Bits, instructions, caches, and virtual memory5 exercisesDecode integer and floating-point representations, distinguish language rules from compiler and hardware choices, trace a cache model, and explain how source code becomes an executable.
- C10Operating systems, concurrency, and safe coordination5 exercisesDistinguish processes and threads, explain blocking and asynchronous work, identify races and deadlocks, and implement a bounded queue whose closure and lifetime contracts are explicit.
- W03From program objects to memory behavior5 exercisesSeparate language guarantees from a hardware model; reason about ownership and publication; predict small address-translation and cache traces before measuring real programs.
- C11Relational databases, transactions, and recovery5 exercisesDesign a small schema, write joins and aggregates, use constraints and parameterized queries, explain transaction boundaries, and test rollback and backup behavior.
- C12Networks, byte streams, and protocol boundaries5 exercisesDistinguish transport guarantees from application guarantees, reason about latency and throughput, and implement a bounded incremental message decoder.
- C13Partial failures, retries, and distributed consistency5 exercisesModel ambiguous failures, specify a retry-safe operation, distinguish consistency models, and explain a bounded CAP argument without the misleading “pick any two” slogan.
- C14Software engineering, testing, debugging, and defensible measurement5 exercisesTurn a requirement into testable behavior, isolate faults, design meaningful regression tests, and report a benchmark with enough detail to reproduce and challenge it.
- C15Languages, parsing, interpreters, and compiler structure5 exercisesSeparate syntax from meaning, parse precedence into an abstract syntax tree, evaluate a bounded expression language, and explain how an interpreter differs from a compiler.
- C16Automata, decidability, reductions, and complexity classes5 exercisesConstruct small finite-state recognizers, explain a halting contradiction, use reduction direction correctly, and distinguish P, NP, NP-hardness, and NP-completeness.
- W07The reach and limits of computational proof5 exercisesConstruct a finite-model equivalence algorithm and its proof; distinguish nonregularity, undecidability, and intractability; use a reduction in the correct direction.
- C17Security boundaries, usable interfaces, and professional responsibility5 exercisesConstruct a small threat model, distinguish authentication from authorization, apply context-appropriate input/output handling, and document privacy, accessibility, and operational limits.
- Cumulative checkpoint: systems and engineering evidence6 exercisesUse after C09–C17. These questions intentionally mix representation, failures, safety, and evaluation. Work from assumptions rather than recalling a slogan. A design answer can have several valid implementations, but must…
- chapter
- workshop: connects two subjects
- checkpoint, review or assessment