Last updated 11 May 2013.
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.
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.
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. |