MAT344
Introduction to Combinatorics
Fall 2021
Course information
MAT344H1-F
Basic counting principles, generating functions, permutations with restrictions. Fundamentals of graph theory with algorithms; applications (including network flows). Combinatorial structures including block designs and finite geometries.
MAT223 (Linear Algebra) or MAT240 (Algebra I)
In person
Instructors
| name | section | office hour | |
|---|---|---|---|
| Shubhangi Saraf | shubhangi.saraf@utoronto.ca | LEC0101 | Wed 15:30—16:00 |
| Maxence Mayrand | mayrand@math.toronto.edu | LEC0201 | Thu 11:00—12:00 |
Email is the preferred method of communication.
Lectures
LEC0101 — Shubhangi Saraf
Monday9:00—11:00
Wednesday9:00—10:00
Monday, September 13, 2021
Thursday, December 9, 2021 (make-up day)
MP 102
LEC0201 — Maxence Mayrand
Monday16:00—18:00
Tuesday17:00—18:00
Monday, September 13, 2021
Thursday, December 9, 2021 (make-up day)
GB 221
Students are permitted to attend lectures and tutorials online on Zoom for the first two weeks (September 13–23, 2021). Zoom links are on Quercus.
Teaching assistants
| name | tutorials | office hour | |
|---|---|---|---|
| Lemonte Alie-Lamarche | lemonte@math.utoronto.ca | TUT5301 | Wed 13:00-13:30 |
| Christopher Kaumeyer | chris.kaumeyer@mail.utoronto.ca | TUT0101 | Thu 12:30-13:00 |
| Feodor Kogan | feodor.kogan@mail.utoronto.ca | TUT5201 | Fri 13:00-13:30 |
| Theodore Lindgreen | theodore.lindgreen@mail.utoronto.ca | TUT0201 TUT5302 | Fri 14:00-14:30 |
| Charlie Wu | charliec.wu@mail.utoronto.ca | TUT5101 | Wed 13:30-14:00 |
| Fengkai Ye | fengkai.ye@mail.utoronto.ca | TUT0301 | Thu 14:00-14:30 |
Zoom links for office hours are on Quercus.
Tutorials
| sections | time | room | TA |
|---|---|---|---|
| TUT0101 | Monday 13:00-14:00 | BA 1220 | Christopher Kaumeyer |
| TUT0201 | Tuesday 13:00-14:00 | SS 1086 | Theodore Lindgreen |
| TUT0301 | Tuesday 16:00-17:00 | RW 142 | Fengkai Ye |
| TUT5101 | Monday 17:00-18:00 | BA 2195 | Charlie Wu |
| TUT5201 | Monday 18:00-19:00 | MP 134 | Feodor Kogan |
| TUT5301 | Tuesday 17:00-18:00 | GB 220 | Lemonte Alie-Lamarche |
| TUT5302 | Tuesday 17:00-18:00 | GB 120 | Theodore Lindgreen |
During the tutorials, TAs will explain solutions to some exercises, answer students questions, and review the relevant course material.
Tutorials start in the week Sep 20—Sep 24 and continue every week until the week Dec 6—Dec 10, except for the week of the Thanksgiving (Oct 11—Oct 17) and the reading week (Nov 08—Nov 14).
Textbook
We will use the free and online textbook Applied Combinatorics, by Keller and Trotter
Course content
The plan is to cover the following sections of the textbook:
1, 2, 3, 4.1, 5.1-5.6, 7, 8, 9, 13
Tentative schedule
| week | textbook sections | evaluation | note |
|---|---|---|---|
| Sep 13—Sep 19 | 2 | ||
| Sep 20—Sep 26 | 2 | first tutotrial | |
| Sep 27—Oct 03 | 3 | PS1 due Sunday | |
| Oct 04—Oct 10 | 4.1, 5 | ||
| Oct 11—Oct 17 | 5 | PS2 due Sunday | no lecture on Monday and no tutorial all week |
| Oct 18—Oct 24 | 5 | ||
| Oct 25—Oct 31 | 7 | midterm on Monday | |
| Nov 01—Nov 07 | 8 | PS3 due Sunday | |
| Nov 08—Nov 14 | reading week: no lecture and no tutorial | ||
| Nov 15—Nov 21 | 9 | PS4 due Sunday | |
| Nov 22—Nov 28 | 9 | ||
| Nov 29—Dec 05 | 13 | PS5 due Sunday | |
| Dec 06—Dec 09 | 13 | last tutorial; make-up class on Thursday | |
| final exam | final assessment period (Dec 10—Dec 21) |
Marking scheme
40% (best 4 out of 5 problem sets)
25%
35%
Problem sets
40%
5
Your problem set with the lowest grade will be dropped, so only your best 4 will count. Each will have an equal weight of 10% in your final grade.
Problem sets are due on Sundays at 11:59PM (one minute before
midnight) and are released one week before. The due dates are:
PS1due on Sunday October 3 at 11:59PM
PS2due on Sunday October 17 at 11:59PM
PS3due on Sunday November 7 at 11:59PM
PS4due on Sunday November 21 at 11:59PM
PS5due on Sunday December 5 at 11:59PM
will be marked 0%.
The problem sets will be sent to you via Crowdmark.
You will be asked to submit your solutions electronically on Crowdmark.
No paper copy will be accepted.
The easiest way to upload your problem set is to use a scanner, but if
you don't have access to one, you can also use a scanner app on your
phone. Make sure that your work is legible before submitting it;
otherwise, it will not be accepted.
Written solutions are not provided, but some of them will be discussed in tutorials. You are encouraged to consult with TAs, your fellow students, and the instructors to identify shortcomings in your grasp of the material.
Your submissions must be your own work, written independently, in your own words. Otherwise, it will be considered an offence under the University of Toronto's Code of Behaviour on Academic Matters (see section B.I.) and serious sanctions will be applied.
Midterm exam
25%
1 hour and 50 minutes, in person, during class time
Monday, October 25
TBA
There will be no make-up midterm exam. For students who missed the midterm exam because of illness or any other approved legitimate reason, its weight will be transferred to the final exam.
Final exam
35%
3 hours, in person
December 11, 2021, 19:00—22:00
All material from the first lecture to the last lecture.
Discussion forum
We will use Piazza, which is a discussion forum where you can ask as many questions as you like, and will receive answers from other students, the TAs, or the instructor.
To join the forum, go to piazza.com and search for MAT344. You will also get an email invitation at the beginning of the course. Alternatively, you can sign up using by cliking here.
Practice problems
All problems are in the textbook. Doing these exercises is excellent preparation for the midterm and final exams.
1, 2, 3, 4, 5, 7, 10, 12, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 29, 30, 31, 32
2, 3, 4, 5, 9, 10, 11, 12, 15, 16, 17, 18
2, 3
1, 2, 3, 6, 7, 10, 11, 12, 13, 14, 16, 17, 25, 26, 28, 29, 30, 32
7, 8, 9, 11, 14, 17, 19, 21
1, 2, 3, 4, 5, 7, 9, 10, 16, 17, 19, 20, 21, 22, 23, 24, 26
1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 15, 16