What Lecture Notes Should Everyone Read?

Question

There has been several questions with the same scheme as this one:

I was reluctant to post yet another one, but Jeff Erickson's lecture notes on algorithms changed my mind. I thought: Oh my! All these years and I haven't seen these excellent notes!

So, I thought there might be other great lecture notes, which are really worth reading. So, for each computer science subfield (data structures, algorithms, theory of computation, computational complexity, cryptography, etc.), recommend the superb lecture notes of your choice, and say why you think it excels.

One simple rule to keep it tidy: One answer per each subfield. (This will be a community wiki, so you can edit existing answers, and add your recommendation.)

You get my vote. If only such a list had existed back when I was a student ... — Anthony Labarre, Jan 04 '11 at 08:27
@Dave: Yeah, I've already flagged it as CW. It requires mod attention. — Sadeq Dousti, Jan 04 '11 at 10:29

score 34 · Answer 1 · edited Jun 17 '20 at 09:38

34

Probability Theory And Randomized Algorithms

Lecture notes from Ryan O'Donnell's course Probability and Computing is pretty neat.
Lecture notes from Amit Chakrabarti's course Data Stream Algorithms

edited Jun 17 '20 at 09:38

Community

1

answered Jan 04 '11 at 18:01

Nikhil

1,354
10
23

2

This link is now dead. Could you please fix or it will be removed? – Dave Clarke Feb 09 '12 at 16:10
5

@Dave, it seems there is no longer a link from Ryan's webpage to the course. But I don't think removing the entry is a good idea, he might put the link back at some point. Your comment that the link is broken is sufficient IMO. – Kaveh Feb 09 '12 at 22:12
@DaveClarke The link is fixed. Yay! – Jardine Jul 23 '14 at 05:30

score 26 · Answer 2 · edited Jul 30 '12 at 23:58

Quantum computation and information

Some excellent lecture notes from this field:

John Preskill's lecture notes on Quantum Computation.

An introductory course on quantum computing. Good enough to be made into a book. I know several researchers who have a printout of these notes on their bookshelf.

John Watrous' lecture notes on the Theory of Quantum Information.

An advanced course on quantum information. Some of the best lectures notes I've ever read.

Andrew Childs' lecture notes on Quantum Algorithms.

An advanced course on quantum algorithms. A very good resource for recent quantum algorithms. If the original paper on some quantum algorithm is hard to understand, this is where I would check next.

Scott Aaronson's lecture notes on Quantum Computing Since Democritus.

I can't summarize this course in one line. Read the description on the course web page.

Unruh's lecture notes on Quantum Cryptography.

Includes general introduction to Quantum Computing, as well as crypto-specific topics such as Quantum Key Distribution, Quantum Commitments, Bounded Quantum Storage Model, and Quantum Zero-Knowledge.

Very interesting, thanks. I always wanted to learn quantum computing, but didn't have enough time to read a book. Do you know any course devoted to quantum cryptography? I found one here, but unfortunately, the notes aren't available online. — Sadeq Dousti, Jan 05 '11 at 16:38

score 25 · Answer 3 · edited Jan 23 '17 at 04:51

Computational Complexity

There are many excellent courses on this topic. The following is merely the tip of the iceberg. To choose one, I suggest taking a look at the material covered in each course, as well as the level it is offered:

Introduction to Complexity Theory by Oded Goldreich. Available in two flavors: notes for a two-semester introductory course and notes for a single-semester course. You can also check Goldreich's book on computational complexity.
Two different Computational Complexity courses offered at Princeton by Sanjeev Arora and Boaz Barak. You can also check their book on computational complexity.
Complexity Theory by Eric Allender. Suggested by Boaz Barak at his homepage.
Complexity Theory by Luca Trevisan. Suggested by Boaz Barak at his homepage.
Advanced Complexity Theory by Madhu Sudan. Suggested by Boaz Barak at his homepage.
Lectures in Computational Complexity by Jin-Yi Cai. Written more or less in the form of a book.
Approaches to the P versus NP Question and Related Complexity Questions by Toniann Pitassi, with guest lectures by Steve Cook, Mika Goos, Joshua Grochow, David Liu, and Robert Robere. Graduate course covering many of the state-of-the-art lower bound techniques, several of which aren't well-covered (or covered at all) in other lecture notes.

score 23 · Answer 4 · edited Jan 04 '11 at 10:28

23

A Theorist's Toolkit by Sanjeev Arora.

I love these notes because it gives you a rather complete set of tools for attacking problems in complexity theory. For example, VC-dimension is used widely for proving lower bounds in the communication model, and these notes explains it so well and from the basics.

edited Jan 04 '11 at 10:28

Sadeq Dousti

16,479
9
69
152

answered Jan 04 '11 at 10:03

Marcos Villagra

3,290
27
45

Derrick Stolee · Answer 5 · 2011-01-04T20:39:59.800

21

Information Theory

Anup Rao's Information Theory lecture notes give a detailed description of the cutting-edge tools and how they are applied in recent research, including work from 2010.

edited Jan 04 '11 at 20:39

answered Jan 04 '11 at 18:24

Derrick Stolee

2,044
1
21
34

This is not available anymore. Can you share it with me. – Soham Chatterjee Feb 11 '24 at 18:12

score 17 · Answer 6 · edited Jan 11 '11 at 16:39

17

PCP & Hardness of Approximation

The course offered by Uri Feige is very good.
Another excellent course is offered by Luca Trevisan.
Yet another course is offered by Irit Dinur and Dana Moshkovitz. This one seems more like a link farm, and has few notes.
Limits of approximation algorithms : PCPs and Unique Games by Prahladh Harsha

edited Jan 11 '11 at 16:39

Holger

975
9
17

answered Jan 08 '11 at 17:23

Sadeq Dousti

16,479
9
69
152

Which of them did you read yourself? – Thomas Ahle Mar 31 '15 at 15:53

score 17 · Answer 7 · answered Jan 12 '11 at 18:21

17

Discrete math

Discrete Mathematics for Computer Science by Lehman, Leighton, and Meyer (older version)

answered Jan 12 '11 at 18:21

Jeffε

23,129
10
96
163

I get a 403 Forbidden error on your link. – Derrick Stolee Jan 12 '11 at 19:11
@Derrick: The error is gone or the link is corrected. – Sadeq Dousti Jan 13 '11 at 01:16
Yes, both links work now..... – Derrick Stolee Jan 13 '11 at 04:39
Hence the link to the older version. – Jeffε Jan 13 '11 at 07:15
1

Currently more up-to-date version: https://courses.csail.mit.edu/6.042/spring15/mcs.pdf . It feels like finding the right link amid the many outdated mirrors has become an NP-complete problem... – darij grinberg Aug 01 '15 at 13:53
@Jeffε I get a 403 Forbidden error on the first link. The link from the last comment is also password protected. However, this link might help: http://www.seas.harvard.edu/courses/cs20/MIT6_042Notes.pdf. – mehdix Jul 19 '16 at 22:37
Currently up-to-date version: https://courses.csail.mit.edu/6.042/spring17/mcs.pdf . Looks like a pattern has emerged in these links! – darij grinberg Jul 20 '17 at 15:04

score 15 · Answer 8 · edited Apr 13 '17 at 12:32

Cryptography

There are a number of excellent lecture notes on the subject, all by famous people in the field. You can choose one (or two) of the following to study; it all depends on your environment, background, and requirements:

Lecture Notes on Cryptography by Shafi Goldwasser and Mihir Bellare, 2008. A series of lectures for Cryptography and Computer Security [6.87s], a one week long course on cryptography taught at the MIT.
Advanced Topics in Cryptography, covering more advanced topics than ordinary courses.
Advanced Topics in Cryptography by Jonathan Katz, 2004. Covers an interesting range of topics in advanced cryptography. A more basic treatment can be found here.
(Suggested by Yasser): Yevgeniy Dodis's lectures on introductory and advanced cryptography.
Cryptography by Boaz Barak (2010).
Foundations of cryptography by Yehuda Lindell, 2010. Based on Goldreich's famous book.
Cryptography by Luca Trevisan. Luca's notes cover the basic topics very nicely.
Advanced cryptography by Daniele Micciancio. Covers lots of advanced topics, and is specially inclined towards secure multi-party protocols.
Introduction to Cryptography by Salil Vadhan. Good for beginner/intermediate level.

score 15 · Answer 9 · edited Apr 13 '17 at 12:32

15

Pseudorandomness

The best course on the subject is offered by Salil Vadhan. See also this topic for a draft of Salil's book on pseudorandomness.

edited Apr 13 '17 at 12:32

Community

1

answered Jan 08 '11 at 17:34

Sadeq Dousti

16,479
9
69
152

score 14 · Answer 10 · edited Apr 13 '17 at 12:32

14

Expander Graphs

The authoritative course is offered by Nati Linial and Avi Wigderson. See this topic for more information,

edited Apr 13 '17 at 12:32

Community

1

answered Jan 08 '11 at 17:30

Sadeq Dousti

16,479
9
69
152

score 13 · Answer 11 · edited Jun 17 '20 at 09:38

13

Computational Geometry

Lecture Notes by David Mount.

edited Jun 17 '20 at 09:38

Community

1

answered Jan 22 '11 at 23:38

Vinicius dos Santos

1,868
12
21

score 11 · Answer 12 · edited Jun 17 '20 at 09:38

11

Combinatorial Optimization

Chandra Chekuri's Topics in Combinatorial Optimization
Michel Goemans' Topics in Combinatorial Optimization
Lex Schrijver's A Course in Combinatorial Optimization
Jan Vondrak's Polyhedral techniques in combinatorial optimization

edited Jun 17 '20 at 09:38

Community

1

answered Nov 01 '13 at 04:50

Austin Buchanan

1,166
1
17
28

1

And Schrijver: http://homepages.cwi.nl/~lex/files/dict.pdf – Sasho Nikolov Nov 01 '13 at 05:13
1

Jan Vondrak's notes: http://theory.stanford.edu/~jvondrak/CS369P.html – Chandra Chekuri Apr 05 '14 at 17:57

Sacha · Answer 13 · 2011-01-04T10:05:22.713

11

SAT

I visited a SAT course a few years ago with Professor Welzl. His lecture notes are by far the best I’ve seen throughout my entire studies.

Unfortunately, only the 2005 version is online, including a short list of updates.

(The fastest SAT algorithm as well as the constructive proof of the Lovász local lemma come from guys in his group.)

edited Jan 04 '11 at 10:05

answered Jan 04 '11 at 09:10

Sacha

338
2
11

score 9 · Answer 14 · answered Apr 03 '12 at 18:14

9

Spectral Graph Theory

Spielman (Yale, 2009)
Chung (UCSD, 2010)

answered Apr 03 '12 at 18:14

user7545

251
4
8

score 9 · Answer 15 · answered Jan 21 '11 at 20:48

9

The course "Pearls of Algorithms". Part 3: Probabilistic Analysis and Randomized Algorithms. The lectures notes are on smoothed analysis. I especially like the figure 1.1 on the third page.

answered Jan 21 '11 at 20:48

Oleksandr Bondarenko

4,215
1
25
46

What Lecture Notes Should Everyone Read?

15 Answers15

Probability Theory And Randomized Algorithms

Quantum computation and information

Computational Complexity

Information Theory

PCP & Hardness of Approximation

Discrete math

Cryptography

Pseudorandomness

Expander Graphs

Computational Geometry

Combinatorial Optimization

SAT

Linked