 |
|
| Week | Date | Day | Lecture | Topic | Available | Due |
| 1 | Aug 25 |
M | Recitation 1 (Latex) | |||
| Aug 26 |
T | 1 (VA) | Pancakes with a Problem
Lecture slides [PDF] Notes on Pancakes |
|||
| Aug 28 |
R | 2 (VA) | Inductive Reasoning: One Step at a Time
Lecture slides [PDF] Notes on Induction: 1, 2, 3. Notes on common induction mistakes |
Hwk1 | ||
| 2 | Sep 1 |
M | NO CLASSES | |||
| Sep 2 |
T | 3 (VG) | Logic: Axiomatic Systems, Propositional Calculus, First Order Logic.
Lecture slides [PPS, PDF] Notes on Propositional Formulas Notes on first order logic |
|||
| Sep 4 |
R | 4 (VG) | Proofs
Lecture slides [PPS, PDF] Notes on proof methods |
Hwk2 | Hwk1 [Solutions] | |
| 3 | Sep 8 |
M |
Recitation 2 (Logic)
Solutions |
|||
| Sep 9 |
T | 5 (VG) | Counting I
Lecture slides [PDF] Notes on Counting |
|||
| Sep 11 |
R | 6 (VG) | Counting II.
Lecture slides [PDF] |
Hwk3 | Hwk2 [Solutions] | |
| 4 | Sep 15 |
M |
Recitation 3 (Counting)
Solutions |
|||
| Sep 16 |
T | 7 (VG) | Generating Functions
Lecture slides [PDF] Notes on generating functionss More notes on generating functions |
|||
| Sep 18 |
R | 8 (VG) | Combinatorial Games Lecture slides [PDF] Notes on Games |
Hwk4 |
Hwk3 [Solutions] | |
| 5 | Sep 22 |
M |
Recitation 4 (Generating Functions and Combinatorial Games) Solutions |
|||
| Sep 23 |
T | 9 (VA) | Probability - I Lecture slides [PDF] Notes on probability |
|||
| Sep 25 |
R | 10 (VA) | Probability - II
Lecture slides [PDF] Notes on random variables |
Hwk5 | Hwk4 [Solutions] | |
| 6 | Sep 29 |
M |
Recitation 5 (Probability) Solutions |
|||
| Sep 30 |
T | TEST 1
Practice Test [Solutions] |
||||
| Oct 2 |
R | 11 (VA) | Graphs - I Lecture notes [PDF] Notes on Graphs I Further notes on basics of graphs |
|||
| 7 | Oct 6 |
M | Recitation 6
(Graphs)
Solutions |
|||
| Oct 7 |
T | 12 (VA) | Graphs - II Lecture slides [PDF] Notes on Graphs II Notes on Planar Graphs |
Hwk6 | Hwk5 [Solutions] | |
| Oct 9 |
R | 13 (VA) | Graphs - III Lecture slides [PDF] |
|||
| 8 | Oct 13 |
M | Recitation 7
(Graphs)
Solutions |
|||
| Oct 14 |
T | 14 (VG) | Group Theory
Lecture slides [PDF] Notes on group theory |
|||
| Oct 16 |
R | 15 (VG) |
Fields, Polynomials
Lecture slides [PDF] Notes on polynomials, error correction |
Hwk7 | Hwk6 [Solutions] | |
| 9 | Oct 20 |
M | Recitation 8 (Polynomials and Groups)
Solutions |
|||
| Oct 21 |
T | 16 (VA) | Random Walks
[PDF] |
|||
| Oct 23 |
R | 17 (VG) | Error Correction Lecture slides [PDF] [PPS] Notes: Sections 5 here and here |
Hwk8 | Hwk7 [Solutions] | |
| 10 | Oct 27 |
M | Recitation 9 (Random Walks, Error Correction)
Solutions |
|||
| Oct 28 |
T | 18 (VG) | Public Key Cryptography Lecture slides [PDF] |
|||
| Oct 30 |
R | 19 (VA) |
Finite State Automata
[PDF] |
Hwk8 [Solutions] | ||
| 11 | Nov 3 |
M | Recitation 10 (Crypto and FSAs)
Solutions |
|||
| Nov 4 |
T | TEST 2
Practice Test [Solutions] |
||||
| Nov 6 |
R | 20 (VA) | Cantor's Legacy: Infinity And Diagonalization [PDF] | Hwk9 | ||
| 12 | Nov 10 |
M |
Recitation 11 (FSA)
Solutions |
|||
| Nov 11 |
T | 21 (VA) | Turing and Church's Legacy: The Limits of Computation [PDF] | |||
| Nov 13 |
R | 22 (VG) | Godel's Legacy: Truth vs. Proof
Lecture slides [PDF] |
Hwk10 | Hwk9 [Solutions] | |
| 13 | Nov 17 |
M | Recitation 12 (Turing Machines)
Solutions |
|||
| Nov 18 |
T | 23 (VG) | Efficient reductions
Lecture slides [PDF] |
|||
| Nov 20 |
R | 24 (VG) | P vs NP
Lecture slides [PDF] |
Hwk11 | Hwk10 [Solutions] | |
| 14 | Nov 24 |
M |
Recitation 13 (Reductions)
Solutions |
|||
| Nov 25 |
T | 25 (VA) | Approximation algorithms Lecture notes [PDF] |
|||
| Nov 27 |
R | No classes | ||||
| 15 | Dec 01 |
M | Recitation 14 (Solutions) ( ) | |||
| Dec 02 |
T | 26 (VG) | Interactive/Zero Knowledge Proofs Lecture slides [PDF] |
Hwk11 [Solutions] | ||
| Dec 04 |
R | 27 (VA) |
Epilogue/special topic
Lecture slides [PDF] |
|||