21-228: Discrete Mathematics (Spring 2013)

Po-Shen Loh

Last updated 11 May 2013.

Location

Grading

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

Homework

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.

Tests

There will be 3 in-class tests, on Wed Feb 6, Wed Mar 20, and Wed Apr 24. There will also be a comprehensive final exam on Fri May 10, from 1-4pm.

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 follows the order of topics in the well-written book Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. 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 read the book, 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
Week 1
(Mon Jan 14)    		Basic counting; induction Chapter 1; Fwd-backward induction Homework 1
Week 2
(Mon Jan 21) 		Inclusion-exclusion,
pigeonhole principle
(No class Mon Jan 21)
Chapter 2;
Dirichlet's approximation theorem
(on AoPS)
Week 3
(Mon Jan 28) 		Homework 2
Week 4
(Mon Feb 4) 		Binomial coefficients Chapter 3; Lucas' Theorem Test 1 on Wed
Week 5
(Mon Feb 11) 		Linear algebra and recurrences Chapter 4; Wikipedia, Croot's notes Homework 3
Week 6
(Mon Feb 18) 		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 25) 		More generating functions Homework 4
Week 8
(Mon Mar 4) 		Introduction to graphs
(No class Fri Mar 8) 		Chapter 7
Spring break
(Mon Mar 11) 		Relax
Week 9
(Mon Mar 18) 		Trees Chapter 8 Test 2 on Wed
Homework 5
Week 10
(Mon Mar 25) 		Traveling salesman problem Chapter 9
Week 11
(Mon Apr 1) 		Matchings Chapter 10 Homework 6
Week 12
(Mon Apr 8) 		Combinatorial geometry Chapter 11
Week 13
(Mon Apr 15) 		Ramsey theory
(No class Fri Apr 19) 		Alt refs #1 and #2 from B. Sudakov's
Princeton Combinatorics course. 		Homework 7
Week 14
(Mon Apr 22) 		Planar graphs Chapter 12 Test 3 on Wed
Week 15
(Mon Apr 29) 		Coloring Chapter 13 Homework 8
Final exam
(Fri May 10) 		In Wean 7500, from 1:00pm - 4:00pm

You are visitor number since 28 December 2012.
[back home]