Exam solutions: [pdf]
Two 75 min lectures are scheduled each week for this course. The classes are held in W400, at the following times:
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.
|1||Sep 6|| What is combinatorics
Examples of problems
|Ch.1, pages 1-4|
|2||Sep 11-13|| Proof techniques
|3||Sep 18-20|| Counting basics
Assignment 1 due (2.1, 2.2)
|5||Oct 2-4||Binomial coefficients||5.1-5.3|
|6|| Oct 9
| Inclusion-exclusion principle
Test 1 (2.1, 2.2, 3)
| 6.1-6.3,6.5 |
| Recurrence relations
Matchings and bipartite graphs
Assignment 2 due (3, 5.1-5.3)
| 7.1-7.3 |
|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
| Path, Cycles
Assignment 3 due (6.1-6.3,6.5,7.1-7.3)
|11||Nov 13-15||Hamiltonian cycles||handouts|
|12|| Nov 20-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)
| CLASS CANCELLED
|12.1 up to p.500|
|14|| Dec 4
| 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.
|Oct 11||Test 1||answer|
|Oct 30||Test 2||answer|
| Handed out on Thr. Nov 22 in class |
Due Tue. Dec 4 in class
Take home test!
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.