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 bigtheta 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 

