Math 442 - 201, Term 2 2012

Optimization in Graphs and Networks

Announcements

Announcements will be posted here from time to time. Please check regularly.

Midterm details now up.
Don't forget UBC will be closed February 11 2013, so no office hours that day. Please email me instead.
Congratulations on the midterm median of 80%! Enjoy your candy and have a good long weekend.
Since UBC is shut April 1 2013, there won't be office hours that day. Please email me instead and enjoy the long weekend.

Lecture details

Lecturer: S van Willigenburg , Math 208, 822-2630, steph at math splotch ubc splotch ca.
Location: TTh 11.00-12.30 MATX 1100.
Web page: http://www.math.ubc.ca/~steph/442/442.html
Office hours: Mon 10-11am, Thur 4-5pm, 15 mins just after class, and by appointment (not Wednesday). You can also email me anytime.

Course description

This is an introduction to graph theory. There will be emphasis both on proof and algorithmic techniques. Topics include tours and graphs, planarity, graph colouring, trees, shortest paths, flows, matchings. Prerequisite is Math 340.

Text

Robin J Wilson, Introduction to Graph Theory, Pearson. ISBN-13: 978-0-273-72889-4. Other books on the subject can also be found in the library around QA 166.

Homework

There will be a weekly homework assignment due on Thursdays at the start of class. The homework is the most important part of the course as most of your learning will take place while doing it. We will not accept late homework except in very unusual circumstances. We will, however, drop the lowest homework grade.

Exams

Midterm, Tuesday 5th February.
Final exam, Wednesday 24th April.

Calculators, books, notes etc are not permitted in either exam. Please bring your student ID to both exams.

Please note that there are no make-up or alternate exams, so make sure you do not make travel plans, work plans etc that will conflict. Valid documentation must be provided within 72 hrs if any consideration is to be taken for a missed midterm.

Grading

Your grade will be based on the homework (10%), the midterm (30 or 40%), and the final (60 or 50%), whichever gives you the best grade.

Since this is a Mathematics Majors course, there is a median grade of around 68% and students will be expected to perform calculations and construct rigorous proofs involving fundamental ideas of the course.

Working together and academic integrity

Homework: We have no objection to collaboration on the homework, provided that it is done in a way that maximizes the benefit of the homework to all people involved. It is our experience that you get

maximum benefit from a homework problem if you work hard on it alone before combining your ideas with someone else's,

no benefit from one person just telling another how to do a problem.

Regardless of whether you arrive at solutions in collaboration with others or alone, the paper that you turn in with your name on it should represent your own solutions, written in your own words.

In particular, you may not simply copy someone else's homework and turn it in as your own. Similarly, copying solutions that you might find on the web or from some other source is illegal.

These will all be treated as a violation of UBC's Academic Integrity Code. We take academic integrity very seriously and will follow university procedures in all cases of suspected cheating - disciplinary measures can result in expulsion.

Exams: There is anecdotal evidence that quite a bit of cheating occurs on campus. In an effort to prevent one common form of cheating, we will xerox a random sample of exam books before returning them.

Class etiquette

Use of cell phones (in any manner), laptops, iphones, Blackberries and other electronic devices during class is highly inappropriate, as it is distracting and disrespectful to fellow students and the instructor. Chatting with neighbours, even when whispered, is equally inappropriate. If you have a question then please ask the instructor so the whole class may benefit too.

Arriving late and leaving early is also discouraged. If it happens then please enter/leave the room silently and do not disrupt the other students or instructor. Thank you.

Assignments

Assignment 1, due Thursday January 10th.
Assignment 2, due Thursday January 17th.
Assignment 3, due Thursday January 24th.
Assignment 4, due Thursday January 31st.
No assignment due Thursday February 7th due to midterm.
Assignment 5, due Thursday February 14th.
Assignment 6, due Thursday February 28th.
Assignment 7, due Thursday March 7th.
Assignment 8, due Thursday March 14th.
Assignment 9, due Thursday March 21st.
Assignment 10, due Thursday March 28th.
Assignment 11, due Thursday April 4th.

Solutions

These are to help you study. Please make sure your solutions include full details and citations.

Assignment 1
Assignment 2
Assignment 3
Assignment 4
Assignment 5
Assignment 6
Assignment 7
Assignment 8
Assignment 9
Assignment 10
Assignment 11

Other handouts

Here are some more study materials I found to help, or might be interesting.

Two web pages about proofs can be found here and here.
Notes on how to take notes can be found here and here.
A paper by a learning psychology expert How to succeed in college: learn how to learn.
Practical advice on learning effectively.
Isomorphic graphs: it is hard.

Other useful links

Math department home page