Announcements
Exam solutions:
[pdf]
Two 75 min lectures are scheduled each week for this course. The classes are held in W400, at the following times:
| Day | Time |
| Tue, Thr | 12:15-13:30 |
Details about textbook, grading and what is expected from you in this class are described in the course outline available here .
If you disagree with your mark in an assignment or test, please fill out this form. Include the form and your marked test/assignment in an envelope and hand them in during the office hours or in class no later than one week after the marked test is returned. Your entire work will then be re-marked and, as a result, your mark may go up or down, or remain unchanged. Please note that no request for a re-mark will be considered if your answers were written in pencil or erasable ink.
| Week | Dates | Topic | Textbook sections |
| 1 | Sep 6 | What is combinatorics Examples of problems |
Ch.1, pages 1-4 |
| 2 | Sep 11-13 | Proof techniques Pigeonhole principle |
2.1, 2.2 |
| 3 | Sep 18-20 | Counting basics (permutations, combinations) |
Ch.3 |
| 4 | Sep 25-27 Sep 27 |
Ch.3 (c'ed) Assignment 1 due (2.1, 2.2) |
Ch.3 |
| 5 | Oct 2-4 | Binomial coefficients | 5.1-5.3 |
| 6 | Oct 9 Oct 11 |
Inclusion-exclusion principle Test 1 (2.1, 2.2, 3) |
6.1-6.3,6.5 |
| 7 | Oct
16-18 Oct 18 |
Recurrence relations Matchings and bipartite graphs Assignment 2 due (3, 5.1-5.3) |
7.1-7.3 9.1,9.2 |
| 8 | Oct 23-25 | Matchings, Isomorphisms, Subgraphs | 9.1,9.2,11.1, handouts |
| 9 | Oct 30 Oct 30 - Nov 1 |
Test 2 (5.1-5.3, 6.1-6.3,6.5) Isomorphism, Subgraphs, Paths, Cycles |
handouts |
| 10 | Nov
6-8 Nov 8 |
Path, Cycles Assignment 3 due (6.1-6.3,6.5,7.1-7.3) |
handouts |
| 11 | Nov 13-15 | Hamiltonian cycles | handouts |
| 12 | Nov 20-22 Nov 22 Nov 23 (tutorials) |
Shortest paths
Take Home Test 3 (7.1-7.3, 9, 11.1) HANDED OUT Assignment 4 (9.1-9.2, 11.1, Hamiltonian/Eulerian circuits) HANDED OUT |
handouts |
| 13 | Nov 27 (no class) Nov 29 |
CLASS CANCELLED Directed graphs |
12.1 up to p.500 |
| 14 | Dec 4 Dec 4 Dec 4-6 |
Test 3 DUE Assignment 4 DUE Network flows / Review. |
12.2 up to p.511 bottom |
Tests are given during normal class hours on Tuesdays (except for Test 1), at the following dates. The topics covered in tests are described in the course schedule.
| Dates | ||
|---|---|---|
| Oct 11 | Test 1 | answer |
| Oct 30 | Test 2 | answer |
| Handed out on Thr. Nov 22 in class Due Tue. Dec 4 in class | Test
3,
Take home test! |
answer |
You will have 5 full days to work on assignments (except for Assignment 4 where you have 9 full days because you will also be writing Test 3 at home in the same time). They will be handed out Friday during the Lab and will also be posted on this page the same day. Assignments are due Thursday at class time. Solutions will be published on this page after the due date, so no late assignments are accepted. It is in your best interest to hand in on Thursday as much work as you were able to complete.
| Out | Due | Problem set | Solutions | Compare your performance |
|---|---|---|---|---|
| Sep 21 | Sep 27 | Assignment 1 | Solutions | [view] |
| Oct 12 | Oct 18 | Assignment 2 | Solutions | |
| Nov 2 | Nov 8 | Assignment 3 | Solutions | |
| Nov 23 | Dec. 4 | Assignment 4 | Solutions |
Updated Dec. 7, 2007.