MATH 2865 - Combinatorial Mathematics (Fall 2007)

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

Textbook, Grading and Examinations

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.

Schedule for course, tests, assignments

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)
4 Sep 25-27
Sep 27
Ch.3 (c'ed)
Assignment 1 due (2.1, 2.2)
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)
7 Oct 16-18
Oct 18
Recurrence relations
Matchings and bipartite graphs
Assignment 2 due (3, 5.1-5.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

10 Nov 6-8
Nov 8
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 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
13 Nov 27 (no class)
Nov 29
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.

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!


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

Solutions to the homework

Updated Dec. 7, 2007.