#Computer Science Theoretical Foundation: A Reading List
For the working programmer who wants the science behind the craft.
This curriculum assumes you can already write software. You know C, Go, Python, and JS/TS. You run Arch, you patch suckless tools. What you want now is the theoretical machinery that separates engineering intuition from mathematical certainty.
#Phase 1: Foundations
The bedrock. Everything else builds on this.
#Discrete Mathematics
You need to be comfortable writing proofs, reasoning about graphs, and thinking combinatorially before anything else in this list will stick.
Primary text:
- Discrete Mathematics and Its Applications by Kenneth Rosen (8th ed). Comprehensive and methodical. Covers logic, proofs, sets, functions, relations, graph theory, combinatorics, number theory. The exercises are the point.
- Mathematics for Computer Science by Lehman, Leighton, and Meyer. The MIT 6.042 textbook, available free. More proof-focused and better written than Rosen in places.
Supplementary:
- How to Prove It by Daniel Velleman. If proofs feel shaky, start here.
- Concrete Mathematics by Graham, Knuth, and Patashnik. Not a first book. Come back after you have some combinatorics under your belt.
Course:
- MIT 6.042J Mathematics for Computer Science (OCW). Full lectures, problem sets, exams.
#Data Structures and Algorithms
Not interview prep. Rigorous analysis, correctness proofs, and understanding why algorithms work.
Primary text (choose one):
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (CLRS), 4th ed. The reference standard. Dense, encyclopedic, proof-heavy. Chapters 1-16 and 22-26 form the core.
- The Algorithm Design Manual by Steven Skiena, 3rd ed. More opinionated, more practical, better at building intuition about when to use what. Weaker on proofs than CLRS.
Recommendation: Start with Skiena for the intuition and narrative. Use CLRS as the rigorous companion and long-term reference.
Supplementary:
- The Art of Computer Programming by Donald Knuth. Volumes 1-3. You do not read TAOCP. You study it, slowly, over years. Start with Volume 1, Chapters 1-2.
- Algorithm Design by Kleinberg and Tardos. Excellent on algorithm design paradigms (greedy, divide-and-conquer, dynamic programming, network flow).
Courses:
- MIT 6.006 Introduction to Algorithms (OCW). Erik Demaine's lectures are exceptionally clear.
- MIT 6.046J Design and Analysis of Algorithms (OCW). Amortized analysis, randomized algorithms, approximation algorithms, network flow.
- Stanford CS 161 (Tim Roughgarden's lectures on Coursera as "Algorithms Specialization").
Project: Implement a balanced BST (red-black or AVL), a hash table with open addressing, a priority queue backed by a Fibonacci heap, and Dijkstra's algorithm using your priority queue. Do it in C. Prove the runtime bounds on paper before you code.
#Phase 2: Core Theory
The subjects that make computer science a science.
#Theory of Computation
Automata, formal languages, computability, and complexity. This is where you learn what computers cannot do.
Primary text:
- Introduction to the Theory of Computation by Michael Sipser, 3rd ed. Beautifully written, rigorous without being impenetrable. Part 1 (automata and languages), Part 2 (computability), Part 3 (complexity). Read it linearly. Do the exercises.
Supplementary:
- Computational Complexity: A Modern Approach by Arora and Barak. The graduate-level follow-up. Free draft online. Covers P vs NP, circuit complexity, probabilistic computation, interactive proofs, quantum computation.
- Automata and Computability by Dexter Kozen. More concise than Sipser, slightly more mathematical.
Course:
- MIT 18.404J Theory of Computation (OCW), taught by Sipser himself.
Papers:
- Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936). The founding document. More accessible than its reputation suggests.
- Stephen Cook, "The Complexity of Theorem-Proving Procedures" (1971). Introduces NP-completeness.
- Richard Karp, "Reducibility Among Combinatorial Problems" (1972). The 21 NP-complete problems.
#Computer Architecture
You write C and patch suckless software. Now learn what the hardware is actually doing.
Primary texts:
- Computer Organization and Design: The Hardware/Software Interface by Patterson and Hennessy (RISC-V edition). Covers ISA design, datapath, pipelining, memory hierarchy, I/O.
- Computer Architecture: A Quantitative Approach by Hennessy and Patterson, 6th ed. The graduate-level companion.
Supplementary:
- Computer Systems: A Programmer's Perspective (CS:APP) by Bryant and O'Hallaron, 3rd ed. The best book on how C maps to machine code, how the memory hierarchy affects performance, and how linking, exceptions, and virtual memory actually work. The labs are legendary.
- CODE: The Hidden Language of Computer Hardware and Software by Charles Petzold. Light reading for building intuition about how logic gates become computers.
Course:
- Nand2Tetris (nand2tetris.org). Build a computer from NAND gates up through an assembler, VM, compiler, and operating system. Part 1 is the essential one.
- MIT 6.004 Computation Structures (OCW).
Project: Complete Nand2Tetris Part 1. Then write a RISC-V disassembler in C.
#Operating Systems
You use Linux daily. Now learn the theory behind what the kernel is doing.
Primary texts:
- Operating Systems: Three Easy Pieces (OSTEP) by Remzi and Andrea Arpaci-Dusseau. Free online (ostep.org). The best modern OS textbook. Three sections: virtualization, concurrency, persistence.
- Operating System Concepts by Silberschatz, Galvin, and Gagne (the "Dinosaur Book"). The traditional alternative. Use as reference.
Supplementary:
- The Design and Implementation of the FreeBSD Operating System by McKusick, Neville-Neil, and Watson. A real production Unix kernel.
- Linux Kernel Development by Robert Love, 3rd ed. Practical kernel internals.
- The Design of the UNIX Operating System by Maurice Bach. The classic. Based on System V but the architectural ideas are timeless.
- Lions' Commentary on UNIX 6th Edition by John Lions. Line-by-line walkthrough of the original UNIX kernel source.
Course:
- MIT 6.828 Operating System Engineering (now 6.1810). Uses xv6. The labs have you implement parts of a real kernel. Gold standard OS course.
Papers:
- Dennis Ritchie and Ken Thompson, "The UNIX Time-Sharing System" (1974).
- Butler Lampson, "Hints for Computer System Design" (1983).
Project: Work through the xv6 labs from MIT 6.828. Then read the xv6 source in full (only about 6,000 lines).
#Phase 3: Systems Depth
Deeper dives. These can be pursued in parallel.
#Compilers
- Primary: Compilers: Principles, Techniques, and Tools by Aho, Lam, Sethi, and Ullman (the "Dragon Book"), 2nd ed. Lexical analysis, parsing (LL, LR, LALR), syntax-directed translation, intermediate representations, code generation, optimization.
- Alternative: Engineering a Compiler by Cooper and Torczon, 3rd ed. More modern, stronger on optimization.
- Practical: Crafting Interpreters by Robert Nystrom. Free online. Build two interpreters: tree-walk in Java, bytecode VM in C.
- Also: Modern Compiler Implementation in C by Andrew Appel.
- Course: Stanford CS 143 Compilers (Alex Aiken, available on edX/Coursera).
- Paper: Ken Thompson, "Reflections on Trusting Trust" (1984). The Turing Award lecture.
- Project: Build a compiler for a simple C-like language targeting x86-64 or RISC-V.
#Networking
- Primary: Computer Networking: A Top-Down Approach by Kurose and Ross, 8th ed.
- Deep: TCP/IP Illustrated, Volume 1: The Protocols by W. Richard Stevens.
- Sockets: UNIX Network Programming, Volume 1 by Stevens, Fenner, and Rudoff.
- Alternative: Computer Networks by Andrew Tanenbaum and David Wetherall, 6th ed.
- Course: Stanford CS 144 Introduction to Computer Networking. The labs have you build a TCP implementation from scratch.
- Project: Implement a minimal TCP stack in userspace. Or build an HTTP/1.1 server from raw sockets in C.
#Databases
- Primary: Database System Concepts by Silberschatz, Korth, and Sudarshan, 7th ed. Relational model, SQL, normalization, query processing, transaction management, concurrency control, recovery.
- Papers: Readings in Database Systems (the "Red Book") edited by Bailis, Hellerstein, and Stonebraker, 5th ed. Free online.
- Architecture: Architecture of a Database System by Hellerstein, Stonebraker, and Hamilton.
- Bridge: Designing Data-Intensive Applications by Martin Kleppmann.
- Course: CMU 15-445/645 Database Systems (Andy Pavlo). Full lectures on YouTube. The BusTub labs are excellent.
- Project: Build a simple relational database engine with a B-tree-backed storage engine, SQL parser, and basic query executor.
#Phase 4: Advanced Theory and Specialized Topics
#Programming Language Theory
- Structure and Interpretation of Computer Programs (SICP) by Abelson and Sussman, 2nd ed. Free online. Not a programming book. A book about computational processes, abstraction, and metalinguistic abstraction. Work through at least Chapters 1-4.
- Types and Programming Languages (TAPL) by Benjamin Pierce. The standard introduction to type theory. Lambda calculus, simply typed lambda calculus, subtyping, recursive types, polymorphism.
- Concepts, Techniques, and Models of Computer Programming by Van Roy and Haridi. Broader view of programming paradigms.
- Course: MIT 6.001 (the original SICP lectures by Abelson and Sussman, YouTube).
- Papers:
- Alonzo Church, "An Unsolvable Problem of Elementary Number Theory" (1936). Lambda calculus.
- Robin Milner, "A Theory of Type Polymorphism in Programming" (1978). Hindley-Milner type inference.
- Luca Cardelli and Peter Wegner, "On Understanding Types, Data Abstraction, and Polymorphism" (1985).
#Distributed Systems
- Designing Data-Intensive Applications by Martin Kleppmann. The entry point.
- Distributed Systems by Maarten van Steen and Andrew Tanenbaum, 4th ed. Free online.
- Distributed Algorithms by Nancy Lynch. The rigorous mathematical treatment.
- Course: MIT 6.824 Distributed Systems (now 6.5840). Robert Morris's course. The labs have you build a fault-tolerant key-value store using Raft.
Papers (essential reading):
- Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (1978). One of the most cited papers in CS.
- Leslie Lamport, "Paxos Made Simple" (2001). 14 pages and actually comprehensible.
- Diego Ongaro and John Ousterhout, "In Search of an Understandable Consensus Algorithm" (2014). The Raft paper.
- Eric Brewer, "CAP Twelve Years Later" (2012).
- Fischer, Lynch, and Paterson, "Impossibility of Distributed Consensus with One Faulty Process" (1985). The FLP impossibility result.
- Jim Gray, "The Transaction Concept: Virtues and Limitations" (1981).
- Elements of Information Theory by Cover and Thomas, 2nd ed. The standard graduate text.
- Information Theory, Inference, and Learning Algorithms by David MacKay. Free online. Connects information theory to ML and Bayesian inference.
- Paper: Claude Shannon, "A Mathematical Theory of Communication" (1948). One of the most important papers in the history of science.
#Cryptography
- Introduction to Modern Cryptography by Katz and Lindell, 3rd ed. Rigorous, proof-based treatment.
- Serious Cryptography by Jean-Philippe Aumasson. More practical.
- A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. Free online draft.
- Course: Stanford CS 255 (Dan Boneh, available on Coursera).
#Plan 9 Track
A separate track for the Plan 9 enthusiast. Plan 9 represents some of the most coherent systems design thinking ever produced.
#Essential Papers
- Rob Pike et al., "Plan 9 from Bell Labs" (1995). The overview paper. Everything is a file, per-process namespaces, network transparency.
- Rob Pike, "The Use of Name Spaces in Plan 9" (1992). How Plan 9's namespace mechanism replaces most of what UNIX uses mount points, environment variables, and symlinks for.
- Rob Pike et al., "The Styx Architecture for Distributed Systems." The 9P protocol is Plan 9's central abstraction.
- Sean Quinlan and Sean Dorward, "Venti: A New Approach to Archival Storage" (2002). Content-addressed archival storage.
- Rob Pike, "Systems Software Research is Irrelevant" (2000). Essential context for why Plan 9 matters.
- Charles Forsyth, "The Organization of Networks in Plan 9" (1995). Network stack as a filesystem.
#Plan 9 Documentation
- The Plan 9 Programmer's Manual (Volume 1 and 2). Available at plan9.io and 9p.io. Volume 2 contains the system papers.
- Introduction to Operating Systems Abstractions Using Plan 9 from Bell Labs by Francisco Ballesteros.
- cat-v.org archives. Extensive collection of Plan 9 documentation, papers, and cultural artifacts.
#Plan 9 Projects
- Install 9front on a VM or spare machine. Use it as a daily environment for a week. Write rc scripts. Use acme.
- Read the 9front kernel source. It is small enough to read in its entirety.
- Implement a 9P file server in C or Go.
- Study Go's design influences from Plan 9 (goroutines from Alef,
/proc filesystem influence, etc.).
#Foundational Papers Worth Reading
These shaped the field.
- Edsger Dijkstra, "Go To Statement Considered Harmful" (1968).
- Edsger Dijkstra, "The Humble Programmer" (1972). His Turing Award lecture.
- Edsger Dijkstra, EWD 1036 ("On the Cruelty of Really Teaching Computing Science").
- Tony Hoare, "An Axiomatic Basis for Computer Programming" (1969). Hoare logic.
- Tony Hoare, "Communicating Sequential Processes" (1978). CSP, which directly influenced Go's concurrency model.
- Fred Brooks, "No Silver Bullet" (1987). Essential and accidental complexity.
- Edgar Codd, "A Relational Model of Data for Large Shared Data Banks" (1970).
- Whitfield Diffie and Martin Hellman, "New Directions in Cryptography" (1976).
#Practical Projects That Reinforce Theory
| Project |
Theory Reinforced |
| Build a shell (in C) |
Process management, system calls, pipes, file descriptors |
| Build an assembler (Nand2Tetris or RISC-V) |
ISA, machine code, symbol resolution |
| Build a CPU in HDL (Nand2Tetris) |
Digital logic, computer architecture |
| Build a compiler for a C subset |
Lexing, parsing, type checking, code generation |
| Build a TCP stack in userspace |
Protocol design, state machines, networking |
| Build a key-value store with WAL |
Storage engines, crash recovery, B-trees |
| Build malloc |
Virtual memory, fragmentation, system calls |
| Implement Raft consensus |
Distributed systems, fault tolerance |
| Build a regex engine |
Automata theory, NFAs, DFAs, Thompson construction |
| Write a garbage collector |
Memory management, graph traversal, runtime systems |
| Build a simple OS kernel (xv6 labs) |
Scheduling, virtual memory, filesystems, interrupts |
| Implement RSA from scratch |
Number theory, modular arithmetic |
| Build a DNS resolver |
Protocol parsing, UDP, caching, recursion |
| Build a 9P file server |
Plan 9 philosophy, protocol design |
#Suggested Sequencing
Year 1:
- Discrete Mathematics (Rosen or Lehman/Leighton/Meyer + MIT 6.042)
- Data Structures and Algorithms (Skiena + CLRS as reference + MIT 6.006)
- Computer Architecture (Patterson and Hennessy + Nand2Tetris Part 1)
- CS:APP (Bryant and O'Hallaron), especially the labs
Year 2:
5. Theory of Computation (Sipser + MIT 18.404)
6. Operating Systems (OSTEP + xv6 labs from MIT 6.828)
7. Networking (Kurose/Ross + Stevens TCP/IP Illustrated)
8. SICP (work through Chapters 1-4)
Year 3:
9. Compilers (Dragon Book or Cooper/Torczon + Crafting Interpreters + build a compiler)
10. Databases (Silberschatz + CMU 15-445 labs)
11. Distributed Systems (Kleppmann + MIT 6.824 labs + the Lamport papers)
12. Programming Language Theory (TAPL)
Year 4 (ongoing, self-directed):
13. Information Theory (Cover and Thomas or MacKay)
14. Cryptography (Katz and Lindell + Boneh's course)
15. Advanced Algorithms (MIT 6.046 + Arora/Barak for complexity)
16. Knuth's TAOCP (ongoing, never finished, that is the point)
17. Plan 9 deep dive (papers, source reading, 9P server implementation)
#On Reading Papers
Do not just read textbooks. The papers listed above are where the ideas actually originated, and they are often clearer than the textbook treatments that came after. Start a paper reading habit: one paper per week, with notes. The two best aggregators are:
- Papers We Love (paperswelove.org). Community-curated collection with discussion groups.
- Adrian Colyer's The Morning Paper archives (blog.acolyer.org). A goldmine.
#A Note on Depth vs. Breadth
This list is long. You will not finish it. That is fine. The point is not completion. The point is that when you encounter a concept in your work, you know where to go for the rigorous treatment. The difference between a programmer and a computer scientist is not what they can build. It is what they can prove, what they can reduce, and what they know is impossible.