Home

Calendar

Staff

Grades

FAQ

Policies
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]
   

© 2006-2014 Carnegie Mellon University, all rights reserved.