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 
Chapter 8 
Chapter 15 
15 
Mar. 6 
Counting Subsets  
16 
Mar. 8 
MIDTERM 2 (Lectures 10  15) 

SPRING BREAK  
17 
Mar. 20 
InclusionExclusion, Pigeonhole Principle  Chapter 9  Chapter 16 
18 
Mar. 22 
Events and Sample Spaces 
Chapter 10 
Chapter 17 Tomasi's Notes 
19 
Mar. 27 
Conditional Probability, Independence Bayes' rule, Monty Hall Problem 
Chapter 18 

20 
Mar. 29 
Random Variables, Expectation Distributions  Chapter 19 

Graph Theory 

21 
Apr. 3 
Basic terminology, Connectivity, Isomorphism 
Chapter 12 
Chapter 12 
22 
Apr. 5 
Trees, Breadth first search Eulerian Tours 

23 
Apr. 10 
Bipartite Graphs and Matchings  
24 
Apr. 12 
Graph Colorings and Planarity  
25 
Apr. 17 
MIDTERM 3 (Lectures 1420) 

26 
Apr. 19 
Directed Acyclic Graphs, Topological Sort  Chapter 12 
Chapter 12 
Applications 

27 
Apr. 24 (slack) 
Opinion polls and estimation Variance and Chebychev's Inequality Weak Law of Large Numbers 
Chapter 20  
May 3, 9 AM 
FINAL EXAM
