Links:    Home     Homework     Exams     Calendar     Syllabus     Resources

Math 154: Discrete Mathematics and Graph Theory
Winter 2020, Prof. Tesler
Calendar

Updated 3/11/20


Note: This calendar is approximate and is subject to revision.
Chapter numbers are for the class textbook by Verstraete.

Lectures will be a mix of chalkboard and slides.
If there are slides, they'll be posted below.
Slides are subject to revision.

Week 1
Jan 6 Syllabus

Introduction to Graph Theory (slides 1-21)
  • Chapter 1 (1.1, 1.3-1.6) and Appendices A.2-A.3
  • Ch. 1.2 is optional; it's an overview of topics in the book.
Jan. 8
  • slides continued (21-37)
Jan. 10
  • slides continued (rest of slides)

Subgraphs, walks, Eulerian and Hamlitonian graphs (slides 1-17)
  • Chapters 1.7 and 2 (2.1-2.6; skip 2.7)
Week 2
Jan. 13
  • slides continued (18-35)
Jan. 15
  • slides continued (36-47)
Jan. 17
  • slides continued (rest of slides)

Week 3
Jan. 20 Martin Luther King, Jr. Holiday
Jan. 22 Trees (slides)
  • Chapter 3.1

Spanning tree algorithms (slides 1-3), (worksheets)
  • Chapter 3.2-3.4
  • Please print out the worksheets at full size to facilitate note taking in lecture.
Jan. 24
  • slides continued (4-51) + worksheets
  • The DFS example on the slides has a mistake, so I used worksheets on the projector instead. There were also several other examples on the worksheets on the projector. See the 1/24 and 1/27 podcasts to review it.
Week 4
Jan. 27
  • slides continued (rest of slides and worksheets)

Weighted graph algorithms (slides 1-14)
  • Chapter 3.5-3.6
Jan. 29
  • slides continued (14-35)
Jan. 31
  • slides continued (rest of slides)

Connectivity
  • Will be on the chalkboard, not on slides.
  • Chapter 4.4-4.5 and 4.7. Skip other parts of Chapter 4 for now (may do later in the quarter if time permits).
Campuswide deadline to drop without a "W"
Week 5
Feb. 3
  • Chapter 4 continued
  • Example for question asked in class about a graph with λ(G)<δ(G), namely, 1<2: (drawing)

Matchings
  • Chapter 5 intro to matchings (on chalkboard)
Feb. 5
  • Chapter 5.1: Independent sets, matchings, vertex and edge covers

Feb. 7 Midterm
Week 6
Feb. 10 Matchings: Hall's Theorem, applications, and generalizations (slides 1-24) [slides revised 2/10 after class]
  • Chapter 5.2-5.8
Feb. 12
  • slides continued (25-39, 57-61)
Feb. 14
  • slides continued (rest of slides)

Campuswide deadline to drop with a "W"
Week 7
Feb. 17 Presidents' Day Holiday
Feb. 19 Vertex and Edge Colorings (revised slides 1-24, 45-48) [slides revised again 2/23]
  • Chapter 6
Feb. 21
  • slides continued (25-39)
Week 8
Feb. 24
  • slides continued

Planar Graphs (slides 1-16)
  • Chapter 7
  • Covering 7.1-7.3 in full, and parts of 7.4 and 7.6-7.8. Skipping 7.5.
Feb. 26
  • slides continued (17-34)
Feb. 28
  • slides continued (rest of slides)

Week 9
Mar. 2 The Max-Flow Min-Cut Theorem (slides 1-31)
  • Chapter 8
Mar. 4
  • slides continued (32-48)
Mar. 6
  • slides continued (rest of slides)

Stable Matchings: The Gale-Shapley Algorithm (slides 1-8)
Week 10
Mar. 9
  • slides continued (up to 31)
Mar. 11
  • slides continued (rest of slides)

Extremal Graph Theory (slides 1-26)
  • Chapter 9-9.2 (+ Ramsey Numbers, not in the book)
Mar. 13
  • slides continued
Week 11
Wed.
Mar. 18
Final exam, 3-6 p.m.