Computer Science — Core Curriculum A general prerequisite-led education with explicitly documented gaps.
Independent educational material; not endorsed by the named companies.
Track progress 0 / 0
Progress is stored only in this browser. Reset progress
1. Mathematics, algorithms and implementation Programming fundamentals: control flow, functions and loop invariants Learn branches, loops, functions, scope and invariants by tracing a complete linear-time array algorithm with boundary tests. Data types and representation: integers, bytes, text and precision Learn type contracts, integer bounds, byte order, UTF-8 lengths and numeric precision through a reproducible binary record format. Logic, Proof Techniques and Loop Invariants Build precise program arguments with propositions, quantifiers, counterexamples, induction, loop invariants and termination proofs. Programming Semantics, Aliasing and Executable Contracts Reason about evaluation, equality, mutation, exceptions and function contracts before using language features in algorithmic solutions. Programming memory: references, aliasing and object lifetimes Understand name bindings, identity, mutable aliases, call frames and immutable snapshots through a reproducible memory model. C programming foundations: pointers, arrays, bounds and object lifetimes Learn C pointers, array decay, valid pointer arithmetic, ownership and lifetime through a bounded C11 program and tests. Discrete Mathematics: Sets, Counting and Exact Probability Learn counting identities, combinations, conditional probability, Bayes and expectation with exact fractions and independently tested examples. Binary Relations, Equivalence Classes and Partial Orders Derive equivalence partitions, partial orders, reachability closure and topological dependencies with executable counterexamples. Asymptotic Analysis and Algorithmic Cost Derive time and space complexity from loops, recurrences and invariants, while distinguishing worst-case, amortized and expected costs. Floating-point reasoning: rounding, cancellation and compensated summation Analyze binary approximation, nonassociative addition and Neumaier compensated summation using exact rational oracles. Numerically stable statistics: online mean and Welford variance Derive one-pass mean and variance updates, distinguish sample and population denominators and test against exact fractions. Number theory fundamentals: divisibility, GCD and the Euclidean algorithm Derive divisibility, the Euclidean algorithm and Bézout coefficients with proofs, signed inputs and independent exercises. Modular arithmetic: congruences, inverses and fast exponentiation Derive congruences, modular inverses and repeated squaring with correctness invariants and exhaustive small-number tests. Algorithmic reasoning: specifications, brute force, invariants and optimization Learn a repeatable problem-solving method by deriving a correct linear-time solution from a quadratic reference algorithm. Recursion, Call Stacks and Divide-and-Conquer Understand recursive contracts, base cases, stack frames, termination proofs and divide-and-conquer recurrences with executable tests. Solving Algorithmic Recurrences: Trees, Substitution and Master Theorem Derive and independently verify divide-and-conquer recurrences, exact operation counts, Master cases, counterexamples and stack costs. Arrays and Strings: Representation, Costs and Correct Iteration Understand contiguous arrays, dynamic growth, indexing, slices, Unicode strings and boundary invariants with tested examples. Abstract data types: interfaces, representation invariants and costs Separate an ADT contract from storage, derive a bounded circular queue and verify FIFO, wraparound and complexity. Dynamic arrays: capacity, shrinking and amortized analysis Implement a resizable array with append, pop, reference clearing and quarter-full shrinking, then prove amortized costs. Linked Lists: Nodes, Reversal, Cycles and Ownership Implement and prove singly linked-list reversal and Floyd cycle detection; compare pointer operations with dynamic-array costs. Stacks and Queues: LIFO, FIFO, Deques and Invariants Distinguish stack and queue contracts, derive their invariants, implement balanced-delimiter scanning and BFS-compatible queues. Sorting Algorithms: Stability, Mergesort, Quicksort and Heapsort Derive insertion, merge, quick and heap sorting, compare worst-case costs and stability, and verify two complete implementations. Binary Search: Bounds, Invariants and Monotone Predicates Derive binary search with a partition invariant, implement exact bounds, analyze complexity and explain when the method is invalid. Hash Tables, Collisions and Invariants Understand hash functions, collision resolution, load factors and adversarial inputs, with a correct frequency-counting example and edge cases. Binary Heaps and Priority Queues Explain heap shape and order invariants, derive logarithmic updates and linear heapify, and solve top-k with executable examples. Binary Trees and BSTs: Traversals, Ordering and Height Explain binary-tree structure, DFS/BFS traversals, BST ordering and height-dependent complexity with an iterative tested implementation. Graph Traversal with BFS and DFS Derive breadth-first and depth-first search, shortest paths in unweighted graphs, visited-state invariants and O(V+E) complexity. Formal Languages and Finite Automata: DFA, NFA, Epsilon Closure and Determinization Build the computational model behind lexical analysis: define languages, derive DFA/NFA equivalence, implement epsilon-closure determinization, and test it independently. Context-Free Grammars, Pushdown Automata and Syntax Analysis Derive context-free recognition, implement a pushdown recognizer and syntax tree, and test an Earley-style chart parser with independent oracles. An Expression Compiler: Lexing, Precedence Parsing, AST, Bytecode and Virtual Machine Implement an auditable arithmetic language from ASCII tokens to an AST, stack bytecode and exact rational evaluation, with independent tests. Static Type Checking, Lexical Scopes and a Typed Expression Compiler Extend the expression compiler with typed let-bindings, lexical shadowing, Boolean conditionals, static judgments and verified stack bytecode. Typed Functions, Lexical Closures and Bytecode Call Frames Compile typed first-class functions, lexical closures and higher-order calls with explicit VM activation frames and independent execution tests. Mutable Cells, Shared Closures and Typed Recursive Functions Extend typed functions with mutable lexical cells, assignment and let-rec initialization, then verify aliasing and recursive VM execution. Lexical Addresses, Typed Bytecode Verification and a Slot-Based Virtual Machine Resolve lexical variables to indexed slots, analyze bytecode control flow and stack types, and verify execution against an independent VM. Versioned Bytecode Serialization, Integrity Checks and Verified Loading Design a bounded, versioned bytecode wire format with deterministic JSON, integrity checking, strict decoding and mandatory VM verification. Heap Reachability, Object Lifetimes and Stop-the-World Mark-and-Sweep Derive object reachability and a bounded mark-and-sweep collector with shared closure cells, cycles, explicit roots and independent tests. Garbage Collection Inside the Slot VM: Roots, Closures and Recursive Cycles Integrate explicit-root mark-and-sweep with the verified slot VM, preserving mutable closures and reclaiming unreachable recursive cycles. Dynamic Programming: States and Recurrences Learn to define states, derive recurrence relations, prove transition correctness and select memoization or tabulation with exact cost bounds. 2. Software design and engineering Modular programming: cohesion, explicit interfaces and pure functions Learn how to decompose programs into cohesive modules, separate computation from input/output and test boundaries without frameworks. Python error contracts: exceptions and resource cleanup Specify invalid data, propagate exceptions and verify context-manager cleanup with reproducible source streams. File and data fundamentals: bytes, UTF-8, JSON schemas and safe boundaries Read bounded UTF-8 JSON files, reject ambiguous or malformed data and write validated records with explicit failure limits. Git fundamentals: working tree, index, commits and branch history Understand three Git states, reproducible commits, branches and merges, with a tested isolated repository workflow. Testing, Contracts and Maintainable Changes Build correct, reviewable changes using invariants, test boundaries, integration contracts, regression cases and explicit operational risk analysis. Clean Code Fundamentals: Cohesion, Coupling and Change-Safe Design Derive readable and maintainable code boundaries using cohesion, coupling, pure functions, explicit contracts, refactoring and tested inventory examples. Object-Oriented Design: Encapsulation, Composition and Polymorphism Design object-oriented boundaries with encapsulation, composition, polymorphism, contracts and a tested order-pricing model. Low-Level Design: Contracts, State Machines and Dependency Boundaries Design maintainable components from invariants, state transitions, interfaces and dependency direction, with a tested reservation model. SOLID, Dependency Inversion and Behavioral Contracts Apply SRP, OCP, LSP, ISP and DIP pragmatically with Python protocols, stable boundaries and verified behavior tests. Software architecture: dependency boundaries and modular design Derive layered and ports-and-adapters architectures, enforce module dependencies, document decisions and test a modular monolith. Domain modeling: entities, value objects and aggregate invariants Distinguish identity from immutable values, select aggregate boundaries and enforce order invariants with executable contracts. Software Testing Strategies: Units, Contracts, Integration and E2E Separate unit, property, integration, contract and end-to-end tests with executable examples and clear limits of evidence. Refactoring and Design Patterns: Strategy, Adapter and Behavior Preservation Refactor safely with behavioral tests; compare Strategy, Adapter and Decorator with concrete Python examples and trade-offs. Design Pattern Families: Builder, Facade and Observer Derive creational, structural and behavioral design choices using tested Builder, Facade and Observer examples and explicit failure contracts. State and Command patterns: transitions, replay and failure contracts Use explicit state transitions and command objects to separate business decisions from requests, with tests for versions and duplicate execution. Creational patterns: Factory Method, Abstract Factory and simple factories Compare constructor selection, overridable creation hooks and compatible object families with tested export pipelines and explicit failures. Debugging and Profiling: Reproduction, CPU, Memory and Tracing Diagnose bugs through reproducible cases, independent oracles, CPU profiles, memory traces and production telemetry. Software Project Lifecycle: From Requirements to Operations Trace a software project from acceptance criteria and design through tested delivery, measured releases, incident learning and maintenance. CI/CD and Release Engineering: Canary, Schema Evolution and Rollback Design CI gates, immutable artifacts, canary decisions, safe database migrations, secrets and recovery procedures. 3. Processes, threads, memory and networks Digital logic fundamentals: Boolean gates, truth tables and binary adders Derive AND, OR, NOT and XOR from truth tables and construct verified half-adders, full-adders and fixed-width addition. Sequential logic fundamentals: clocked state, registers and finite-state machines Derive clocked state transitions, D flip-flops, registers and finite-state machines with executable invariants and traces. Machine Representation, CPU Instructions and Cache Mapping Derive two's complement, endianness, ISA execution and direct-mapped cache conflicts with reproducible Python models and boundary tests. CPU fundamentals: datapath, control and the fetch–decode–execute cycle Trace PC, accumulator, memory, ALU and branches using a bounded 8-bit instructional CPU with explicit instruction semantics. CPU Pipelines: Data Hazards, Forwarding and Branch Prediction Derive instruction latency, throughput, stalls, load-use dependencies and two-bit branch prediction with independently tested pipeline models. From C source to executable: preprocessing, object files and linking Compile multi-file C11, understand translation units, object symbols, linking failures and loader boundaries. Build fundamentals: dependency graphs, incremental compilation and GNU Make Derive a build DAG and test C11 recompilation rules with header dependencies, phony targets and failure propagation. How programs run: command-line arguments, environment, streams and exit status Trace a program invocation using C11 arguments, environment variables, stdout, stderr and subprocess tests. Processes, Virtual Memory and System Calls Derive process isolation, virtual-address translation, page tables, TLBs, context switching, syscalls and protection guarantees. Heap Allocation: Free Lists, Fragmentation and Coalescing Model first-fit and best-fit heap allocation, contiguous free blocks, external and internal fragmentation, splitting and coalescing with independent tests. File Descriptors, Buffered I/O and fsync Crash Boundaries Trace open file descriptions, dup, shared offsets, read/write, buffering, fsync and crash recovery with independently verified Python models. Filesystem Internals: Inodes, Block Allocation, Journaling and Recovery Model inode identity, directory entries, noncontiguous block allocation and commit/replay crash boundaries with tested finite-state examples. CPU Scheduling: FCFS, Round Robin, Response and Fairness Derive FCFS and Round Robin scheduling, preemption, arrival ties, turnaround and waiting with executable models and independent tick oracles. Concurrency: Races, Locks, Conditions and Deadlocks Derive synchronization invariants, critical sections, race conditions, condition-variable protocols, deadlocks and bounded queues. Priority Scheduling: MLFQ, Aging and Priority Inheritance Derive MLFQ scheduling, periodic priority boosts, starvation and lock priority inheritance with independently verifiable models. Memory Models: Atomics, Happens-Before and Visibility Explain C++ data races, per-object modification order, release/acquire, relaxed operations, sequential consistency and publication safety. C++17 Engineering Workshop: Thread-Safe Token Bucket and CI Build and test a native C++17 token bucket with steady clock injection, mutex invariants, input validation and compiler-backed CI. HTTP fundamentals: requests, responses, methods and client-server boundaries Understand web requests, status codes, GET/POST/PUT/DELETE semantics and basic API responsibilities before advanced system design. IP Routing and DNS: Prefix Selection, Resolution and TTL Caches Derive IPv4 longest-prefix routing and DNS resolver caching, record TTL expiry and failure semantics with independent Python test oracles. IP Packet Size: IPv4 Fragmentation and Path MTU Discovery Derive the 8-byte IPv4 fragment offset, MF/DF semantics, ordered reassembly, and classical PMTUD under explicit finite models. DNS Authority, CNAME Chains and Negative Caching Derive DNS zone authority, recursive referrals, CNAME chains, NXDOMAIN/NODATA cache keys and SOA-based negative TTLs with independent tests. Networking Fundamentals: DNS, TCP, TLS and HTTP Trace a web request through DNS, transport, TLS and HTTP; derive latency and failure budgets and distinguish TCP from QUIC. TCP Byte Streams: Message Framing, ACKs and Flow Control Derive TCP stream framing, relative sequence numbers, cumulative acknowledgments and sender windows using independently verified Python models. TCP Retransmission Timers: RTT Estimation, Karn's Rule and Congestion Windows Derive RFC 6298 SRTT/RTTVAR/RTO and backoff, then distinguish a simplified cwnd/ssthresh round model from actual TCP Reno. 4. Security, storage and distributed systems TLS 1.3: Handshake Authentication, HKDF and Traffic Keys Trace TLS 1.3 authentication and key derivation, distinguish HKDF from encryption, and verify HKDF-SHA256 and TLS labels against standard vectors. API Security: Identity, Authorization and Threat Models Distinguish authentication from object authorization, analyze OAuth and JWT boundaries, and derive tenant isolation and API threat controls. OAuth 2.0 Security: PKCE, Token Binding and Replay Derive the authorization-code PKCE flow, threat boundaries, refresh-token rotation, audience checks and replay resistance from IETF standards. Relational database fundamentals: keys, joins and data integrity Derive tables, primary and foreign keys, normalization and SQL joins from a small data model with executable constraints. SQLite application fundamentals: parameterized CRUD and atomic transactions Build and test a small SQLite repository with bound parameters, constrained balances and transaction rollback. SQLite schema migrations: user_version, compatibility and rollback Evolve a SQLite database safely from two schema versions while preserving rows and rejecting inconsistent states. Database Storage: Pages, MVCC, B-Trees and Write-Ahead Logs Trace tuple storage, B-tree page splits, MVCC version visibility and write-ahead crash recovery using documented PostgreSQL internals. SQL Query Planning: Selectivity, Statistics, Indexes and Joins Understand SQL cost-based plans, cardinality estimation, composite indexes, join strategies and EXPLAIN ANALYZE with reproducible math. Transactions, Isolation and Distributed Consistency Distinguish ACID isolation, serializability, linearizability, replication lag and practical consistency anomalies using explicit operation histories. Transactional Indexes: MVCC, Uniqueness and Serializable Isolation Explain unique constraints under concurrency, multi-version indexes, predicate locking, write skew, isolation retries and indexing trade-offs. Queues, Delivery Semantics and Idempotency Design asynchronous processing with at-least-once delivery, acknowledgments, dead-letter queues, retries, idempotent consumers and backpressure. Distributed Consensus: Raft, Quorums and Replicated Logs Derive quorum intersection and Raft terms, elections, log matching, commit rules, safety and limits during network partitions. Network Partition Models: Exhaustive Quorum Connectivity Checks Enumerate every undirected network graph for three and five voters, prove majority exclusivity, and identify untested partition behaviors. 5. Architecture and operational judgment Capacity Estimation and System Constraints Build capacity estimates from explicit workload assumptions, utilization, peak traffic, storage growth and queueing effects without false precision. System Design Method: Requirements, Sizing, Interfaces and Failures Learn a complete system design method through requirements, workload estimation, APIs, data ownership, failure handling and verifiable SLOs. System design: authoritative writes, projections and consistency Design write paths and read projections with replay-safe event processing, consistency targets, lag budgets and recovery verification. Storage Selection: Relational, Document, Key-Value and Object Stores Choose storage by access patterns, consistency invariants and cost; compare relational, document, key-value, blob and search models. Service Boundaries: Modular Monoliths, Microservices and Events Choose software service boundaries by ownership, consistency, synchronous failure and measured scaling trade-offs. Production Incident Response, Recovery and Postmortems Build an incident command structure, stabilize service, quantify user impact, preserve evidence and write testable postmortem actions. Formal Verification: Invariants, State Exploration and TLA+ Learn safety versus liveness, atomicity and refinement through finite-state model checking of a concurrent reservation protocol, with TLA+ foundations. Not yet covered in this edition Not published: advanced number theory beyond Euclid and basic modular arithmetic, and higher-order recurrences, generalized parse forests, mutual recursion, incremental heap collection and detailed object-layout analysis, authenticated bytecode distribution and native code generation, Turing computability, P/NP, physical timing of sequential circuits, microarchitectural implementation, cache coherence, production allocator internals, advanced multicore scheduling, production filesystem recovery and fault injection, full TCP sequence wrap/retransmission and ACK-driven congestion models, DNSSEC, IPv6 neighbor discovery and live packet captures, AEAD/signatures/PKI beyond HKDF, P2P and optional blockchain.
Publicly documented requirements https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/ https://pages.cs.wisc.edu/~remzi/OSTEP/