# A Self-Learning, Modern Computer Science Curriculum

## Table of Contents

- 1. Introduction
- 2. Preliminaries
- 3. Fundamentals I: Mathematics Core
- 4. Fundamentals II: Abstraction
- 5. Fundamentals III: Functional Programming
- 6. Fundamentals IV: Algorithms & Functional Persistent Data Structures, Complexity
- 7. You're Done the Fundamentals
- 8. Graduate Research Elective: Type Theory
- 9. Graduate Research Elective: Machine Learning/AI
- 10. Graduate Research Elective: Cryptography

## 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 theoretical computer science with the necessary rigorous background to understand academic papers in journals to continue self-learning.

### 1.1 Accreditation

If you are going to take all this material, why not get an accredited degree at the same time so you can pursue graduate studies later or just for extra motivation to complete the material on a regular schedule. Combine the free theoretical material here with any of the below programs.

#### 1.1.1 University of the People (UoPeople)

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 proctored 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 40 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. Both NYU and Berkeley will accept UoPeople courses for transfer into their BSc programs, and NYU has a scheme where some students are eligible to transfer from UoPeople to the NYU campus in Abu Dhabi with a full scholarship.

#### 1.1.2 Other Accredited Remote Programs

Open University(OU) in the UK offers Computer Science to students in the UK/EU and select other regions with testing centers. Other options include University of Illinois, Arizona State, University of Florida, and the nonprofit Western Governor's University which allows you to audit the material, if you wish to complete the degree faster. OU 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. Most of the above programs focus on applied software development, which doesn't matter as each course can be paired with one of the below recommendations for depth of theory should you wish to apply to a grad school after obtaining an undergrad. If you already have an undergrad degree in a different area, there are numerous online Masters programs available such as Georgia Tech's Computer Science MSc that mirrors most of the material here.

If you choose to enroll in any of the above, be sure to read Cal Newport's college guide to learn how to succeed by managing time and strategies for studying, such as Work Accomplished = Time x Intensity.

### 1.2 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 a few hours a day and see how far you get after a year. The most difficult part will be gaining mathematical maturity and doing the preliminaries, as you will not be used to doing hard work and concentration, the rest will be much easier. 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.3 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.4 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.

You may also want to learn to use emacs org-mode to organize your time. I found it essential to keep track of tasks and even for taking notes, since you can directly paste in code, slides and pdfs. Try some tutorials.

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.

- (Full Course) Learning How to Learn
- Optional course but highly recommended

- How to Study as a Mathematics Major - Lara Alcock
- How to read theorems and definitions, how to write proofs, how to study math
- How to read a research paper

### 2.2 Intro to Programming

This book/course has proven success teaching new students a profoundly typed discipline to programming. Really all you need is a good drilling in basic computation, and the Little Schemer series is perfect for this as they are exercises instead of passive reading.

- (Full Course) How to Code: Simple Data
- Based on the book How to Design Programs (HtDP)
- There is also a Masters level bootcamp to condense HtDP

- Some notes on editors and version control (git) and how to write a good commit comment
- Part two of the course is here and covers Backtracking and traversing graphs
- Optional sequel to HtDP is PAPL

- Based on the book How to Design Programs (HtDP)

#### 2.2.1 Alternative Intro

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,
the first in the series is *The Little Schemer* which teaches you the basics of 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.

### 2.3 Repair Your Deficiencies in Elementary Math

First, learn math intuitively. The Better Explained Math and Calculus book series is excellent at providing these skills, such as demystifying Trig identities.

Once you have a grasp of the intuition, the best way to fix all your deficiencies in manipulation of basic algebra is to jump into a first year calculus text and complete all the exercises. If you get stumped, refer to material such as Sheldon Axler's Precalculus book as it includes a solutions manual, where exercises are fully worked out instead of just providing a magic answer, also ask
questions/search math.stackexchange.com, or hire a tutor from a local university. The reason why all universities dump incoming students into three semesters of calculus is it's the best solution for reteaching math to students since they undoubtedly learned it incorrectly in most high schools. A typical first year
course will use the text *Calculus: Early Transcendentals* by Stewart which covers Single Variable, Multi-Variable and Differential Equations. I used Thomas' book instead, but it doesn't matter what text you use. What you want to be able to do is understand future material in this guide, such as the
summation notation in 15-213 Computer Systems to describe Two's Compliment, proofs by induction used in 15-150 Functional Programming and in discrete math texts, understand amortized analysis, and 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. Stewart's book has everything you need to do this or Thomas' text.

#### 2.3.1 Traditional Calculus Text

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. If you can't find Thomas' book any other free Calculus book will do, such as Gilbert Strang's Calculus or Stewart's book.

- (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. Covers Single, Multi-Variable and Differential Equations, Linear Algebra.
- 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).
- Watch Gilbert Strang's Highlights of Calculus for a survey of calculus and more intuition if necessary
- Read Common Errors in Undergrad Math like undistributed cancellations, sign errors, confusion about notation ect.

#### 2.3.2 Rigorous Theory of Calculus (Optional)

Math 2400/2410 course follows Spivak's book *Calculus*, which introduces students to single variable calculus done rigorously. This will be hard to do by yourself, you'll need to ask questions on stack exchange or hire a tutor even with the 3rd version solution guide available, as some of the
exercises are truly difficult. The preface of the course notes Honors Calculus, titled *Spivak and Me* detailing the writer's history of trying to teach Spivak to freshman students will explain how difficult the book can be.

The MIT course covers Apostol's book, which provides an absolute thorough drilling in university level mathematics for anybody who needs to clear up their skills in basic algebra. It's much more formal with definition, theorem, proof type style but this is how most math texts at this level are written. My recommendation is if you have been out of school for a while, or you struggle with math, do Apostol's two books and leave no exercises unfinished. I credit slogging through the first volume's exercises in building my mathematical maturity to a level where I could write proofs in later courses without making trivial mistakes, even if some of the exercises do become tedious, you'll thank yourself later when trig identities and algebra manipulation become second nature.

- Math 2400/2410 - Honors Calculus w/Theory
- Rigorous introduction to single variable, comes with full course notes Honors Calculus.
- Uses Spivak's
*Calculus*as additional reading, has you do some of the exercises, they are of course difficult - Pair with this excellent introduction to pure mathematics and Hammack's book of proof, use the Problem Solving section of this guide to consult Tao or Polya for strategies
- If you want a rigorous multi-variable text after finishing Stewart or Thomas, try Advanced Calculus or Apostol's
*Calculus Vol. 2*

- If you want a rigorous multi-variable text after finishing Stewart or Thomas, try Advanced Calculus or Apostol's

- 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!
- Very thorough, nothing is missed here in the exercises, they are gradual in difficulty as compared to Spivak's book.
- Pair with this excellent introduction to pure mathematics and Hammack's book of proof, use the Problem Solving section of this guide to consult Tao or Polya for strategies
- Part 2 of the course is here which covers
*Calculus, Vol. 2: Multi-Variable Calculus and Linear Algebra with Applications to Differential Equations and Probability*.

- Part 2 of the course is here which covers

- Uses Apostol's

### 2.4 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
- Optional book, 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.
- Alternative read
*Solving Mathematical Problems*by Terence Tao for strategies

- Alternative read

- (Wikipedia) How to Solve it - George Polya
- Summary on stragies in the book, optionally read whole book.
- There is also Descartes Discourse On the Method for a classical guide

- Summary on stragies in the book, optionally read whole book.

## 3 Fundamentals I: Mathematics Core

### 3.1 Recorded Lectures

Watch these as you do the Thomas VanDrunen book. The CMU lectures also cover some linear algebra and Complexity Theory. They are an excellent introduction to theoretical CS.

- CMU 15-251
*Great Theoretical Ideas in Computer Science*lectures and backup lectures and course notes - (Optional) MIT 6.042j
*Mathematics for Computer Science*lectures and course notes

### 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 (you should definitely get the book) the MIT lecture notes will work along with some kind of introductory material on Set Theory such as the free Book Of Proof or
these CMU prepared notes for an introduction to Pure Mathematics, with focus on active learning through exercises. Set theory will come up everywhere in future courses, like the cardinality of a finite set in relational databases. You can also start 15-150 *Principles of Functional Programming* at the same time you start discrete math.

- (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.
- Combine these chapters with the above recorded lectures by CMU/MIT.
- 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
- See Robert Harper's blog post on proof by contradiction
- Read Lambda Calculus: The Other Turing Machine

#### 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 reasoning about abstractions.

### 4.1 Abstract Algebra I

- (Book) Linear Algebra: An Introduction to Abstract Mathematics - Robert J. Valenza
- Focuses on the geometric intuition of linear algebra, surprisingly easy and straight-forward problem sets.
- These YouTube presentations here help with understanding the topics on a geometric level. Watch the Essence of Linear Algebra to see what this means
- These recorded lectures also focus on a more geometric understanding of linear algebra by Prof N J Wildberger and go well with the Valenza text
- Gilbert Strang also has a full Linear Algebra intro course here with recorded lectures
- Sheldon Axler additionally has recorded lectures for his Linear Algebra Done Right book, aka Down With Determinants! book.

### 4.2 Abstract Algebra II (Optional Elective)

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.

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

- There is also this Harvard course with excellent recorded lectures and uses readings from
- 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.

- (Full Course) 15-213 Intro to Computer Systems (CMU)
- Recorded lectures here
- 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 to not get lost in imperative programming.
- You can also do Unix programming in Standard ML(pdf)
- Try the embedded security CTF here after you finish the Attack Lab.

### 4.4 Data Abstraction

Abstracting data to model it however you want using advanced SQL with a standard relational dbms like SQLite.

- (Full Course) 15-445 Database Systems (CMU)
- Recorded lectures on youtube
- Uses readings from this book, assumes you have taken 15-213 and know some basic set theory
- Try this course with the small book The Reasoned Schemer which teaches you relational programming
- (Optional) An advanced class w/recorded lectures on building your own dbms

### 4.5 Meta-Linguistic Abstraction (Optional Elective)

This is optional but recommended to see the possibilities of abstraction you can attain within a language like Scheme. There's a 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 using an embedded DSL. Users, all their profile options, pre-installed packages, build options, file system setup and even which services to start are declared in one file and built in a clean container. 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. This enables transactional upgrades and roll-backs if something goes wrong. If you publish your local store (all the immutable packages you have built) then other users can use you as a substitution server to obtain pre-built binaries instead of having to build the same binary themselves. They can verify the build with guix challenge. This enables a p2p package manager, instead of relying on centralized repositories anybody can publish packages. Reproducible builds eliminate the use of signatures, TLS and all it's shortcomings. In addition, GuixSD uses a scheme init system (GNU Shepherd), which means you get all the advantages of Guile Scheme's libraries/API and can completely abstract your system (or hundreds of servers) as just data to be manipulated in a program since a full system configuration w/dependency graph can be a first-class Scheme value, a variable can be bound to your configuration and passed around a program. A recent GUixSD feature gexp (g-expressions) enables macros, allowing programmatically configured and maintained systems to be even easier to abstract and automate.

- (Full Course) 6.037 Structure and Interpretation of Computer Programs
- Recorded lectures from the first edition of SICP here
- Read the excellent forward from SICP on what programming is
- There is a unit test library for SICP as well as an online tutorial
- SICP in TeXinfo so you can read it in emacs
- Optional read: The Art of the Propagator for further adventures in symbolic programming

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

- (Lecture Notes) 15-150 Principles of Functional Programming
- "PSML Chapters" are assigned reading from this book Programming in Standard ML an excellent book that will teach you programming if you don't know it already.
- If you want pair these notes with the recorded lectures from Unit 1 through 4 (specific to SML) at CSE341 (UW)
- Do these homework assignments and labs plus any exercises you find in the PSML book. Try the CSE341 homework
- Note emacs setup also here (if you use emacs)
- Read this post about what recursion is if you struggle with it, complete The Little MLer or
*The Little Schemer*book- Try MLton, one of the few whole program optimizing compilers

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

- (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 (and difficult).
- This course covers higher-order programming (where functions are first-class values), a good introduction to this is
*The Seasoned Schemer*book- The Intuitive Guide to Data Structures and Algorithms helps to explain Big O notation and Logarithms in addition to the
*Parallel and Sequential Algorithms*book

- The Intuitive Guide to Data Structures and Algorithms helps to explain Big O notation and Logarithms in addition to the

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

- (Book) Practical Foundations for Programming Languages - Robert Harper
- Read these reasons for studying programming languages
- Recorded lectures to accompany the book Programming Languages Background — Robert Harper and Dan Licata
- More info on Judgements (logic) here and a series of recorded lectures here by Frank Pfenning on Basic Proof Theory but all this is self contained in the PFPL book
- Read these recitations and try the assignments here

### 5.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

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

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

- (Lecture Notes/Book) 15-411 Compiler Design
- Implement C0 (for background info, see 15-122 lecture notes or the specification of C0 which is a garbage collected C-like syntax language with an interpreter shell designed for teaching imperative language contracts
- Assumes you have done 15-213 so have knowledge of stack frames
- Uses the Andrew Appel book Modern Compiler Implementation in ML

### 5.6 Physical Systems Software Security (Optional Elective)

- (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 insight into calculus. Assumes you are somewhat familiar with invariants and programming via contracts

## 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 already done the *Parallel and Sequential Algorithms* book, and some linear algebra you satisfy the prerequisites. You want to go through the *Purely Functional Data Structures* book and match up the text with the lectures, all other lectures
are optional but this is an excellent course.

- (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 is 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 Useful Math for Theoretical CS

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 programming, 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

- Start with the lectures on
*Basic Proof Theory*by Frank Pfenning- These 15-317 Constructive Logic notes go with the seminar, there is another set here
- Read Martin-Löf's lecture notes

### 8.2 Intro to Category Theory

- (Book) Category Theory - Steve Awodey
- The most accessible introduction see errata, and recorded lectures by Steve Awodey here(HQ mp4) or here(YouTube)
- There is also this seminar
*Basic Category Theory: Semantics of Proof Theory*by Ed Morehouse- Also see this post here explaining Category Theory and as types in ML

- Notes on Categorical Logic

### 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, some 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) or use Algebraic Topology as a text

### 8.4 Type Theory Foundations

- Read Chapters 1-12, 23 and 24 from TAPL
- Watch seminar on
*Type Theory Foundations*by Robert Harper- Pair with Programming in Martin-Löf's Type Theory and the rest of the suggested reading

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

- (Full Course) Homotopy Type Theory
- Self-contained grad seminar with recorded lectures
- Assigns readings from self-contained HoTT book https://homotopytypetheory.org/book/
- Try the homework, see some of the open problems in HoTT research

- Self-contained grad seminar with recorded lectures

### 8.6 Further Research

- 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
- Try an advanced course in Modal or Substructural logic or Linear type theory
- Follow the research on Bob Harper's CMU page such as Cartesian Cubical Type Theory
- See CMU's Principles of Programming Group for more graduate course offerings
- See the POPL 2018 tutorial on Computational Higher Type Theory

## 9 Graduate Research Elective: 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.

### 9.1 Graduate Introduction to AI

- (Full Course) 15-780 Graduate Introduction to AI
- Recorded lectures here
- No formal pre-requisites, assignments are in Python.
- Also 15-659, Probability & Computing which compliments any class on AI.

### 9.2 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.3 Advanced Introduction to ML

- (Full Course) 10-701 PhD Introduction to ML
- Recorded lectures, provides a more in-depth treatment
- This 10-715 Advanced Introduction to ML also has recorded lectures

### 9.4 Algorithms for Big Data

- (Full Course) CS229r Algorithms for Big Data
- A grad level course in designing/analyzing algorithms for massive data.

### 9.5 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

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

- (Full Course) Masters Level Cryptology
- Recorded lectures here
- See djb's talks and papers from his personal site, and post-quantum crypto site

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

- A draft book on Coding Theory with some lecture notes

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