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
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 |
generatingfunctionology,
1.1-1.3 Frieze's Notes, Day 15 |
| Thursday, 5/27 |
More Generating Functions: Bell Numbers, Stirling numbers |
generatingfunctionology,
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 |