A Self-Learning, Modern Computer Science Curriculum

Table of Contents

1 Introduction

"The great idea of constructive type theory is that there is no distinction between programs and proofs… Theorems are types (specifications), and proofs are programs" (Robert Harper)

This guide is based on Carnagie Mellon's new curriculum, for reasons why they rewrote it from scratch see Robert Harper's blog and his follow up post on the success of the new material. The goal of this guide is to build up to a senior undergrad level in computer science with the necessary rigorous background in fundamentals to understand academic papers in journals to continue self-learning.

1.1 How Long Will This Take?

Depends on daily effort. Each entry is typically a class with about one semester worth of material and a regular undergrad student at any university will take 5 courses per semester with lectures 3 days a week for each course, and be assigned large projects plus multiple extra readings. Often these readings are entire texts, with the warning "exam questions from the assigned reading are fair game". Just make a commitment for one hour a day and see how far you get after a year. Because this guide almost exclusively uses functional programming you will write far less code and be able to complete a book like Parallel and Sequential Algorithms in one semester which would be impossible in an imperative language. The "functional" part in functional programming refers to mathematical functions, meaning functions where each input has a single output. This property then gives you referential transparency, immutability, and equational reasoning.

1.2 Build a Library (if you can't, use library genesis)

If you can, buy these books and start building yourself a library. Abe Books often has used copies, or global editions you can buy at significant discount. You will want them around for reference and it's good for motivation, you get books off your desk and into the display shelf and have a physical reference for your accomplishments. It also saves your eyes from the strain of screens. If you can't afford these then try libgen.io (Library Genesis) to get a pdf/epub.

1.3 How to Succeed

This anecdote by Cal Newport on how he was able to get the best grade in his Discrete Mathematics class involved him practicing proving every theorem given in the lectures and assigned reading over and over until he could comfortably pick randomly through his notes and prove something without assistance. The more deliberate practice you can do by completing the exercises and problem sets the faster you will complete this curriculum, since you will be able to skip review chapters and will spend less time working on problems as you will have gained mathematical maturity.

On Isaac Newton self-learning geometry:

"He bought Descartes' Geometry and read it by himself .. when he was got over 2 or 3 pages he could understand no farther, than he began again and got 3 or 4 pages father till he came to another difficult place, than he began again and advanced farther and continued so doing till he made himself master of the whole without having the least light or instruction from anybody" (King's Cam.,Keynes MS 130.10,fol. 2/v/)

2 Preliminaries

These are all optional of course if you are familiar with the material already.

2.1 Learn How to Learn

This is a waste of time if you just watch lectures, and try one or two exercises. You will get the illusion of learning. Do as many exercises as possible, and if the course page has old exams and quizzes absolutely do them. Teaching Assistants (TAs) exist in universities to give guidence to students correcting their errors and answer questions, which you don't have access to so use stack exchange instead. The only way to become an expert is learning from other experts.

2.2 Intro to Programming

If you've struggled with programming books in the past, worry not as this book/course has proven successs teaching a profoundly typed discipline to programming.

2.2.1 Alternative Intro

The Little Schemer series books are a Q&A format/Socratic method for learning the basics of recursion, types and other core ideas in Computer Science (read the Preface of each book). You can do the Little Schemer with pencil and paper.

  • (Book) The Little MLer - Matthias Felleisen, Daniel P. Friedman
    • Teaches you to think recursively, and provides an introduction to the principles of types, computation, and program construction.
    • Applies to any functional language, almost all the exercises can be done in OCaml or another language with a small amount of syntactic adjustment.

2.3 Elementary Mathematics Survey

Build a better foundation of elementary mathematics. Go through this mathematics reading list from Cambridge University and choose any books that interest you, the books by T.W. Körner provide excellent insight, and A Concise Introduction to Pure Mathematics by Martin Liebeck compliments the Stillwell book.

2.4 Calculus

Many courses listed here assume you have a basic Calculus background since all university students do, so often will have examples to provide insight using Calculus they expect you to be familiar with. It's also worth knowing Calculus for it's own sake, as the fundamental theorem of Calculus is a major breakthrough in terms of cultural importance and it's heavily used in all engineering disciplines and for finance and AI (stats), probability (integration), optimization (differentiation), analysis, and to further build mathematical maturity by learning to solve problems.

The best way to learn math is to just jump in and look up anything you come across you don't remember instead of going back to square one and redoing everything. If you don't remember cosine/sine then look up the tutorials on Khan Academy or any precalculus book and attempt the exercises in the calculus book instead of spending a week redoing elementary math. The more exercises you do the better you will get at this material and soon will no longer need any refresher material.

  • (Book) Calculus & Analytic Geometry - Thomas
    • You want the third or fourth edition from the 1960s. This Amazon comment explains the difference in the editions. The "Classic" edition is the second ed.
    • Various different printings exist, some split the book into 2 parts, other printings have both contained in one volume.
    • This is the book Don Knuth liked so much he chose Addison-Wesley as his publisher for The Art of Computer Programming series.
    • Alternatively read Calculus: Early Transcendentals by James Stewart which CMU uses.
    • See Common Errors in Undergrad Math like undistributed cancellations, sign errors, confusion about notation ect.

2.5 Intro to Mathematical Thinking

2.6 Problem Solving

"So I went to Case, and the Dean of Case says to us, it’s a all men’s school, “Men, look at, look to the person on your left, and the person on your right. One of you isn’t going to be here next year; one of you is going to fail.” So I get to Case, and again I’m studying all the time, working really hard on my classes, and so for that I had to be kind of a machine. In high school, our math program wasn’t much, and I had never heard of calculus until I got to college. But the calculus book that we had was (in college) was great, and in the back of the book there were supplementary problems that weren’t assigned by the teacher. So this was a famous calculus text by a man named George Thomas (second edition), and I mention it especially because it was one of the first books published by Addison-Wesley, and I loved this calculus book so much that later I chose Addison-Wesley to be the publisher of my own book. Our teacher would assign, say, the even numbered problems, or something like that (from the book). I would also do the odd numbered problems. In the back of Thomas’s book he had supplementary problems, the teacher didn’t assign the supplementary problems; I worked the supplementary problems. I was scared I wouldn’t learn calculus, so I worked hard on it, and it turned out that of course it took me longer to solve all these problems than the kids who were only working on what was assigned, at first. But after a year, I could do all of those problems in the same time as my classmates were doing the assigned problems, and after that I could just coast in mathematics, because I’d learned how to solve problems" (Don Knuth )

  • (Book) The Art and Craft of Problem Solving - Paul Zeitz
    • Any edition will do
    • Written by former coach of the US Math Olympiad team
    • First 3 chapters have excellent strategies, such as finding invariants, pigeonhole principal ect.
      • Other chapters are optional but are very relevant to all the material here
    • Alternative read Solving Mathematical Problems by Terence Tao for strategies

3 Fundamentals I: Mathematics Core

3.1 Recorded Lectures

Watch these as you do the book. The CMU lectures also cover some linear algebra and Complexity Theory while the MIT lectures are great for understanding induction.

3.2 Discrete Math with Standard ML

The merging of proof and program is what makes this a great book. ML syntax and concepts is similar to set notation, you really should get this book if you can. If you can't the MIT lecture notes for 6.042j will work as well combined with the recorded CMU/MIT lectures. You can also start 15-150 Principles of Functional Programming at the same time you start discrete math.

3.2.1 Additional Exercises to Build Mathematical Maturity

The more practice you have the better you will understand this material

  • Go through the lecture notes for both 15-251/6.042j and try to prove the example propositions and theorems yourself
  • Try the exercises in Concrete Mathematics for deliberate practice. It is an accessible (and rigorous) book to all levels of math backgrounds as Knuth is a good teacher.
  • Buy a used copy (any edition) of The Art of Computer Programming Vol 1: Fundamental Algorithms by Donald E. Knuth and try the exercises in 1.1 and 1.2.x chapters, and 2.3.4.x Basic Mathematical Properties of Trees

4 Fundamentals II: Abstraction

Functional programming languages support algebraic datatypes, and besides direct applications to CS this material will train your mind in building up and reasoning about abstractions.

4.1 Abstract Algebra I

4.2 Abstract Algebra II

  • (Full Course) Math-371 Abstract Algebra
    • Has recorded lectures which are essential as you can quickly get lost in the texts at this level of abstraction
    • Uses readings from three texts
      • There is also this Harvard course with excellent recorded lectures and uses readings from Algebra - M. Artin (blue book) as a great compliment to Math-371 lectures
    • Optional history of Abstract Algebra by Prof Lee Lady

4.3 Low Level Abstraction

"[Computer science] is not really about computers - and it's not about computers in the same sense that physics is not really about particle accelerators, and biology is not about microscopes and Petri dishes…and geometry isn't really about using surveying instruments. Now the reason that we think computer science is about computers is pretty much the same reason that the Egyptians thought geometry was about surveying instruments: when some field is just getting started and you don't really understand it very well, it's very easy to confuse the essence of what you're doing with the tools that you use." (Hal Abelson)

This covers computer architecture from a programmer's perspective, such as how to write cache friendly code, and other optimizations for the x86-64 arch. You learn how to manually write loops in assembly and see how recursion works at the lowest abstraction. You learn machine code instructions, return oriented programming to bypass stack protections, the memory hierarchy, and networks. You could read K&R's The C Programming Language for a brief intro, though this course will explain C as you go anyway and fully covers pointers at the assembly language level.

4.4 Meta-Linguistic Abstraction (Optional Elective)

This is optional but highly recommended. There's a package manager Guix and distro GuixSD. You configure packages, or your entire system with declarative programming in scheme (Guile), and can create full dependency graphs for exact reproduction on any other system. You can create containers that do not require taking snapshots of virtual file storage or keeping track of imperative state. GuixSD uses a scheme init system (GNU Shepherd), which means you get all the advantages of Guile's libraries/API and can completely abstract your system (or hundreds of servers) as just data to be manipulated in a program. Besides teaching wizardry SICP also fills in any first year CompSci gaps.

5 Fundamentals III: Functional Programming

5.1 Principles of Functional Programming

The 2012 version by Dan Licata has the best lecture notes, optionally combine with most recent course notes.

5.2 Introduction to Parallel and Sequential Algorithms

Design, analysis and programming of sequential and parallel algorithms and data structures in a functional pseudocode similar to Standard ML.

5.3 Programming Language Theory

Learn the fundamental principles to the design, implementation, and application of programming languages. Terence Tao article on formalism and rigor you want to be Stage 3: post rigorous stage where you can confidently reason with intuition because you have the necessary formal background.

5.4 Isolating Software Failure, Proving Safety and Testing

How to verify software, and strategies of programming that minimize catastrophe during failure.

  • (Book) Verified Functional Algorithms
    • Part 3 of the Deep Specifications interactive book series by Andrew Appel, learn by doing.
    • Assumes you have read these chapters of Software Foundations Part I: Preface, Basics, Induction, Lists, Poly, Tactics, Logic, IndProp, Maps, (ProofObjects), (IndPrinciples).
      • A good introduction to Dependent Types by Dan Licata is here

5.5 Designing Compilers (Optional Elective)

The labs have starter code files that aren't public, alternative is to read the recommended chapters from the Appel book and implement the Tiger language using the lecture notes as supplemental material. This material will really solidify your understanding of programming languages and is highly recommended.

5.6 Physical Systems Software Security (Optional Elective)

6 Fundamentals IV: Algorithms & Functional Persistent Data Structures, Complexity

6.1 Advanced Algorithms

Graduate level algorithms design course from Harvard with recorded lectures. Since you have (hopefully) already done the Parallel and Sequential Algorithms book, and some linear algebra you satisfy the prerequisites.

  • (Full Course) CS224 Advanced Algorithms
  • Pair this with Purely Functional Data Structures book by Chris Okasaki (the full book, not the thesis .pdf it's missing a lot of material)
    • Splay trees/heaps/binomial heaps/hashing ect are all in the Okasaki book as well as CS224
    • Compare both to see how to make data structures persistent
    • Also see the external links in this Wikipedia entry on persistent data structures for other material
  • Try the psets

6.2 Undergraduate Complexity Theory

Expands on the lectures in 15-251. This material glues everything you have learned up until now together into the big picture, and gives you an introduction to real theoretical computer science.

6.2.1 Graduate Complexity Theory (Optional Elective)

If you liked the above material, there's many resources to study Complexity Theory at the graduate level. You may even want to try solving one of the hard problems in this domain that doesn't have a lot of published papers.

7 You're Done the Fundamentals

7.1 Optional Extra Math

If you feel at this level there are gaps in your mathematical understanding, There is these scribed lecture notes that give you a diverse background in math useful for theoretical CS. There is also the book series Analysis I & II by Terence Tao to fill the gaps, you start at the very beginning, building up the naturals and reals. This book Real Analysis for Graduate Students by Richard Bass is a crash course in graduate Analysis/Probability/Topology that can help fill those gaps as well. Real (and Complex) Analysis has many applications to CS Theory.

7.2 How to Get Better at Programming

If you want to improve your skills in the trade/craft of programming here is some advice from Richard Stallman. You find a large open source project somewhere with active users, write a feature, then accept feedback from the users and more experienced project members. Repeat. Keep repeating until you build up your skills in reasoning and writing for programs people actually use. You could also get a job and learn directly from senior programmers. Jane Street Capital is a finance tech company that hires functional programmers worldwide, you may want to apply there, or any bio research lab would welcome your skills after completing the Parallel & Sequential Algorithms book. The test/debug methology of most industry programming consistently produces piles of junk software, so there are numerous opportunities to apprentice as a security researcher.

8 Graduate Research Elective: Type Theory

Read these slides from A Theorist's ToolKit on how to find research, how to write math in LaTeX, how to give a talk, where to ask on stackexchange ect.

8.1 Basic Proof Theory

8.2 Intro to Category Theory

8.3 Graduate Algebra Introduction

  • (Book) Algebra: Chapter 0 - Paolo Aluffi
    • Designed for self-learning, this is a fully self-contained, coherent treatment of graduate algebra with material from homological algebra
    • Tons of exercises, most very difficult but Aluffi is a great writer for demystifying Category Theory and Homology
      • Lectures on Algebraic Topology here to accompany the text (Homology intro, Groups ect).

8.4 Type Theory Foundations

8.5 Higher Dimensional Type Theory

Start with this talk A Functional Programmer's Guide to Homotopy Type Theory with intro to Cubical Type Theory

8.6 Further Research

  • The Type Theory podcast
  • Use the Sci-Hub proxy to get access to journals in Applied Logic or Functional Programming or visit a local library to ask for a printing, in a few cases the authors of a paper have a draft copy on their personal pages as well
  • Look up your closest university's event listings for the Mathematics or Computer Science departments to find seminars, these are open to the public usually and as stated in the intro you can only become an expert by learning from other experts
  • Try an advanced course in Modal or Substructural logic or Linear type theory
  • Follow the research on Cubical Higher Type theory as a programming language

9 Graduate Research Elective: Machine Learning

Read these slides from A Theorist's ToolKit on how to find research, how to write math in LaTeX, how to give a talk, where to ask on stackexchange ect.

9.1 Graduate Introduction to ML

  • (Full Course) 10-601 Masters Introduction to ML
    • Recorded lectures and recitations
    • Self contained, assumes you are grad level standing so have familiarity with basic probability and algebra
    • Prepares you in the foundations to understand journals and research papers
      • You may want to also take an introduction to Statistics like Penn State's Stat-500 or look at the Harvard Graduate Statistics Course family tree

9.2 Advanced Introduction to ML

9.3 Algorithms for Big Data

9.4 Further Research

  • The Journal of Machine Learning Research
  • Go to conferences, meet with experts, attend workshops
  • Open challenges in ML

10 Graduate Research Elective: Cryptography

Read these slides from A Theorist's ToolKit on how to find research, how to write math in LaTeX, how to give a talk, where to ask on stackexchange ect.

10.1 Graduate Cryptography Intro

This course covers post-quantum crypto, elliptic curve crypto, and is taught by premiere researcher Tanja Lange (TU/e)

10.2 Theoretical Cryptography

  • This 2 volume book The Foundations of Cryptography by Oded Goldreich
  • Lecture notes and recommended readings from 18.783 Elliptic Curves
  • Some good course notes on resource bound cryptography
  • Peruse the latest additions (books, lectures, papers) to the Number Theory Web and journals via Sci-Hub proxy
  • Attend the Theory of Cryptography Conference or look up previous years proceedings published by Springer through Sci-Hub

10.3 Applied Cryptography

  • Draft book A Graduate Course in Applied Cryptography - Dan Boneh and Victor Shoup
  • Lecture notes from 18-733 Applied Cryptography
  • Read all Daniel J. Bernstein's (and Peter Gutmann's) posts on the IETF Crypto Forum Research Group [Cfrg] archive, it's a master class in modern cryptanalysis and he rips apart bad standards/protocol/API designs.
  • Read The Art of Computer Programming - Seminumerical Algorithms by Knuth (Vol 2) chapter on Random Numbers. These same tests are still used in crypto grad courses. Try it on every library you can find that supposedly generates random numbers
  • Read about the proof of the Wireguard protocol, a VPN that uses AEAD_CHACHA20_POLY1305

10.4 Coding Theory

Whereas cryptography strives to render data unintelligible to all but the intended recipient, error-correcting codes attempt to ensure data is decodable despite any disruptions introduced by the medium.

10.5 Future Research

  • Follow whatever the PhD students of djb and Tanja Lange are working on
  • Watch the lectures from the 2017 Post-Quantum Crypto Summer School
  • Read the journal of Crypto Engineering (use SciHub proxy)
  • Read a book on Random Graphs there is a connection between Graph Theory and Cryptography
  • Try the Cryptopals challenges
  • Read about the libgcrypt (GnuPG) full key recovery for 1024-bit RSA keys (and ~1 in 8, 2048-bit keys) via L3 cache timing due to bad advice in 1990s crypto engineering handbooks.
  • Try and get into TU/e or other university graduate program, this is possible even if you don't have a bachelors degree

Author: jbh

Created: 2017-09-21 Thu 09:59