21-228: Discrete Mathematics (Spring 2017)

Po-Shen Loh

Last updated 9 May 2017.



The course grade will be calculated as follows: All exams will be open notes / open book.


The only way to learn mathematics is to do mathematics. (Paul Halmos)

In order to encourage students to experiment with the concepts taught in class, homework assignments will be given on alternate weeks. They will be due in class on Fridays, at the beginning of lecture.

Since homework is a learning activity, students are welcome to discuss ideas with each other, although collaboration in the writing stage is not permitted. In other words, please do not look at the actual document that another student is handing in.


There will be 3 in-class exams, on Fri Feb 10, Fri Mar 24, and Mon May 1. There will also be a comprehensive final exam.

Make-up exams will be given only in the case of a documented medical excuse, a university-sanctioned absence (e.g., participation in a varsity sporting event), or a family emergency. However, this must be requested before the official start time of each exam.

Detailed syllabus

The course follows the order of topics in the well-written book Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. This book is not required for the class, because the level of CMU students is somewhat beyond. To adjust for the level of students at CMU, a substantial amount of extra material (not in the textbook) is covered in class. Students are encouraged to reference the book for further clarification, as it provides a clear presentation of an alternate perspective on the content discussed in class. The semester's tentative schedule is detailed below.

Week Topic Alternate reference Work due Fri
Week 1
(Mon Jan 16)   
Basic counting; induction Chapter 1; Fwd-backward induction
Week 2
(Mon Jan 23)
pigeonhole principle

Chapter 2;
Dirichlet's approximation theorem
(on AoPS)
Homework 1
Week 3
(Mon Jan 30)
Homework 2
Week 4
(Mon Feb 6)
Binomial coefficients Chapter 3; Lucas' Theorem Exam 1 on Fri
Week 5
(Mon Feb 13)
Linear algebra and recurrences Chapter 4; Wikipedia, Croot's notes Homework 3
Week 6
(Mon Feb 20)
Generating functions Generatingfunctionology (free book),
by H. Wilf. Sections 1.1-1.3, 2.1-2.3;
notes from MIT's OpenCourseWare
Week 7
(Mon Feb 27)
More generating functions Homework 4
Week 8
(Mon Mar 6)
Introduction to graphs
(No class Fri Mar 10)
Chapter 7
Spring break
(Mon Mar 13)
Week 9
(Mon Mar 20)
Trees Chapter 8 Exam 2 on Fri
Homework 5
Week 10
(Mon Mar 27)
Traveling salesman problem Chapter 9
Week 11
(Mon Apr 3)
Matchings Chapter 10 Homework 6
Week 12
(Mon Apr 10)
Combinatorial geometry Chapter 11
Week 13
(Mon Apr 17)
Ramsey theory
(No class Fri Apr 21)
Alt refs #1 and #2 from B. Sudakov's
Princeton Combinatorics course.
Homework 7
Week 14
(Mon Apr 24)
Planar graphs Chapter 12
Week 15
(Mon May 1)
Coloring Chapter 13 Exam 3 on Mon
Homework 8
Final exam
Mon May 8
In Doherty 1212, from 8:30am-11:30am

You are visitor number since 18 January 2017.
[back home]