Learning objectives

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.

• Foundations of Computer Science , a free textbook written by A. Aho and J. Ullman
• The Art of Mathematics, Coffee Time in Memphis, by Béla Bollobás. (electronically available at our library)
• Proofs from the Book, by Martin Aigner, Günter M. Ziegler. (electronically available at our library). Also a translation into Turkish exists.

Courses on Applications

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

Grading

• Class attendance, 10%
• Midterm Exam, 30%
• Quizzes, 30%
• Final Project, 30%




---

Schedule (Delayed by 2 weeks after March,12)

Date	Topic	Notes	Reading on Applications
Feb. 27	Introduction and Counting I: The Binomial Theorem, Double Counting, Jensen's Inequality, The Averaging Principle (Jukna) 1, (West) 1.1, 1.2	Notes	An Application of Jensen's Inequality in Machine Learning Mathematical (mostly Combinatorial) Tools used in Machine Learning
Mar. 5	Trees and Distance (West) 2.1
Mar. 12	Maximum Matchings in Bipartite Graphs Augmenting Path Algorithm (West) 3.1	Notes, Print Version
Apr. 2	Matchings and Covers in Bipartite Graphs (West) 3.1
Apr. 9	Matchings in General Graphs (West) 3.3 Edmonds's maximum-cardinality (nonbipartite) matching algorithm. (West) 3.2, (Cook) 5.2, (Tarjan) 9.3
Apr. 16	Cuts and Connectivity (West) 4.1	Notes, Print Version
Apr. 23	Official Holiday
Apr. 30	k-connected Graphs (West) 4.2
May 7	Vertex Coloring (West) 5.1,2	Notes, Print Version	Coloring Large Complex Networks
May 14	Application of the Probabilistic Method on Graphs (Mitzenmacher and Upfal) 6	Notes
May 21	Algorithmic Applications of Lovász Local Lemma (Mitzenmacher and Upfal) 6 Planar Graphs (West) 6.1	Notes(LLL) Notes(Planar), Print Version	Gödel Prize Winner (2020) A Constructive Proof of the General Lovász Local Lemma
May 28	Hamiltonian Graphs (West) 7.2 Special Topics: Higher-order graph clustering with network motifs	Notes, Print Version
June 4	Project Presentations		--
June 11	Project Presentations		--



© 2020 Hacettepe University