[uwl] [math@uwl] [will@uwl]

Graph Theory
Fall 2007,
MTH 317 Cr. 3
MWF 8:50-9:45 in 113 Cowley Hall
Dr. Todd Will, 2030 Cowley, 785-8388
Office Hours: T,Th: 9-11; MWF: 3:15-4:15
email: will.todd@
web: www.uwlax.edu/faculty/will/

Course Description: An introduction to graph theory emphasizing algorithms. We will cover the basic graph properties of isomorphism, Euler circuits, Hamilton cycles, planarity, and graph coloring. We will be interested in determining whether specific graphs have these properties, and proving general theorems which guarantee when a collection of graphs has one or more of these properties. We will cover basic graph algorithms: DFS, BFS, MST, TSP, shortest paths, network flows, and bipartite matching. We will learn how to apply each of these algorithms and learn why they are guaranteed to provide the correct answers.  The final few weeks of the semester we will cover either elementary counting techniques from Tucker's book or additional graph theory topics from West's book.

Prerequisite: MTH 225.  You will need to write proofs for this course!  

Primary text: Applied Combinatorics by Alan Tucker
Possible secondary text: Introduction to Graph Theory by Doug West

Attendance: If you miss class due to circumstances beyond your control or if despite efforts you do not understand material covered in class, I am eager to provide additional help.  If you can't meet during my office hours, feel free to contact me by phone or email to set up an appointment.   On the other hand if you choose to skip class or sleep through class, you should not expect me to provide private tutoring on the material you missed.

Important Dates:  Tentative exam dates are 28-Sep, 26-Oct, 30-Nov.  No class on Friday, 23-Nov.  The Final Exam is on Friday, 14-Dec, 2:30-4:30pm.

Grading:  Your final grade will be based on homework (150pts), presentations & participation (150pts), three exams (150pts each),  and a comprehensive final exam (250pts).  Percentage to Letter Grade guarantees:  92 is an A, 82 is a B,  70 is a C, 60 is a D.  Cutoffs for AB and BC will be determined based on clustering of scores. 

Homework:  You are encouraged to discuss homework problems with one another.  However, under no circumstances should you lend your solutions to another student to read or copy.  Discussions about homework must take place face to face.  There may be an occasional quiz asking you to reproduce a solution to a homework problem. 

Presentations and participation:  You will be asked to prepare and present exercises, examples, definitions, theorems, and proofs from our text.  You will also be expected to be an active participant during your classmates' presentations. 

Exams:  Midterms exams will have both in-class and take-home components.  The final exam will be comprehensive with an emphasis on material covered after the third exam.

Accommodations:  Any student with a documented disability (e.g., physical, learning, psychiatric, vision, or hearing, etc.) who needs to arrange reasonable accommodations must contact the instructor and the Disability Resource Services office (165 Murphy Library) at the beginning of the semester.

Page corrections to