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.
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