UNIVERSITY OF TORONTO

FACULTY OF ARTS AND SCIENCE

MAT344 INTRODUCTION TO COMBINATORICS

SYLLABUS - WINTER 2021

Course Description: Basic counting principles, generating functions, permutations with restrictions. Fundamentals of graph theory with algorithms; applications.

Prerequisite: MAT223H1/MATA23H3/MAT223H5/MAT240H1/MAT240H5

Instructors:

• Kostya Tolmachov, email: [email protected]

• Zack Wolske, email: [email protected]

Lectures:

Office Hours: To be announced.

Teaching Assistants:

• Sina Abbasi

• Keegan Dasilva Barbosa

• Mehmet Durlanik

• Malors Emilio Espinosa Lara

• Gavin Hurd

• Xiao Jie

• Relia Zheng

Tutorials: Check your timetable. Tutorials will start the second week of classes. Students must be registered in a tutorial section.

Course Webpage: We will use Quercus (BB Collaborate) for lectures and tutorials. Each class will meet synchronously and be recorded.

In order to participate in this course, students will be required to have reliable internet access and a computer satisfying the minimum technical requirements (https://www.viceprovoststudents. utoronto.ca/covid-19/tech-requirements-online-learning/)

        If you are facing financial hardship, you are encouraged to contact your college or divisional registrar (https://future.utoronto.ca/current-students/registrars/) to apply for an emergency bursary.

Textbook (Required): Applied Combinatorics by M. T. Keller and W. T. Trotter, 2017 Edition, available for free at https://www.rellek.net/appcomb/

        The numbering in the pdf and html versions are different. Whenever we reference to something in the book (e.g. section numbers or exercises), we refer to the pdf version.

        For the final topics, Combinatorics by J. Morris, 2017 Edition, will be used, available for free at https://www.cs.uleth.ca/˜morris/Combinatorics/Combinatorics.html.

Grading Scheme:

• Assignments 50% : Eight assignments with tentative due dates of Jan 25, Feb 1, Feb 8, Feb 15, Mar 8, Mar 15, Mar 22, Mar 29. The lowest two assignments will be dropped. Assignments are to be submitted through Crowdmark.

• Midterm 25%: Special assignment during the week Feb 22-26.

• Final 25%: Special assignment during the exam period.

More on Assignments: The assignments form a very important part of the course. The purpose of them is to improve your understanding of the material and prepare you for the midterm and final. In addition to the assignments that are to be submitted for grading, most weeks you will be provided with a list of extra practice problems. You are expected to work on these as well. (They might be relevant for the midterm or exam.)

        Note that only a selected number of questions from each assignment will be graded (due to time limitations).

        The assignments are to be submitted on Crowdmark. Students are responsible to make sure that they upload their work before the deadline, and that their solutions are properly scanned and easy to read.

Policy for Late/Missed Assignments: Each assignment must be submitted before its deadline. Assignments submitted late or not submitted (for any reason) will be recorded with a grade of zero. The lowest two out of eight assignments will be dropped in the end.

Policy for Missed Midterm due to an Emergency: Students who miss the midterm for reasons beyond their control must submit a request for special consideration to their instructor electronically within 3 days after the midterm deadline, explaining the reason for missing the assignment. If the request for special consideration is approved, the student will have to write the make-up midterm, which will take place on a date and time decided and announced by the instructors (likely the make-up will be during the week after the regular midterm). A grade of zero will be recorded for students who (after missing the original sitting) also miss the make-up midterm. Requests for exceptions to this rule must come from official university channels, such as the office of the Registrar or the Test and Exam Services. 

Policy for Conflicts: Students who will not be able to write the midterm due to a conflict must send an email to their instructor during the week prior to the midterm with a request for special consideration. The email must include the appropriate supporting documentation. If the request for special consideration is approved, the student will have to write the make-up midterm, which will take place on a date and time decided and announced by the instructors (likely the make-up will be during the week after the regular midterm). A grade of zero will be recorded for students who (after missing the original sitting) also miss the make-up midterm. Requests for exceptions to this rule must come from official university channels, such as the office of the Registrar or Test and Exam Services.

Policy for Term Work Regrade: Regrade requests for any piece of term work, if submitted later than a week after the date on which the grades for the assessment in question have become available on Quercus, may be denied.

Collaboration versus Plagiarism: You are encouraged to discuss the problems sets with each other, but each of you must write up your own solutions independently. If you find the solutions in books or on the internet, you must quote your source, and still write up the solution in your own words. You are expected to be be familiar with the University’s Code of Behaviour on Academic Matters, available at the following link:

        http://www.governingcouncil.utoronto.ca/Assets/Governing+Council+Digital+Assets/Policies/PDF/ppjun011995.pdf

        You are also expected to have read the document How Not to Plagiarize available at the following link:

        http://www.writing.utoronto.ca/advice/using-sources/how-not-to-plagiarize

Accessibility Services: The University of Toronto is committed to accessibility. If you have any accessibility concerns about the course, or require any accessibility-related accommodation, please contact the Accessibility Services (www.studentlife.utoronto.ca/as) as soon as possible.

Email Policy: Math questions will not be answered over email. Emails are mainly to be used for administrative purposes. Please use your @mail.utoronto.ca or @utoronto.ca email account to contact the teaching staff, and include MAT344 in the subject line. If the answer to an email is included in the syllabus, the email will likely receive no response.

Tentative Weekly Plan of Lectures: The chapter numbers are from the textbook. Note that this is just to serve as a rough guideline. Students are responsible to be aware of what is covered in lectures each week.

Reminder: Last day to drop S section code courses without academic penalty is March 15.