Applied Discrete
Mathematics MAT 3348 - Winter 2021
This website is not maintained. For
the latest update, please consult the course Brightspace
page.
Class Time:
Mondays 8:30-10:00 on Zoom
Thursdays
10:00-11:30 on Zoom
Classes will be run synchronously via Zoom and will be recorded.
Attendance is mandatory.
Office Hours: Wednesdays 4-5 on Zoom (subject to
change)
Professor:
Mateja Šajna
Office: STEM 629
Phone: 562-5800 ext. 3522
E-mail:
msajna@uottawa.ca
Important: Please include MAT3348 in the subject line of every
email you send me and sign
your message. Otherwise your email may be deleted unread.
Virtual Campus: All course material and grades
will be posted on Brightspace. You will also need to login to
Brightspace in order to enter the virtual classroom (Zoom).
Zoom requirements: High-speed
internet connection and a camera are a must. To enter the virtual
classroom, students must use their full names and UOttawa email
addresses.
Prerequisites: (MAT2343
or MAT2348 or CSI 2101) and MAT1341, or permission of the
instructor.
Please email me if you would like
to register in the course but do not have the prerequisites.
Target audience: Students enrolled in programs in the
Department of Mathematics and Statistics, selected students enrolled
in programs in the School of Electrical Engineering and Computer
Science. This course focuses on applied and algorithmic discrete
mathematics. These topics are essential for anyone interested in
discrete mathematics, optimization, or operations research, and any
mathematics student with the intention to work for the industry.
Highly recommended for any math co-op student.
Required Textbook: The
e-textbook (M. Šajna, Applied
Discrete Mathematics) is posted on Brightspace.
Additional
Resources (optional):
- J.A. Bondy and U.S.R Murty, Graph
Theory with Applications.
- L.R. Foulds, Combinatorial Optimization for Undergraduates
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics
- Jonathan Gross and Jay Yellen, Graph Theory and Its Applications.
- Kenneth H. Rosen, Discrete
Mathematics and Its Applications
Course Outline:
Trees
and applications. Applications of graphs. Networks and flows.
Matching theory.
Detailed Course Contents :
- Computational complexity. Introduction to graphs.
- Trees: characterization and properties. Spanning trees and
graph traversals. The Connector Problem. The Shortest Paths
Problem.
- Euler trails and the Chinese Postman Problem. Hamilton cycles,
Gray codes, and the Travelling Salesman Problem.
- Matchings in bipartite graphs, Hall's Theorem, König's
Theorem. The Hungarian Method and the Kuhn-Munkres
Algorithm.
- Flows and cuts in networks, Max Flow - Min Cut Theorem and the
Labelling Procedure.
Coursework Evaluation: The final grade will be
calculated as follows
- 4 tests: 15% each
- final exam: 40%
A mark of at least 40% on the final exam is required to pass the
course. See also Attendance below.
Tests:
- There will be 4 take-home tests during the term. The dates are
Jan. 29, Feb. 26, March 12, and March 26 (Friday 2pm - Saturday
2pm).
- Each test should be completed within 90 minutes, however,
students will have a 24 hour-window to submit each test. Please plan your life
accordingly.
- Test will be submitted on Brightspace.
- If a student misses a test for a valid, serious reason (e.g.
serious illness or death in the family) and provides a proof of
extenuating circumstances, then the weight of the test will
carry over to the final exam.
- A take-home test may be converted to an online test if such
a need arises.
Online tests/exams: The
final exam and online tests (if any) will be proctored using Zoom. Students must have high-speed
internet and a camera.
Attendance: In order to
pass the course, students are
expected to attend most lectures. In
addition, each student must attend at least one one-on-one meeting
with the professor (on Zoom, with video) during the term.
Academic Integrity: Students
are advised to carefully examine the university
guidelines on academic integrity.
Re-marking: Before sending a
remarking request, carefully study the posted solution of the test.
Afterwards, if you are still convinced that your test needs to be
remarked, submit the request (carefully pointing out the presumed
error) within 14 days after the marked paper was returned to you. No
remarking requests will be accepted after this deadline.
Important Dates:
- Jan. 11: first class
- Jan. 29: Test 1
- Feb 14-20: reading week
- Feb. 26: Test 2
- Mar 12: Test 3
- Mar. 26: last day to withdraw
- Mar 26: Test 4
- Apr. 2-5: Easter break
- Apr. 12: last class
- Apr. 16-29: final exams