Lecture Number  Date  Topic  Reading Assignment from {Z] For maximum gains, please complete before coming to lecture 
Readings from {LLM] 
Proofs, Logic, and Sets  
1 
Jan. 11 
Course Organization Basic Proof Techniques 
Chapter 1 
Chapter 1 
2 
Jan. 16 

Jan 18 
SNOW DAY 

3 
Jan. 23 
Propositional Logic  Chapter 2 
Chapter 3 
4 
Jan. 25 
First order Logic 

5 
Jan. 30 
Set Theory 
Chapter 3 
Chapter 4.1, 4.3 
6 
Feb. 1 
Functions, Sequences, Summations 
Chapters 4,5 
Chapter 4.2, 14 
7 
Feb. 6 
Mathematical Induction  Chapter 2, 5  
8 
Feb. 8 
Strong Induction, Infinite sets 
Chapter 8 

9 
Feb. 13 
MIDTERM 1 (Lectures 1  7) 

Computation  
10  Feb. 15 
Diagonalization, Halting Problem 
Chapter 8 

11 
Feb. 20 
Approximate Summation, Asymptotics 
Chapter 6 
Chapter 14 
12 
Feb. 22 
Recursion and Recurrence Relations  Chapter 7 
Chapter 22 
13 
Feb. 27 
Structural Induction  Chapter 6 

Combinatorics and Probability 

14 
Mar. 1 
Basic counting rules, Counting Subsets

Chapter 8 
Chapter 15 
15 
Mar. 6 
InclusionExclusion, Pigeonhole Principle  Chapter 9 
Chapter 16 
16 
Mar. 8 
MIDTERM 2 (Lectures 10  15) 

SPRING BREAK  
17 
Mar. 20 
Events and Sample Spaces 
Chapter 10 
Chapter 17 Tomasi's Notes 
18 
Mar. 22 
Conditional Probability, Independence Bayes' rule, Monty Hall Problem 
Chapter 18 

19 
Mar. 27 
Random Variables, Expectation Bernoulli Trials  Chapter 19 

Graph Theory 

20 
Mar. 29 
Basic terminology and applications 
Chapter 11 
Chapter 12 
21 
Apr. 3 
Matchings and Hall's theorem 

22 
Apr. 5 
Graph Isomorphism, Colorings 

23 
Apr. 10 
Connectivity, Eulerian and Hamiltonian paths 

24 
Apr. 12 
Trees, Tree traversal, Spanning trees 
Chapter 12 

25 
Apr. 17 
MIDTERM 3 (Lectures 15  23) 

Applications 

26 
Apr. 19 (slack) 
Opinion polls and estimation Variance and Chebychev's Inequality Weak Law of Large Numbers 
Chapter 20  
27 
Apr. 24 (slack) 
Ranking the Web Markov Chains and Random Walks 
Lecture Notes Chapter 21 

28 
Apr. 26 (slack)  Nonmandatory Review Session 

May 3, 9 AM 
FINAL EXAM (French Science 2231)
