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

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

15 Answers 15

Reset to default
34
$\begingroup$

Probability Theory And Randomized Algorithms

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ This link is now dead. Could you please fix or it will be removed? $\endgroup$
    – Dave Clarke
    Commented 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
    Commented Feb 9, 2012 at 22:12
  • $\begingroup$ @DaveClarke The link is fixed. Yay! $\endgroup$
    – Jardine
    Commented 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.

Improve this answer
$\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$
    – Sadeq Dousti
    Commented Jan 5, 2011 at 16:38
  • $\begingroup$ @Sadeq: Sorry, no idea. $\endgroup$
    – Robin Kothari
    Commented 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:

Improve this answer
$\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.

Improve this answer
$\endgroup$
21
$\begingroup$

Information Theory

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is not available anymore. Can you share it with me. $\endgroup$
    – Sassy Math
    Commented Feb 11 at 18:12
17
$\begingroup$

PCP & Hardness of Approximation

Improve this answer
$\endgroup$
1
  • $\begingroup$ Which of them did you read yourself? $\endgroup$
    – Thomas Ahle
    Commented Mar 31, 2015 at 15:53
17
$\begingroup$

Discrete math

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ I get a 403 Forbidden error on your link. $\endgroup$
    – Derrick Stolee
    Commented Jan 12, 2011 at 19:11
  • $\begingroup$ @Derrick: The error is gone or the link is corrected. $\endgroup$
    – Sadeq Dousti
    Commented Jan 13, 2011 at 1:16
  • $\begingroup$ Yes, both links work now..... $\endgroup$
    – Derrick Stolee
    Commented Jan 13, 2011 at 4:39
  • $\begingroup$ Hence the link to the older version. $\endgroup$
    – Jeffε
    Commented 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$
    – darij grinberg
    Commented 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:

Improve this answer
$\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.

Improve this answer
$\endgroup$
14
$\begingroup$

Expander Graphs

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

Improve this answer
$\endgroup$
13
$\begingroup$

Computational Geometry

Lecture Notes by David Mount.

Improve this answer
$\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.)

Improve this answer
$\endgroup$
11
$\begingroup$

Combinatorial Optimization

Improve this answer
$\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.

Improve this answer
$\endgroup$
9
$\begingroup$

Spectral Graph Theory

Improve this answer
$\endgroup$

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