|
|
Course Outline: Graph Theory concerns the study of sets of vertices, some pairs of which are connected by edges. These objects, known as graphs, can be used to model many different situations. For example, given a set of cities and driving distances between certain pairs which have roads between them, there is a graph theory algorithm to find the shortest path between any given pair of cities. Similarly, we might want to find the shortest total amount of road necessary to build in order to make sure that it is possible to travel between any pair of cities. Given a set of cell phone towers, some pairs of which can communicate with one another, we could determine its robustness by finding the smallest number of towers which, if disabled, will cause a disconnection in service. There are many applications, but we will also study properties of
graphs and prove theorems which don't seem to be of immediate consequence.
We will do this because graphs are beautiful! We'll work through
as many chapters of the textbook as possible in a brisk, yet reasonable, pace.
Class Meetings: We will meet in Porter Hall 100 on Mondays,
Wednesdays and Fridays from 12:30pm to 1:20pm. Carmeline Dsilva and Dan Kilgallin
will hold recitation on Thursdays; Section A meets 11:30-12:20 in Wean 5302,
Section B meets 12:30-1:20 in GHC 4307, and Section C meets 10:30-11:20 in Doherty 2210.
Additional enrichment sessions may be scheduled on Tuesday evenings.
Office: Wean 6301 (Bohman) and Wean 6117 (Mackey) Phone: 268-6881 (Bohman) and 268-2545 (Mackey) Email: tbohman@andrew.cmu.edu
and jmackey@andrew.cmu.edu
Office Hours: MW 10:30-11:30 (Bohman), TTH 12:30-1:30 (Mackey), and by appointment.
TA Office Hours: W 11:30-12:30 and 2:30-3:30 in GHC 4126 (Dan), W 5-7 in Wean 6215 (Carmeline)
Help: In addition to class, recitation sessions, and office
hours, the University operates a walk-in Peer Tutoring Center in the Mudge
Library and the Donner Reading Room on Sunday-Thursday evenings from 8:30 to 11:00pm.
Individualized tutoring and other help options are also available through
Academic Development.
Homework: Homework exercises are an essential part of the course. It is difficult to understand the material and do well on the exams without working through the homework problems in a thoughtful manner. Discussion of the homework with your peers is encouraged, but copying any part of another person's homework is not permitted. Please think about the problems posed, your strategies, and the validity of your logic and explanations. Homework is due at the beginning of recitation. Each homework problem should
be written on a separate sheet of paper with your name and the recitation section
you attend in the top right-hand corner. Homework turned in after
recitation has begun, but before the solutions are posted will receive
half credit. Late (or early) homework may be turned in to my
mailbox in Wean 6113, but you must first alert me to this fact with a
brief email of explanation. No credit will be given for homework turned in
without explanation or after the solutions have been posted.
Midterms: There will be three out-of-class midterms (held from 6-8pm in DH 2210) and a cumulative final exam (scheduled by the Registrar). Class will not be held from 12:30-1:20 on the dates of the midterms. The dates of the midterm exams are as follows: Midterm 1: Wednesday,
February 10, 6-8pm in DH 2210 Midterm 2: Wednesday,
March 24, 6-8pm in DH 2210 Midterm 3: Wednesday,
April 21, 6-8pm in DH 2210 Grading: Your course grade will be determined as follows:
Each of the two high midterm scores: 20% Calculators: Calculators and other technology will be of little use in this course.
Calculators and other electronic devices will not be allowed during the exams.
|
