
Week  Date  Day  Lecture  Topic  Available  Due 
1  Jan 11 
M  Recitation 1  
Jan 12 
T  1 (D) 
Pancakes with a Problem [ PPT  PDF ]  Hwk1  Warmup Sols  Solutions  
Jan 14 
R  2 (V) 
Inductive Reasoning [ PPT  PDF ]  
2  Jan 18 
M  No Recitations!  
Jan 19 
T  3 (D) 
Ancient Wisdom: Choose Your Representation, Unary and Binary [ PDF ]  Hwk2  Warmup Sols  Solutions  Hwk1  
Jan 21 
R  4 (V) 
Counting I: Choice Trees and Correspondences
[
PPT 
PDF
]
Quiz 1 

3  Jan 25 
M  Recitation 2
Recitation 2 Solutions 

Jan 26 
T  5 (V) 
Counting II: Pascal, Binomials, and Other Tricks [ PPT  PDF ]  Hwk3  Warmup Sols  Solutions  Hwk2  
Jan 28 
R  6 (V) 
Counting III: Counting with Generating Functions [ PPT  PDF ]  
4  Feb 1 
M  Recitation 3
Recitation 3 Solutions 

Feb 2 
T  7 (A) 
Solving Recurrences with Generating Functions [ PPT  PDF ]  Hwk4  Warmup Sols  Solutions  Hwk3  
Feb 4 
R  8 (V) 
Recurrences and Continued Fractions Quiz 2 [ PPT  PDF ] 

5  Feb 8 
M  Recitation 4: CANCELED Practice test  Solutions  
Feb 9 
T  9 (D) 
Games I CANCELED  
Feb 11 
R  10 (D) 
Games II [ PPT  PDF ]  Hwk5  Warmup Sols  Solutions  Hwk4  
6  Feb 15 
M  Recitation 5: TEST 1  
Feb 16 
T  11 (V) 
Probability I: Sample Spaces and Expectations [ PPT  PDF ]  
Feb 18 
R  12 (Dr) 
Probability II: Infinite Sample Spaces and Random Walks [ PPT  PDF ]  Hwk6  Warmup Sols  Solutions  Hwk5  
7  Feb 22 
M  Recitation 6
Recitation 6 Solutions 

Feb 23 
T  13 (V) 
Number Theory Quiz 3 [ PPT  PDF ] 

Feb 25 
R  14 (D) 
Cryptography and RSA [ PPT  PDF ]  Hwk7  Warmup Sols  Solutions  Hwk6  
8  Mar 1 
M  Recitation 7
Recitation 7 Solutions 

Mar 2 
T  15 (V) 
Grade School Revisited: How to Add and Multiply [ PPT  PDF ]  
Mar 4 
R  TEST 2 Note that this exam is in lecture. Practice Test A  Practice Test A Solutions Practice Test B  Practice Test B Solutions 
PHwk1  Handout1  Hwk7  
SPRING BREAK  
10  Mar 15 
M  Recitation 8 Recitation 8 Solutions  
Mar 16 
T  16 (V) 
Algebraic Structures I [ PPT  PDF ]  
Mar 18 
R  17 (V) 
Algebraic Structures II [ PPT  PDF ]  Hwk8  Warmup Sols  Solutions  PHwk1  
11  Mar 22 
M  Recitation 9
Recitation 9 Solutions 

Mar 23  T  18 (D) 
Graphs I: Trees and Planar Graphs [ PPT  PDF ]  
Mar 25 
R  19 (D) 
Graphs II: Matchings, Tours, and More [
PPT 
PDF ]
Quiz 4 
PHwk2  Warmup Solutions Individual Writeup Solutions  Hwk8  
12  Mar 29 
M  Recitation 10
Recitation 10 Solutions 

Mar 30 
T  20 (V) 
Automata I: Deterministic Automata and Regular Languages [ PPT  PDF ]  

Apr 1 
R  21 (J) 
Turing Machines [
PPT 
PDF ]
Quiz 5 

13  Apr 5 
M  Recitation 11
Recitation 11 Solutions 

Apr 6 
T  22 (BM) 
Social Networks [ PDF ] 

Apr 8 
R  23 (Dm) 
Cantor's Legacy: Infinity and Diagonalization [ PPT  PDF ] 
Hwk9  Warmup Sols  Solutions  PHwk2  
14  Apr 12 
M  Recitation 12: TEST 3 Practice Test 1  Practice Test 2 Practice Test 1 Solutions  Practice Test 2 Solutions 

Apr 13 
T  24 (Al) 
Turing's Legacy: The Limits of Computation [ ODP  PPT  PDF ] 

Apr 15 
R  No Class: Spring Carnival Have Fun! 

15  Apr 19 
M  Recitation 13
Recitation 13 Solutions 

Apr 20 
T  25 (A) 
Formal Logic, Why Gödel was Awesome, and Some Harsh Truths [ PPT  PDF ]  Hwk10  Warmup Sols  Solutions  Hwk9  
Apr 22 
R  26 (D) 
Efficient Reductions Between Problems
[ PPT

PDF ]
Quiz 6 

16  Apr 26 
M  Recitation 14
Recitation 14 Solutions 

Apr 27 
T  27 (?) 
Complexity Theory: What is the PversusNP Question? [ PPT  PDF ]  
Apr 29 
R  28 (V/D) 
Epilogue [ PPT  PDF ]  Hwk10  
FINAL
EXAM: Thu. May 6 1:00p.m.4:00p.m. UC McConomy Practice Test 1  Practice Test 2  Practice Test 1Sols  Practice Test 2Sols 