| Date |
Lecture Topics |
Assigned Readings & Other Info |
| Aug 29 |
- Course introduction
- Basic counting, sum and product principles, counting subsets
|
|
| Sep 3 |
- Bijection principle
- Pascal's Triangle
|
|
| Sep 5 |
- Bijection principle take 2
- Binomial Theorem
- Relations
|
|
| Sep 10 |
- Equivalence Relations, Posets, Orders
- Counting with equivalence relations
|
- Textbook - Pages 43 to the end of Chapter 1
|
| Sep 12 |
- Finishing up Chapter 1
- Logic and truth tables
|
|
| Sep 17 |
- Boolean Algebra
- Quantifiers
|
|
| Sep 19 |
- Negation of quantifiers
- First steps on what is a proof?
|
|
| Sep 24 |
- More proofs
- Contrapositive
|
|
| Sep 26 |
- Proof by contradiction
- Proof by smallest counter example (not part of midterm)
|
|
| Oct 1 |
|
|
| Oct 3 |
|
- Chapter 4 - weak induction
|
| Oct 8 |
- More induction. Intro to strong induction
|
|
| Oct 10 |
- Induction in a CS algorithm (binary search)
- Induction using structures (triangulations of polygons)
|
- Chapter 4 - structural induction
|
| Oct 15 |
|
|
| Oct 17 |
|
- Read the 2/3 examples pertaining to application of the theorem from the book
|
| Oct 22 |
- Divide and conquer
- Specific example of mergesort (Intro to recursion trees)
|
|
| Oct 24 |
- 3 different recursion trees giving different big-theta answers
|
|
| Oct 28 |
|
|
| Oct 31 |
- Inclusion Exclusion principle
- Derangements
|
|
| Nov 5 |
- Conditional probability
- Bayes theorem
|
|
| Nov 7 |
- Independence
- Probability trees
|
|
| Nov 12 |
|
|
| Nov 14 |
|
- Book section 5.4
- Please read the proof for linearity of expectations
|
| Nov 19 |
- Expectation calculations in hashing
|
- Book section 5.5 - only the results we did in class
- 6.1 - we just started with the definitions
|
| Nov 21 |
- Lots of definitions in graph theory
- intro to induction in graphs
|
|
| Nov 26 |
|
|
| Dec 3 |
|
|
| Dec 5 |
- More Eulerian tours
- Hamiltonian tours
|
- Section 6.3
- Chinese Postman Problem
- Traveling Salesman Problem
|
| Dec 10 |
|
|
| Dec 20 |
|
|