Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

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

16 Answers 16

Probability Theory And Randomized Algorithms

share|improve this answer
2  
This link is now dead. Could you please fix or it will be removed? –  Dave Clarke Feb 9 '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 9 '12 at 22:12
    
@DaveClarke The link is fixed. Yay! –  Jardine Jul 23 at 5:30

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.

share|improve this answer

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.

share|improve this answer
    
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 5 '11 at 16:38
    
@Sadeq: Sorry, no idea. –  Robin Kothari Jan 8 '11 at 6:02

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:

share|improve this answer

Information Theory

share|improve this answer

PCP & Hardness of Approximation

share|improve this answer

Discrete math

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

share|improve this answer
    
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 1:16
    
Yes, both links work now..... –  Derrick Stolee Jan 13 '11 at 4:39
    
Hence the link to the older version. –  JɛffE Jan 13 '11 at 7:15

Expander Graphs

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

share|improve this answer

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.

share|improve this answer

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:

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Maybe you need MIT Open Course ... There are necessary algorithms ...

MIT OPEN COURSE Video Lectures

share|improve this answer
9  
The question asked about lecture notes, and not video lectures!!! –  Dai Le Jan 4 '11 at 16:33
12  
Potayto, potahto. You have a problem with notes that move? –  JɛffE Jan 12 '11 at 18:16
    
I've never been cracked up by a comment on cstheory. Notes that move - I only thought you could hear or see them. Moving is a new twist. –  PhD Jun 15 at 2:16

Spectral Graph Theory

share|improve this answer

protected by Kaveh May 20 '13 at 13:23

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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