Discrete Mathematics  21-228

Summer 2004
MTWRF 1:30-2:50
DH 2105

useful links:

* Herbert Wilf's home page (You can download generatingfunctionology and East Side, West Side.)
* Alan Frieze's notes from 2002
* David Pollard's Lecture Notes on Probability

syllabus (pdf) (ps)

HW1 (pdf) (ps)   solutions (pdf) (ps)
HW2 (pdf) (ps)   solutions (pdf) (ps)
HW3 (pdf) (ps)   solutions (pdf) (ps)
HW4 (pdf) (ps)   solutions (pdf) (ps)
HW5 (pdf) (ps)   solutions (pdf) (ps)
HW6 (pdf) (ps)   solutions (pdf) (ps)
HW7 (pdf) (ps)   solutions (pdf) (ps)
HW8 (pdf) (ps)   solutions (pdf) (ps)
HW9 (pdf) (ps)   solutions (pdf) (ps)

exam 1 (pdf) (ps)   solutions (pdf) (ps)
exam 2 (pdf) (ps)   solutions (pdf) (ps)
exam 3 (pdf) (ps)   solutions (pdf) (ps)
exam 4 (pdf) (ps)   solutions (pdf) (ps)

midterm review questions (pdf) (ps)
midterm (pdf) (ps)   solutions (pdf) (ps)
revised midterm (pdf) (ps)   solutions (pdf) (ps)
final review questions (pdf) (ps)
final (pdf) (ps)   solutions (pdf) (ps)

 Date Topic References Monday, 5/17 Introduction: 3 ways of counting Frieze's Notes, Day 0 Tuesday, 5/18 Counting: subsets, permutations, and combinations. Lovasz, 1.3, 1.5-1.8 Frieze's Notes, Day 1 Wednesday, 5/19 Binomial Coefficients, Mathematical Induction, Identities, the Binomial Theorem, Catalan Numbers Lovasz, 2.1, 3.1, 3.5-3.7 Frieze's Notes, Day 2, Day 4 Thursday, 5/20 Asymptotic Behavior, Functions, the Pigeonhole Principle Lovasz, 2.2, 2.4 Frieze's Notes, Day 5 Friday, 5/21 Exam 1, Fibonacci Numbers Lovasz, 4.1-4.3 Monday, 5/24 Recurrence Relations: Examples Solving Lin. Hom. Recurrence Relations. Frieze's Notes, Day 11 handout (pdf) (ps) Tuesday, 5/25 Solving Non-hom. Lin. Rec. Rel. "Divide and conquer" recurrences Frieze's Notes, Day 12 Wednesday, 5/26 Generating Functions: Solving Recurrences Catalan Numbers 1.1-1.3 Frieze's Notes, Day 15 Thursday, 5/27 More Generating Functions: Bell Numbers, Stirling numbers 1.6 East Side, West Side, 5.1-5.4 Friday, 5/28 Exam 2, More Bell Numbers Monday, 5/31 No Class Important Information Tuesday, 6/1 Inclusion/Exclusion Lovasz, 2.3 Frieze's Notes, Day 16 Wednesday, 6/2 Permutations and Derangements Restricted Position Problems Frieze's Notes, Day 14 Thursday, 6/3 Review Midterm Exam distributed in class review questions (pdf) (ps) Friday, 6/4 Midterm Exam due at 2:50 in DH 2105 Monday, 6/7 Introduction to Probability Probability Spaces, Uniform and Geometric Distribution Independence, Conditioning, R.V's, Expectation Lovasz, 5.1, 5.2 Pollard's Notes Chapters 1, 2 Frieze's Notes, Day 6, Day 8, Day 9 Tuesday, 6/8 Random Variables:  Binomial and Poisson Bayes' Theorem Pollard's Notes Chapters 3, 9 Frieze's Notes, Day 9 Wednesday, 6/9 Monty Hall Problem Average-case analysis Boole's Inequality, the probabilistic method Frieze's Notes, Day 7, Day 8, Day 9 Pollard's Notes Chapter 1 Thursday, 6/10 Variance, Markov's Inequality Chebycheff's Inequality Law of Large Numbers Frieze's Notes, Day 10 Pollard's Notes Chapter 4 Friday, 6/11 Exam 3 Monday, 6/14 Intro to Graph Theory:  Definitions and Examples Lovasz, 7.1, 7.2 Frieze's Notes, Day 17, Day 18 Tuesday, 6/15 Euler Tours and Hamilton Cycles Trees Lovasz, 7.3, 8.1, 8.2 Frieze's Notes, Day 19, Day 20 Wednesday, 6/16 Counting Trees: Prufer Code MST: Kruskal's Algorithm Lovasz, 8.3, 8.4, 8.5, 9.1 Frieze's Notes, Day 19 Thursday, 6/17 Matching Lovasz, Chapter 10 Frieze's Notes, Day 21 Friday, 6/18 Graph Coloring, Planar Graphs Lovasz, 13.2, 13.3, 12.1 Monday 6/21 Coloring Planar Graphs Directed Graphs Lovasz, 12.2, 13.4 Frieze's Notes, Day 23 Tuesday, 6/22 Exam 4 Wednesday, 6/23 Vertex Covers, Tournaments Thursday, 6/24 Final Exam distributed in class Friday, 6/25 Final Exam due at 2:50 in DH 2105