# 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). ### Information Theory - *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:** 1. Discrete Mathematics (Rosen or Lehman/Leighton/Meyer + MIT 6.042) 2. Data Structures and Algorithms (Skiena + CLRS as reference + MIT 6.006) 3. Computer Architecture (Patterson and Hennessy + Nand2Tetris Part 1) 4. 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.