21-228: Discrete Mathematics (Spring 2011)

Po-Shen Loh

Last updated 24 April 2011.



The course grade will be calculated as follows: Grade cutoffs will be:


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, you may not look at the actual document that another student is handing in.


There will be 3 in-class tests, on Mon Feb 7, Fri Mar 25, and Wed Apr 20. There will also be a comprehensive final exam during exam week.

Make-up tests 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 test.

Detailed syllabus

The course textbook is Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. The semester's tentative schedule is detailed below.

Week Topic Reference Work due
Week 1
(Mon Jan 10)   
Basic counting Chapter 1 Homework 1
Solutions 1
Week 2
(Mon Jan 17)
Induction; Approximation
(No class Mon Jan 17)
Sections 2.1 and 2.2
Week 3
(Mon Jan 24)
Inclusion-Exclusion; Pigeonhole    Sections 2.3, 2.4, and 2.5 Homework 2
Solutions 2
Week 4
(Mon Jan 31)
Binomial coefficients Sections 3.1 to 3.6.
Week 5
(Mon Feb 7)
Pascal's triangle: asymptotics Sections 3.7 and 3.8. Test 1 on Mon
Solutions | Raw scores
Scaled score converter
Homework 3
Solutions 3
Week 6
(Mon Feb 14)
Linear recursions
Week 7
(Mon Feb 21)
Generating functions Generatingfunctionology (free book),
by H. Wilf. Sections 1.1-1.3, 2.1-2.3.
Additional notes from MIT's OCW,
by A. Meyer.
Homework 4
Solutions 4
Week 8
(Mon Feb 28)
More generating functions
(No class Fri Mar 4)
Spring break
(Mon Mar 7)
No class!
Week 9
(Mon Mar 14)
Expected value Alternate references #1 and #2 from
MIT's OCW, by A. Meyer and
R. Rubinfeld
Homework 5
Solutions 5
Week 10
(Mon Mar 21)
More probability Test 2 on Fri
Solutions | Raw scores
Scaled score converter
Week 11
(Mon Mar 28)
Graph theory Chapter 7 of course text, plus
Section 10.1 of Diestel: free edition
Homework 6
Solutions 6
Week 12
(Mon Apr 4)
Trees Chapter 8
Week 13
(Mon Apr 11)
Ramsey theory
(No class Fri Apr 15)
Alt refs #1 and #2 from B. Sudakov's
Princeton Combinatorics course.
Homework 7
Solutions 7
Week 14
(Mon Apr 18)
Matching Chapter 10 Test 3 on Wed
Solutions | Raw scores
Scaled score converter
Week 15
(Mon Apr 25)
Planarity Sections 12.1 and 12.2 Homework 8
Solutions 8
Final exam
(Mon May 2)
From 8:30 - 11:30am, in Doherty 2302.

You are visitor number since 18 December 2010.
[back home]