A Self-Learning, Modern Computer Science Curriculum

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 is a collection of modern resources on various undergrad level computer science topics, for someone with an interest in theory. Use LibGen if you can't buy these books. You don't have to do everything here, just the topics of interest to you. Almost all the material in each resource is self contained so will cover necessary background but being these resources are university level they will assume the student to be familiar with calculus. See 2 section.

1.1 Accreditation

It's possible to earn an accredited BSc degree online if you want to attend a graduate school to do research. University of The People offers a BSc in Computer Science, and is the cheapest fully remote option. UoPeople is only accredited nationally in the US, but there exists worldwide degree granting campuses to get around the regional accreditation requirement of US grad schools. UoPeople is structured with 5 terms per academic year, with F/T students taking 2 courses per term or P/T students taking 1 course per term. Open University(OU) in the UK offers Computer Science to students in the UK/EU and select other regions with testing centers, and other degrees like Applied Math w/Statistics BSc(Hons) worldwide. The University of Illinois, Arizona State, University of Florida, and Western Governor's University are some of the schools that offer US regionally accredited fully online degrees. Before you apply to any of these schools, research them to make sure they are financially sound so won't disappear half way through your degree, and that the type of accrediation they offer will work for your future plans. Also consider free tuition for international students in countries like Germany.

An alternative strategy if the goal is grad school: do the theory courses here, contact graduate programs asking if they allow non-degree students to take their classes. Taking classes as a non-degree student will let you build up a formal academic background with recommendation letters in your chosen field to make this direct entry to PhD possible but of course you will have to pay for these classes yourself. Prepare a proper grad school application and remember this is a big risk for a department, especially if the department you're applying to is small and therefore needs to be more selective in who they admit. Anything you can do to show that you won't be a risk for them in your letter of intent will help your application.

1.2 How to Learn

On Isaac Newton's iteration method to self-learn 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/)

Cal Newport has some anecdotes on how he was able to get the best grade in his Discrete Mathematics class, and the rest of the site is full of advice on studying, how to schedule yourself and deliberate practice. Further anecdotes exist on the importance of deep work and deliberate practice. There is a free course Learning How to Learn on coursera.org which suggest the same techniques plus Cornell style note taking and how to read a research paper. Attempt as many psets, textbook exercises, and any old exams you can to verify to yourself you understand the material.

2 Preliminaries

If you live near or wish to vacation to Raleigh NC (or possibly remote, ask him), for $500 (or see group rates when available) per course, you can hire this former CMU professor to teach you directly as a guided tutor introductory computer science regardless of your educational background covering functional data structures and other topics. Some of this material exists in lecture notes here from when he taught 15-122 Principles of Imperative Computation. I did have access to the lecture recordings at one point before they got paywalled and they are fantastic. It's a steal for only $500 to have a PhD give you guided personal instruction.

2.1 Intro to Programming

Any of these options will suffice you don't have to do every resource.

2.1.1 Common Lisp Intro

It's possible to do (or at least model) every course in this list using Common Lisp, such as building your own domain-specific machine code while completing 15-213 Computer Systems, or hacking together purely functional data structures, or writing your own pattern matcher, or simulating a turing machine, ect. Of course you will do the courses using their recommended languages and tools, but in addition to this, building your own toy prototypes for the topics here in CLisp can help you learn this material as per this axiom3.1 "people learn more when they discover something for themselves than they do if someone tells them about it." Another reason is the language hasn't changed much in decades, so older books which are now free, can be used.

2.1.2 Little Schemer

The Little Schemer series books are a Q&A format/Socratic method for learning the basics of computation (read the Preface of each book). You can do the Little Schemer with pencil and paper in a weekend though the authors recommend at least 3 sittings. The first in the series is The Little Schemer which teaches you to think recursively. The second is the Seasoned Schemer covering higher-order functions, which will help understand calculus. The differential operator is a higher-order function: given a function on the real line it yields its first derivative as a function on the real line.

  • (Book) The Little MLer - Matthias Felleisen, Daniel P. Friedman
    • Self contained but will make much more sense if you've already done the first book, The Little Schemer covering cons, lists and recursion.
    • 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.1.3 CMU's Fundamentals of Programming

Students who go directly to this course already have a background in programming. I did this course in Common Lisp, using a simple wrapper for tcl/tk similar to Python's tkinter and wrote my own toy data structures as they were explained. Good information here on style, design and efficiency, with an introduction to complexity.

2.2 Elementary Math

"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 )

Start with Po-Shen Loh's new site Expii.com which presents topics in a brief intuitive manner, then feeds you problems in that domain and makes decisions based on your answers if you need more practice problems. The Advanced Topics have all kinds of great tutorials on CS Theory as well as Number Theory. While you go through Expii, do a survey of The Better Explained Math and Calculus series books, which explain basic math such as the natural logarithm then you can practice Calculus on Expii. Gilbert Strang also has a lecture series Highlights of Calculus for more intuition and a free book.

2.3 Calculus With Theory

Optional, though doing the exercises of Apostol's Calculus I however is a great way to build mathematical maturity. This alternative Calculus w/Theory lecture series only uses a simple algebraic framework, eliminating limits/infinity. Linear algebraic ideas and the Discrete Calculus are both highly relevant to the material here. There is also a full course available.

3 Discrete Mathematics

Resources to learn undergrad Discrete Mathematics.

3.1 Introduction to Pure Mathematics

  • (Book) An Infinite Descent into Pure Mathematics
    • Collection of excellent lecture notes used in CMU's 15-151/21-127 Concepts of Mathematics class
    • Curriculum based on findings in evidenced based teaching
    • Author's motivations for not including answers are explained here: "people learn more when they discover something for themselves than they do if someone tells them about it."
      • You may also find as you write your questions on math.stackexchange, that half way through writing you discover the answer yourself

3.2 Discrete Math with Standard ML

The merging of proof and program is what makes this a great book. If you can't get this book Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi is normally used or just skip to 15-251 Great Theoretical Ideas in CS

  • (Book/Lectures) Discrete Mathematics and Functional Programming - Thomas VanDrunen
    • Lectures exist on the author's homepage, this book is used for a one semester university course with additional elective chapters in Graph Theory, Complexity Theory, Automata, ect.
    • List of Common Errors in Undergrad Math like undistributed cancellations, sign errors, confusion about notation ect. if you missed it from the prelims section of this guide
      • The Art of Computer Programming Vol 1: Fundamental Algorithms by Donald E. Knuth also offers an excellent crash course in Discrete Math in the 1.1 and 1.2.x chapters.

3.3 Rigorous Introduction to Computation

15-251 assumes students have completed An Infinite Descent into Pure Mathematics though it is self contained. "This course teaches the mathematical underpinnings of computation and explores some of the central results and questions regarding the nature of computation."

4 Abstract Algebra

It is possible in a functional language like SML to do algebra with types, proving two types are isomorphic with the desired properties of reflexivity, symmetry, and transitivity. It's also possible to abstract Lists and Trees into polynomials, as every polynomial looks like a sum of terms. As you will learn in 15-150 Principles of Functional Programming "most functional datastructures have constant time access near the outer layer of their structure, ie: the head of a list or the root of a tree. However, access at some random point inside the structure is typically linear since looking at some element of a list is linear in the length of the list, and looking at some element of a tree is linear in the depth of the tree. Datatype derivatives allow constant time access to the entire structure."

4.1 Linear Algebra

Though Apostol's Calculus has an excellent introduction to Linear Algebra, these resources focus more on mathematical abstraction.

4.2 Abstract Algebra

  • (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
    • The history of Abstract Algebra by Prof Lee Lady

5 Principles of Functional Programming

The "functional" part in functional programming refers to mathematical functions, meaning functions where each input has a single output. The 2012 version by Dan Licata has the best lecture notes, optionally combine with most recent course notes. Robert Harper keeps a blog and a follow up post on the success of teaching this course. SML is used because it's syntax and module system is simple, much like Scheme's easy syntax was once preferred for introductory courses so the complexity of the language gets out of the way and you learn the fundamentals. This course introduces you to programming with types, proving properties of programs, writing programs for parallel evaluation, and you'll find it surprisingly very intuitive making it easy to grok large programs.

6 Computer Systems

"[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 a lower abstraction. You learn machine code instructions, how compilers work, return oriented programming (ROP) 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 making it self contained.

7 Database Systems

Interesting post on the future of database systems by Andy Pavlo.

8 Meta-Linguistic Abstraction

A classic introductory computer science book on thinking about the big picture of programs with abstraction: finding general patterns from specific problems and building programs based on these patterns. An applied example of this is the package manager GNU Guix and distro GuixSD, which is a GNU implementation of the NixOS functional software deployment model. Package builds, including entire system builds, are declared in one text file. The resulting software deployment is functional: build inputs go in such as compilers, customizations, environments ect, and a reproducible, immutable build comes out with a hashed identifier meaning you can do roll backs to previous successful builds. A recent GUixSD feature gexp (g-expressions) is a good example what can be achieved through syntactic extensions of the Scheme language.

You are more likely to benefit from this book after having some programming experience, but no matter what level of programmer you are you'll still benefit from SICP.

9 Programming Language Theory

Read these reasons for studying programming languages.

10 Isolating Software Failure, Proving Safety and Testing

How to verify software, and strategies of programming that minimize catastrophe during failure. The Little Prover is a good introduction in determining facts about computer programs. Prof Rob Simmons can be hired as a tutor to teach you Coq, the curriculum follows the Software Foundations book series below.

  • (Book) Verified Functional Algorithms
    • Some recorded lectures by Andrew Appel here
    • 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

10.1 Physical Systems Software Security

  • (Full Course) 15-424 Foundations of Cyber-Physical Systems
    • Course (with recorded lectures) if you're interested in programming drones/space shuttles/robots/cars and other things that cannot fail from avoidable errors.
    • Self contained, will teach you differential eq but assumes you already have some calculus background.

11 Algorithms

11.1 Introduction to Parallel and Sequential Algorithms

Unlike a traditional introduction to algorithms and data structures, this puts an emphasis on thinking about how algorithms can do multiple things at once instead of one at a time and ways to design to exploit these properties. It uses a language based analysis model to estimate complexity for abstractions such as garbage collection. Most of the self learning and discovery is done through the labs, try them.

11.2 Advanced Algorithms (Purely Functional Data Structures)

The typical text for a senior undergrad or graduate course on algorithm analysis is The Design and Analysis of Algorithms by Kozen (1992). This is an excellent book to study with difficult problems well presented and clearly analyzed by Kozen. The Okasaki book (1999), Purely Functional Data Structures gives examples in Standard ML and Haskell.

12 Complexity Theory

12.1 Undergraduate Complexity Theory

Expands on the lectures in 15-251.

12.2 Graduate Complexity Theory

You may want to try solving some of the problems in this domain.

12.3 Useful Math for Theoretical CS

These scribed lecture notes give you a diverse background in math useful for theoretical CS, from the excellent book The Nature of Computation such as these slides from A Theorist's ToolKit which describe how to find research, how to write math in LaTeX, how to give a talk, resources on math.overflow ect.

13 Practical Data Science

  • (Full Course) 15-388 Practical Data Science
    • Provides a practical introduction to the “full stack” of data science analysis: data collection and processing, data visualization and presentation, statistical model building using machine learning, and big data techniques for scaling these methods.

14 Jobs

This service matches your skills to people who want to pay you. Jane Street Capital is a finance tech company that hires functional programmers worldwide, you may want to apply there. There are numerous opportunities to apprentice as a security researcher or get paid to prove business logic programs like 'smart contracts'. Check your local university employment listings as well, often students do not take these jobs as they are off chasing that startup stock options payday or doing industry internships, plenty of opportunities to work with post-doc researchers writing algorithms or analyzing data. An indirect strategy is apply to customer support roles, and get yourself involved in software development or design while working as a CSR to move departments. Finally, you can be hired directly from mailing lists by working on open source projects. Somebody likes your knowledgable replies on the mailing list or Github Issues list and may offer you a job.

15 Graduate Research in 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.

15.1 Basic Proof Theory

15.2 Intro to Category Theory

15.3 Type Theory Foundations

15.4 Higher Dimensional Type Theory

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

15.5 Further Research

16 Graduate Research in Machine Learning/AI

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.

16.1 Graduate Introduction to General AI

These notes here cover more topics, such as Computer Vision/NLP/AGI and follows AI: A Modern Approach book by Norvig. The 15-780 course is specific to some topics in AI providing them 2-3 lectures each.

  • (Full Course) 15-780 Graduate Introduction to AI
    • Recorded lectures here and here
    • No formal pre-requisites except grad level standing so familiar with some undergrad calculus and linear algebra/probability
      • MIT's Artificial General Intelligence free class explores possible research paths for creating AGI
      • Sussman had a great 2017 grad course reviewing older paper with unsolved problems or deep ideas, like his own Art of the Propagator paper and implementation
      • AI readings to explain intelligence from a computational point of view

16.2 Math Background for ML

A series of recorded lectures and recommended texts for a crash course in the Math background for ML introductory courses

16.3 Statistics Theory

  • (Full Course) 36-705 Intermediate Statistics
    • Recorded lectures and reading cover the fundamentals of theoretical statistics
    • The probability prereqs can be found here or from any undergrad text on probability
    • Additional lecture notes on the intersection of stats theory and ML
      • An advanced statistics theory book relevant to ML: High-dimensional statistics: A non-asymptotic viewpoint by M. Wainwright (no preprint draft, though some copies are floating around if you search)

16.4 Graduate Introduction to ML

16.5 Advanced Introduction to ML

  • (Full Course) 10-715 Advanced Introduction to ML
    • Most recent version here uses mostly the same recorded lectures.
    • Fast paced curriculum intended to prepare PhD students in the ML grad program to write research papers
    • Some slides on the practical techniques needed for working with large datasets
      • Linear Algebra review crash course w/recorded lectures here relevant to optimization/ML
      • Real Analysis review here
      • Probability lecture notes
  • (Full Course) 10-701 Introduction to ML
    • Intended for PhD students outside the ML program, more theory and rigor than 10-601
    • Assumes you have this16.2 math background
    • Some recorded recitations are here
      • Some slides on the practical techniques needed for working with large datasets

16.6 Convex Optimization

16.7 Deep Learning

If you're interested in parallel GPU programming for training see these lectures and notes.

16.8 Algorithms for Big Data

16.9 Further Research

  • The Journal of Machine Learning Research and other AI journals you can access with Sci-Hub
  • Open challenges in ML
  • Algorithmia.com an open marketplace for AI algorithms

17 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.

17.1 Graduate Cryptography Intro

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

17.2 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 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

17.3 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 some cryptocurrency papers, such as Stellar's Consensus algorithm (soon to be used by mobilecoin.com), Fail-Safe Network or the protocol specification for Zcash.