123
$\begingroup$

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

$\endgroup$
5
  • 10
    $\begingroup$ You get my vote. If only such a list had existed back when I was a student ... $\endgroup$ Jan 4, 2011 at 8:27
  • 7
    $\begingroup$ Thank you for the link to Jeff Erickson's excellent notes! $\endgroup$ Jan 4, 2011 at 9:16
  • 2
    $\begingroup$ Should then this question also be community wiki? $\endgroup$ Jan 4, 2011 at 9:41
  • $\begingroup$ @Dave: Yeah, I've already flagged it as CW. It requires mod attention. $\endgroup$ Jan 4, 2011 at 10:29
  • $\begingroup$ I wish I could upvote this more than once. $\endgroup$ Nov 1, 2013 at 11:42

15 Answers 15

34
$\begingroup$

Probability Theory And Randomized Algorithms

$\endgroup$
3
  • 2
    $\begingroup$ This link is now dead. Could you please fix or it will be removed? $\endgroup$ Feb 9, 2012 at 16:10
  • 5
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Feb 9, 2012 at 22:12
  • $\begingroup$ @DaveClarke The link is fixed. Yay! $\endgroup$
    – Jardine
    Jul 23, 2014 at 5:30
26
$\begingroup$

Quantum computation and information

Some excellent lecture notes from this field:

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.

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

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.

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

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 5, 2011 at 16:38
  • $\begingroup$ @Sadeq: Sorry, no idea. $\endgroup$ Jan 8, 2011 at 6:02
25
$\begingroup$

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:

$\endgroup$
23
$\begingroup$

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.

$\endgroup$
21
$\begingroup$

Information Theory

$\endgroup$
1
  • $\begingroup$ This is not available anymore. Can you share it with me. $\endgroup$ Feb 11 at 18:12
17
$\begingroup$

PCP & Hardness of Approximation

$\endgroup$
1
  • $\begingroup$ Which of them did you read yourself? $\endgroup$ Mar 31, 2015 at 15:53
17
$\begingroup$

Discrete math

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

$\endgroup$
7
  • $\begingroup$ I get a 403 Forbidden error on your link. $\endgroup$ Jan 12, 2011 at 19:11
  • $\begingroup$ @Derrick: The error is gone or the link is corrected. $\endgroup$ Jan 13, 2011 at 1:16
  • $\begingroup$ Yes, both links work now..... $\endgroup$ Jan 13, 2011 at 4:39
  • $\begingroup$ Hence the link to the older version. $\endgroup$
    – Jeffε
    Jan 13, 2011 at 7:15
  • 1
    $\begingroup$ Currently more up-to-date version: 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... $\endgroup$ Aug 1, 2015 at 13:53
15
$\begingroup$

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:

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

Expander Graphs

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

$\endgroup$
13
$\begingroup$

Computational Geometry

Lecture Notes by David Mount.

$\endgroup$
0
11
$\begingroup$

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

$\endgroup$
11
$\begingroup$

Combinatorial Optimization

$\endgroup$
2
9
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

Spectral Graph Theory

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.