Web Analytics Made Easy - StatCounter

CMP 694 - Graph Theory (Spring 2025)

CMP 694 - Graph Theory (Spring 2025), D5 — Time: Monday 9:30 - 12:20

Schedule

Instructor

Lale Özkahya

Office Hours:
Email to arrange an appointment.

All communication will be on https://piazza.com/hacettepe.edu.tr/spring2025/cmp694

Learning objectives

This is an in-depth course on graph theory and its applications.

Text

  • Introduction to Graph Theory, by Douglas B. West.
  • Extremal Combinatorics with Applications in Computer Science, by Stasys Jukna. (electronically available at our library)
  • Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal.
  • Cook/Cunningham/Pulleyblank/Schrijver, Combinatorial Optimization.
  • Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms.
  • Korte/Vygen, Combinatorial Optimization.
  • Kozen, Design and Analysis of Algorithms.
  • Papadimitriou/Steiglitz, Combinatorial Optimization.
  • Schrijver, Combinatorial Optimization: Polyhedra and Efficiency.
  • Tarjan, Data Structures and Network Algorithms.

The texts below are not required. Reading materials will be distributed as necessary. Reading assignments will be posted on the schedule, please check regularly.


Courses on Applications

  • CS 6241: Numerical Methods for Data Science (Cornell)

    • Grading

    • Midterm Exam 30%
    • Problem Session 30%
    • Final Exam, 40%
    • Attendance, 5% (Extra)


    Schedule

     Notes:
    Week Topic Notes Exercises (DBW)
    1 Introduction and Counting I: The Binomial Theorem, Double Counting,
    Jensen's Inequality, The Averaging Principle
    (Jukna) 1, (West) 1.1, 1.2    		1, 2 1.1: 10, 11, 12, 13, 18, 29, 31
    1.2: 1, 2, 8, 10, 11, 14, 16, 21
  • Mathematical (mostly Combinatorial) Tools used in Machine Learning
    • 2 Trees and Distance
    (West) 2.1     		Notes 2.1: 4, 6, 7, 13, 14, 15, 16, 18, 19
    3 Maximum Matchings in Bipartite Graphs
    Augmenting Path Algorithm
    (West) 3.1    		 Notes 3.1: 1-17, 28, 36, 39, 40
    4 Matchings in Graphs
    (West) 3.3    		 Notes 3.3: 1-5, 8, 9, 11, 14, 15
    5 Cuts and Connectivity
    (West) 4.1    		 Notes
    6 Problem Session
    7 Holiday
    8 Midterm Exam
    9 k-connected Graphs
    (West) 4.2    		 Notes
    10 Vertex Coloring
    (West) 5.1,2    		 Notes
  • Coloring Large Complex Networks
    • 11 Planar Graphs
    (West) 6.1    		 Notes
    12 Hamiltonian Graphs
    (West) 7.2    		 Notes
    13 Problem Session
    14 National Commemoration Day Notes


    © 2025 Hacettepe University