Overview
Networks are pervasive in everyday life;
street-networks connect cities, electrical and phone networks connect our
homes, social networks connect friends and associates… The list of examples is
endless. In this course we will study optimization problems in domains that
have network structure. An example of a typical network question that we will
study is the following:
What is the
shortest route between two points A and B in a given network?
We will see that this question, as
well as many others, have efficient solutions. Students taking this
class will learn (a) how to develop mathematical models for network flow
optimization problems, and (b) how to solve problems in these models using fast
algorithms. Specific topics that we will cover include:
Prerequisites
The prerequisites for this class are Math 239/249
(Introduction to Combinatorics), and CO 350/355
(Linear Optimization). In particular, we will assume familiarity with the
following topics:
·
[Math 239] Undirected
graphs, walks, paths, cycles, cuts, trees
·
[CO 350] Linear Programs: optimal
solutions, duality, …
Chapter 1 of the course notes reviews some basic facts
from graph theory.
Grading
|
Assignments |
15% |
|
Midterm |
35% |
|
Final |
50% |
Reading
Material
The reading for this course is mainly from “Course
notes for CO351: Network Flows”, which can be purchased at Campus Copy -
Math (MC 2018). It is highly recommended that you purchase these notes. Any
supplementary material will be posted on the course web page.
Grade Change Policy
For assignments and the midterm, any grade change
requests must be submitted to your instructor within one week of
the receipt. Grades will not be changed if requested any later.
Cheating Policy
While it is acceptable for students to discuss the
course material and the assignments, you are expected to do the assignments on
your own. Copying or paraphrasing a solution from some fellow student, or
old solutions, qualifies as cheating and the TA is instructed to actively
look for suspicious similarities when grading.
If you have gotten an idea from another student, it is
good practice to write your own version of the solution and acknowledge the
assistance you received. An example of how this might be done is: "The
idea for this solution was suggested to me by Jane Doe." Another
possibility, if there was an exchange of ideas, is: "I discussed this
problem with Jane Doe. The solution presented is based on that
discussion."
All students suspected of cheating will automatically
be reported to the Undergraduate Associate Dean. They will receive no credit
for the assignment in question, and in addition any penalty that the associate
dean's office prescribes. Students who are unsure whether an action constitutes
an offence, or who need help in learning how to avoid offences should seek
guidance from the instructor. For information on categories of offences and
types of penalties, students should refer to Policy
#71, Student Academic Discipline.
On the INC Mark
A grade of INC will only be
awarded to students who cannot write the final exam for reasons acceptable to
the Math Undergrad Office (MUO) (you must submit documentation to MUO and they
should approve it). In addition such students need to be in good standing prior to the
final exam. To be in good
standing a student must have submitted and passed all assignments,
written and passed the midterm exam, participated in the course project.
Students with disabilities
The Office for Persons with Disabilities (OPD),
located in Needles Hall, Room 1132, collaborates with all academic departments
to arrange appropriate accommodations for students with disabilities without
compromising the academic integrity of the curriculum. If you require academic
accommodations to lessen the impact of your disability, please register with
the OPD at the beginning of each academic term.