LEARNING PATH
Build your CS foundations
Understand what happens after you write the code.
Follow a program from execution to memory, complexity, and the CPU. Use computer science foundations to answer questions that come up while building software.
For programmers who want to connect their experience to computer science foundations
Why can two implementations of the same task run at different speeds?
Scope and finish line
Every main reading in this course is published and available now.
- Steps
- 22
- Main readings
- 22
- Check questions
- 60
What you will learn to explain
- Explain how array access, data structures and algorithm choices affect running time.
- Explain execution and the role of the OS, then reason about programs using types, compilers and computation theory.
Final main reading: Computability, Reductions, P, and NP
Complete each step’s main reading and its check, where one is provided. Extra reading and experiments are optional.
See the final step ↓0 of 22 steps complete
Start learning →Apply the course in code
After an experiment, apply its rule in a short function and test the result.
Your learning steps
STEP 01Not started From Source Code to a Running Program
Goal: Explain how source code passes through a compiler, interpreter, and runtime before execution.
STEP 02Not started Values, Types, Control Flow, Functions, and Modules
Goal: Trace values, types, expressions, branches, and loops to explain changes in program state.
Main reading: Values, Types, Control Flow, Functions, and Modules →
Explore the mechanisms
STEP 03Not started Propositional Logic, Predicate Logic, and Proof
Goal: Formalize natural-language claims using propositions, logical connectives, and quantifiers, and explain why inference rules are valid.
Main reading: Propositional Logic, Predicate Logic, and Proof →
STEP 04Not started Memory, Pointers, References, and Lifetimes
Goal: Diagram runtime memory using stacks, heaps, addresses, pointers, and references.
Main reading: Memory, Pointers, References, and Lifetimes →
Explore the mechanisms
STEP 05Not started Complexity and Measured Performance
Goal: Derive time and space complexity using O, Omega, and Theta notation and explain how costs grow with input size.
Main reading: Complexity and Measured Performance →
Explore the mechanisms
STEP 06Not started Binary Representation, Logic Circuits, and Instruction Sets
Goal: Represent integers, characters, and instructions as bit sequences and explain how basic logic operations support computation.
Main reading: Binary Representation, Logic Circuits, and Instruction Sets →
Explore the mechanisms
STEP 07Not started CPUs, Instruction Cycles, and Pipelines
Goal: Trace instruction fetch, decode, execution, memory access, and write-back.
Main reading: CPUs, Instruction Cycles, and Pipelines →
Explore the mechanisms
- Measuring execution with perf stat
- IPC and instruction throughput: count useful work per cycle
- Branch predictors: choose a path before the condition is resolved
- Out-of-order execution and dependencies
- Branch prediction and misprediction cost
- SIMD and loop vectorization
- Inspect SIMD instructions and loop tails
STEP 08Not started Caches and the Memory Hierarchy
Goal: Explain the memory hierarchy of registers, caches, main memory, and storage, and why locality matters.
Main reading: Caches and the Memory Hierarchy →
Explore the mechanisms
- Locality of reference: closeness in time and space
- TLBs: caching address translations
- Cache coherence: coordinating copies of one memory location
- Trace cache placement from addresses
- Reason about performance ceilings with Roofline
- Compare row and column traversal order
- Compare stride, visit count and traversal time
- Compare starting alignment with valid C accesses
- Measure arithmetic work and nominal traffic
- Separate first and repeated timing observations
STEP 09Not started Arrays, Lists, Stacks, Queues, Hash Tables, and Trees
Goal: Explain the representations and operation costs of major data structures and select one for a required workload.
Main reading: Choose a data structure from the operations you need →
Explore the mechanisms
STEP 10Not started Divide and Conquer, Greedy Algorithms, Dynamic Programming, and Backtracking
Goal: Identify when divide and conquer, greedy algorithms, dynamic programming, and backtracking apply to a problem's substructure.
Main reading: Choose among greedy methods, divide-and-conquer, and dynamic programming →
Explore the mechanisms
- Binary search: handle boundaries with a half-open interval
- Merge sort: combine already sorted sequences
- Quicksort: partition balance changes performance
- Find a target pair from two endpoints
- Maintain interval state with a sliding window
- Binary-search the smallest feasible answer
- Discover search bounds by doubling
- Select one rank with three-way Quickselect
- Sample an unknown-length stream with a reservoir
- Choose each item once with 0–1 knapsack
STEP 11Not started Graph Representations, BFS, DFS, and Shortest Paths
Goal: Model real problems as vertices, edges, and weights, and explain the differences between adjacency lists and matrices.
Main reading: Understand BFS and DFS through traversal order and shortest paths →
Explore the mechanisms
STEP 12Not started Debugging, Testing, and Reproducibility
Goal: Reproduce a defect and narrow down its cause using logs, stack traces, and a debugger.
Main reading: Debugging and testing: turn a hypothesis into a small check →
Explore the mechanisms
STEP 13Not started Sets, Relations, Functions, and Counting
Goal: Represent discrete objects and their associations using sets, relations, and functions, and explain their properties.
Main reading: Sets, relations, and counting: handle overlap and correspondence →
Explore the mechanisms
STEP 14Not started Induction, Recursion, and Invariants
Goal: Construct base and inductive steps to prove properties of natural numbers and recursively defined structures.
Main reading: Induction and loop invariants: explain why repetition is correct →
Explore the mechanisms
STEP 15Not started The Kernel, Privilege Modes, and System Calls
Goal: Explain the protection boundary between user and kernel modes and how a system call crosses it.
Main reading: The Kernel, Privilege Modes, and System Calls →
Explore the mechanisms
STEP 16Not started Virtual Memory, Page Tables, and the TLB
Goal: Split a virtual address into a page number and offset, and trace translation through page tables and the translation lookaside buffer.
Main reading: Virtual Memory, Page Tables, and the TLB →
Explore the mechanisms
STEP 17Not started Interleaving, Race Conditions, and Atomicity
Goal: Enumerate thread interleavings to detect race conditions and lost updates to shared state.
Main reading: Interleaving, Race Conditions, and Atomicity →
Explore the mechanisms
- Atomicity: choosing an indivisible operation
- Happens-before: causal and synchronization order
- Read memory ordering through publication and synchronization
- Check linearizability from invocation and response histories
- From unlinking a node to reclaiming it safely
- Design thread pools from slots, queues and dependencies
- Separate cancellation delivery from cleanup ownership
STEP 18Not started Mutexes, Semaphores, Condition Variables, and Deadlock
Goal: Trace state changes in mutexes, semaphores, condition variables, and monitors, and explain their different uses.
Main reading: Locks and condition variables: protect state and wait for change →
Explore the mechanisms
STEP 19Not started Syntax, Semantics, and Type Systems
Goal: Distinguish syntax, static semantics, and dynamic semantics, and explain the rules used to interpret a program.
Main reading: Syntax, semantics, and types: separate three kinds of correctness →
Explore the mechanisms
STEP 20Not started Compilers, Interpreters, Runtimes, and Garbage Collection
Goal: Trace lexical analysis, parsing, abstract syntax trees, intermediate representations, optimization, and code generation.
Main reading: Compilers, Interpreters, Runtimes, and Garbage Collection →
Explore the mechanisms
- From source characters to an expression tree
- Build a scanner for a small expression language
- Build and test a recursive-descent expression parser
- Evaluate an expression tree with an explicit environment
- Implement constant folding without hiding failures
- Manage value lifetimes with ownership and borrowing
- Garbage collection through reachability
- JIT optimization and deoptimization
- Observe allocation and escape analysis
- Types, ownership, and errors across an FFI
STEP 21Not started Formal Languages, Regular Expressions, and Finite Automata
Goal: Formalize alphabets, strings, and languages, and explain the connection between regular expressions and finite automata.
Main reading: Formal Languages, Regular Expressions, and Finite Automata →
STEP 22Not started Computability, Reductions, P, and NP
Goal: Use Turing machines and decision problems to distinguish computability, decidability, and undecidability.
Progress is kept in this browser for the current language. You can read the steps in any order.