21.228 Discrete Mathematics

This course introduces three of the fundamental areas of discrete mathematics: enumeration, graph theory and discrete probability. The introduction to enumeration includes recurrence relations, generating functions and the principle of inclusion and exclusion. The introduction to graph theory includes topics such as paths, connectivity, Eulerian and Hamilton cycles, planar graphs, Euler's Theorem, matchings, and trees.

Course Instructor:

Tom Bohman
Wean Hall 6113
Phone: (412) 268-2550
Email: tbohman@math.cmu.edu
Office Hours: Wednesday 2:30-4:30

Teaching Assistants:

Christopher Cox
Wean Hall 6201
Phone: (412) 268-5127
Email: cocox@andrew.cmu.edu
Office Hours: Thursday 12:30-2:30

Zhiyang (Sunny) He
Wean Hall 6215
Email: szh@andrew.cmu.edu
Office Hours: Thursday 4:30-5:30

Course Information

Homework 1

Homework 2

Homework 3

Review Sheet for Test 1

Homework 4

Homework 5

Review Sheet for Test 2

Homework 6

Homework 7

Homework 8

Review Sheet for Quiz 2

Review Sheet for Test 3

Homework 9

Review Sheet for the Final Exam

Latex

LPK L. Lovasz, J. Pelikan, and K. Vesztergombi. Discrete Mathematics, Elementary and Beyond

MN J. Matousek and J. Nesetril. Invitation to Discrete Mathematics


Week of January 13: Counting Sets and Functions. LPK: Chapter 1; Sections 3.2, 3.3, 3.4.

Weeks of January 20 and 27: Approximations and Notes on Pascal's Triangle. LPK: Sections 2.1, 2.2, 2.5; Sections 3.1, 3.5, 3.6, 3.7, 3.8.

Week of February 3: Inclusion/Exclusion. MN: Section 2.7. Also see LPV: Section 2.3 for a brief introduction.

Weeks of February 10 and 17: Generating Functions. MN: Chapter 10. Also see LPV: Chapter 4 for a brief introduction.

Week of February 24: Introduction to Ramsey Theory.

Weeks of March 2, 16, 23 and 30 : Discrete Probability. MN: Chapter 9. LPV Chapter 5.

Weeks of April 6 and 13: Introduction to Graph Theory. MN: Sections 3.1 and 3.4 and Chapters 4 and 5. LPV Chapters 7,8 and 9.