Instructor: Gwen McKinley (gmckinley@ucsd.edu) Course email address: 154-staff-G@ucsd.edu
Lectures: 1-1:50pm on MWF, in York Hall 2622
Discussion sections: Thursday afternoons
Office hours:
| Time | Room | Person |
|---|---|---|
| Mondays 2-4pm | AP&M 6402 | Gwen McKinley and Nicholas Sieger |
| Tuesdays 9-11am | AP&M 5801 | Erlang Surya |
| Tuesdays 11am-12pm | HSS 5041 | Shubham Sinha |
| Fridays 10-11am | HSS 4062 | Emily Zhu |
| Fridays 2-3pm | AP&M B412 | Gwen McKinley |
Finals week office hours:
Individual meetings: if you have a private issue you'd like to discuss, you can request a one-on-one appointment here.
For information on grading, textbook, acommodations, and more: see the Course Syllabus.
Due dates: here is a calendar of all homework due dates and quiz and exam dates.
Quizzes: There will be three Canvas quizzes, held on the dates below. Each quiz will be available during a 24-hour window (12am-11:59pm Pacific Time), and you will have 30 minutes to finish each quiz once you have begun.
Exams: There will be one in-person midterm exam and an in-person final exam, on the following dates:
Weekly homework assignments will be posted here. Homework is due by 11:59pm on Wednesdays, through Gradescope. The due dates are also listed on the calendar of assignments.
Note: there may be some slight changes to the assigments posted below (e.g., shifting a problem to a later homework), but I will do my best to finalize each assignment no later than one week before its due date.
Here is a tentative schedule of what will be covered in each lecture, together with the relevant section(s) of the book: Introduction to Graph Theory (Course Notes), by Professor Jacques Verstraete. This is a rough schedule, and there will be some give and take between lectures.
| Week | Date | Topic | Book Sections |
|---|---|---|---|
| 1 | 4/3 | Definition and basic properties of graphs (warm-up, slide 1, slide 2) | 1,1. 1.4 |
| 4/5 | Basic classes of graphs, Handshaking Lemma (warm-up, slide 1) | 1.3, 1.5 | |
| 4/7 | Subgraphs, walks (warm-up, slide 1, slide 2) | 1.6, 1.7, 2.1 | |
| 2 | 4/10 | Connected graphs, Eulerian graphs (warm up, slide 1) | 2.2, 2.3 |
| 4/12 | Finish Eulerian graphs, start Hamiltonian graphs (Example of Hierholzer's Algorithm) |
2.3, 2.5 | |
| 4/14 | Finish Hamiltonian graphs | 2.5 | |
| 3 | 4/17 | Bridges and trees (slide 1, warm-up, slide 2) | 3.1 |
| 4/19 | Finish trees, depth-first search | 3.1, 3.4 | |
| 4/21 | BFS, Characterizing bipartite graphs (warm-up, slide 1) | 3.2, 3.3 | |
| 4 | 4/24 | Characterizing bipartite graphs (warm-up, slide 1) | 3.3 |
| 4/26 | Prim's and Kruskal's Algorithms (warm-up, slide 1, slide 2) | 3.5 | |
| 4/28 | Independent sets and covers (warm-up, slide 1, slide 2, slide 3) | 5.1 | |
| 5 | 5/1 | Finish independent sets and covers | 5.1 |
| 5/3 | Hall's Theorem (warm-up) | 5.2 | |
| 5/5 | Finish Hall's Theorem | 5.2 | |
| 6 | 5/8 | Edge coloring, Konig's Theorem (warm-up, slide 1, slide 2) | 6, 6.1 |
| 5/10 | Midterm | ||
| 5/12 | Finish Konig's Theorem (warm-up, slide 1) | 6.1 | |
| 7 | 5/15 | Intro to vertex coloring (warm-up, slide 1, slide 2) | 6 |
| 5/17 | Degenrate graphs, start Brooks' Theorem (warm-up, notes) | 6.4, 6.3 | |
| 5/19 | Finish Brooks' Theorem (notes) | 6.3 | |
| 8 | 5/22 | Planar graphs, Euler's formula (warm-up, slide 1) | 7.1 |
| 5/24 | More on planar graphs, Kuratowski's Theorem, Wagner's Theorem | 7.3 | |
| 5/26 | Coloring planar graphs (warm-up, slides) | 7.3 | |
| 9 | 5/29 | No Class (Memorial Day) | |
| 5/31 | Flows, capacities, and cuts (warm-up, slide 1, slide 2) | 8.1-8.3 | |
| 6/2 | The Ford Fulkerson Algorithm | 8.4 | |
| 10 | 6/5 | The Max-Flow Min-Cut Theorem (warm-up, slide 1, slide 2) | 8.3 |
| 6/7 | Fun problems :) | ||
| 6/9 | Review | ||
| Finals | 6/15 | Final Exam (Thursday of finals week, 3-6pm) |