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 sample curriculum if you're interested in undergrad type theory, complexity theory, AI, ect., and you want really good (mostly free) resources to learn these fields so you can follow recent research papers. For reasons why CMU rewrote their curriculum from scratch to be more functional and parallel, see Robert Harper's blog and his follow up post on the success of teaching the new material. You're already familiar with functional programming from basic elementary math. 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.1 Accreditation

It's possible to gain a remote BSc part-time, if you want combine the theoretical material here with any of the below programs should you wish to later pursue graduate studies.

University of The People offers a fully online, US Distance Education Accrediting Commission(DEAC) accredited BSc in Computer Science that is tuition free. You pay an admission fee based on your countries GPA (typically $60), and $100 per exam so ~4k USD for a 4 year degree and they offer financial assistance. They have 5 terms per academic year, with F/T students taking 2 courses per term or P/T students taking 1 course per term. In total there are 11 proctored exams, and you can either ask somebody to be an exam proctor, or use a service like ProctorU, or just look up local universities in your area they often offer this service. Note they currently only have national accreditation, whereas some US graduate programs require regional accreditation. However grads from UoPeople grads have been accepted to foreign campuses since many US universities have multi-country partnerships offering the same accreditation, and the courses are taught in English.

Open University(OU) in the UK offers Computer Science to students in the UK/EU and select other regions with local testing centers. University of Illinois, Arizona State, University of Florida offer various accredited remote undergrads. Western Governor's University computer science program allows you to complete the courses at your own pace, so can finish a degree faster. Besides CS, Open University has some excellent Applied Mathematics degrees, such as the Applied Math w/Statistics BSc(Hons) available to any student worldwide if you want to take mathematics instead, using the material here for your theory of computation interests.

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 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 though sometimes the TeX typesetting looks like shit in digital copies. If your country blocks that domain use Wikipedia to find another one.

1.3 How to Succeed

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

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 until he could comfortably pick randomly through his notes and prove something without assistance. Deliberate practice may also be helpful.

2 Assumed Background

2.1 Intro to Programming

Any of the below introductions will work. If you think you'll be needing Python for scientific computing (such as AI/Machine Learning) then take the 15-112 course.

2.1.1 Optional Intro (Python)

  • (Course) 15-112 Fundamentals of Programming and Computer Science
    • Click on each lecture topic, there are short youtube videos explaining each topic.
    • The homework assignments are self-correcting, meaning they include assert statements so you can download a .py file, fill it in and check your work.
    • Really good source for programming style, algorithmic thinking, introduction to testing and exceptions.
    • Python everything is an object, and the standard library is filled with methods that have side affects. This may be confusing to you because it is confusing.

2.1.2 Optional Intro (Program Design)

This book/course has proven success teaching new students a profoundly typed discipline to programming.

2.1.3 Optional Intro (Little Schemer Series)

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 3 to 5 sittings. These are great books, that really drill the fundamentals of computation through active learning. The first in the series is The Little Schemer which teaches you recursion. The second is the Seasoned Schemer, a book on higher-order functions which will come in handy when you do the Parallel Algorithms book later. The Reasoned Schemer is a great book for learning relational programming (databases). The Little Prover will drill inductive proofs, excellent for when you take 15-150 Principals of Functional Programming. There is even A Little Java book to teach you the OOP paradigm should you ever find yourself in need to learn Java.

  • (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.
      • Some notes on editors and version control (git) and how to write a good commit comment in case you missed it from the other options.

2.2 Repair Your Deficiencies in 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 )

First, learn math intuitively. The Better Explained Math and Calculus book series is excellent at providing this intuition, such as demystifying trig identities.

After gaining intuition, the best way to fix all your deficiencies in basic math is to jump into a first year calculus text and complete all the exercises. Math, like programming, is learn by doing. If you get stumped, refer to Sheldon Axler's Precalculus book as it includes a solutions manual, where exercises are fully worked out instead of just providing an answer, also ask questions/search math.stackexchange.com, or hire a tutor from a local university. One reason why universities dump incoming students into three semesters of calculus is to reteach basic math to new students since they undoubtedly learned it incorrectly in most high schools. Calculus is also worth knowing for it's own sake as the fundamental theorem of calculus is a major breakthrough in terms of cultural importance and heavily used in all engineering disciplines and for finance and AI (stats), probability (integration), optimization (differentiation), estimation, ect.

2.2.1 Calculus

Most universities, including CMU use the text Calculus: Early Transcendentals by Stewart. I used Thomas' book instead, but it doesn't matter what text you use. This mathematics reading list from Cambridge University for new undergrads contains other excellent books, such as What is Mathematics? by Courant & Robbins, which will also teach you single variable calculus in addition to elementary college algebra. There is also Gilbert Strang's free book Calculus and a set of lectures, Highlights of Calculus to provide more intuition if necessary.

  • (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.
    • Covers the traditional Calc I, II and III course being Single, Multi and Differential Calculus (with introduction to Linear Albegra).

2.2.2 Calculus w/Theory (Optional)

Doing the many exercises in this text will help to fix all your problems with common trig identities and basic algebra mistakes. This is a great book for building mathematical maturity, as it's possible for somebody with questionable math background to complete, who is motivated to review prior material as they encounter it, though the introduction is a good crash course in most of the math you forgot since high school. At the same time this text is completely thorough, nothing is missed in the exercises and they are gradual in difficulty. If you are tired of calculus but still need to build maturity, meaning you wish to be familiar with definition, theorem, proof style texts you can use Hoffman and Kunze's Linear Algebra book instead. The amount of abstract algebra in their book is minimal, and all the background is provided so that the text is self contained.

  • MIT 18-014 Calculus w/Theory
    • Uses Apostol's Calculus, Volume 1: One-Variable Calculus, with An Introduction to Linear Algebra (buy the international version on Amazon for $20)
    • Course notes by Munkres!
    • You can purchase Apostol's Calculus, the 'Wiley Student Edition' or 'International Edition' on Amazon for $20. Get the second edition.

3 Discrete Mathematics Core

3.1 Introduction to Pure Mathematics

Sets, Relations, Real Analysis, Discrete Probability Theory, Number Theory, and mathematical reasoning.

3.2 Discrete Math with Standard ML

The merging of proof and program is what makes this a great book, turn sets into types in Standard ML

3.3 Introduction to Theoretical CS

3.3.1 Additional Exercises to Build Mathematical Maturity

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

  • Buy a used copy 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
    • The Mathematical Preliminaries chapter in TAOCP is a great crash course in discrete math, Knuth writes with excellent precision.

4 Functional Programming

4.1 Principles of Functional Programming

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

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

  • (Book) Parallel and Sequential Algorithms
    • Complete, self-contained book with exercises, check 15-210 course schedule for recitation pdfs and extra material
    • If you want to try the 15-210 labs clone this repository, read the lab handout pdf and just erase the answers and try them yourself, they are done in SML
    • This course covers higher-order programming (where functions are first-class values), a good introduction to this is The Seasoned Schemer book

4.3 Programming Language Theory

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

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

  • (Lecture Notes) 15-316 Software Foundations of Security and Privacy
    • Read about tests, strategies to safe program design (in OCaml), and proving safety
    • Clone this repository to get the full course w/homework assignments: github.com/jeanqasaur/cmu-15316-spring17.git
      • Content is erased after each semester, look up a previous year's content or wait for the start of a new semester.
  • (Book) Verified Functional Algorithms
    • Some recorded lectures by Andrew Appel here
    • Part 3 of the Deep Specifications interactive book series
    • 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
  • (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 insight into calculus.

5 Abstraction

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

5.1 Abstract Algebra I

5.2 Abstract Algebra II

Even if you don't plan on studying Type Theory you may want to take this course anyway, you really get a good insight into mathematical abstractions.

  • (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

5.3 Meta-Linguistic Abstraction

Learn the abstraction possibilities you can attain when writing programs. This material is best learned after you have some experience in programming.

6 Systems Programming

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

6.1 Introduction to Computer Systems

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.

  • (Course) 15-213 Intro to Computer Systems (CMU)
    • Recorded lectures here or see the course page above for youtube lectures
    • Get the CS:APP book, 3rd version used or the global version (the global version has a lot of errata, try to get the reg version with the memory mountain graph on the cover)
    • The labs (Data Lab, Bomb Lab ect) are on the book website
    • Read this post on Boolean Blindness
      • Try the embedded security CTF here after you finish the Attack Lab

6.2 Operating Systems

7 Database Systems

  • (Course) 15-445 Database Systems
    • Recorded lectures on youtube
    • Uses readings from this book, assumes you have taken 15-213 Introduction to Computer Systems and know some basic set theory such as the cardinality of a finite set.
      • (Optional) An advanced class w/recorded lectures on building your own dbms, covers the implementation of Peloton

8 Designing Compilers

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. As an example of what you can do with this material, the webAssembly interpreter is written in OCaml, and ReasonML (or OCaml) can compile to javascript.

9 Functional Persistent Data Structures

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

10 Complexity Theory

10.1 Undergrad level Complexity Theory

10.2 Graduate level Complexity Theory

You may want to try solving some of the problems in this domain that doesn't have a lot of published papers.

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

11.1 Basic Proof Theory

  • These lectures on Basic Proof Theory by Frank Pfenning if you haven't already done the Foundations of Programming Languages book earlier

11.2 Intro to Category Theory

11.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, some difficult but Aluffi is a great writer for demystifying Category Theory and Homology
      • Some optional lectures on Algebraic Topology here for more advanced Algebra (Homology intro, Groups ect) that uses Algebraic Topology as a text

11.4 Type Theory Foundations

11.5 Higher Dimensional Type Theory

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

11.6 Further Research

12 Artificial Intelligence

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.

12.1 Graduate Introduction to AI

12.2 Applied Introduction to Data Science/ML

  • (Course) 15-388 Practical Data Science
    • Includes recorded lectures, uses Python
    • Focus is mainly on applying techniques from existing libraries to practical data science problems, and understanding some of the underlying algorithms

12.3 Graduate Introduction to ML

  • (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 research papers in ML
      • 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

12.4 Advanced Introduction to ML

12.5 Algorithms for Big Data

12.6 Further Research

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

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

13.1 Graduate Cryptography Intro

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

13.2 Theoretical Cryptography

13.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 the tests 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

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

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