15-251: Great Ideas in Theoretical Computer Science

Spring Semester 2012

Taught by Ryan O'Donnell and Danny Sleator

Here are the lectures and notes presented during the course.

01 Intro, and Pancakes with a Problem slides notes
02 Proof Techniques for Computer Scientists slides notes
03 Axiomatic Systems and Logic slides
04 Proofs slides
05 Mathematical Games I: Nimbers slides notes
06 Mathematical Games II: Sums of Games slides
07 Counting I: Choice Trees and Correspondences slides
08 Counting II: Pascal, Binomials, and Other Tricks slides
09 Recurrences slides
10 Probability 1 slides
11 Probability 2 slides
12 Graphs I: Trees and Planar Graphs slides notes
13 Graphs II: Kruskal, Euler, Matchings, MSTs, Etc. slides notes
14 Matchings, and the Stable Marriage Problem slides notes
15 Number Theory and Modular Arithmetic slides notes
16 Cryptography and RSA slides
17 Group Theory slides notes
18 Polynomials slides notes
19 Linear Algebra slides notes
20 Random Walks slides
21 Countability and Diagonalization slides
22 Automata slides notes
23 Turing and Computability slides
24 Lambda Calculus slides n1 n2
25 Gödel’s Incompleteness Theorem slides
26 Complexity Theory slides
27 P vs NP slides
28 How Should we Vote? slides
29 Epilogue slides