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 |
Inclusion-Exclusion, 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 14-20) |
||
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
|