Course Summary

Fridays hours 2-3 ( i.e., 9:45 - 11:30)   Location: Paviljoen a12b

Instructions

Wednesdays  (Hours 7-8, i.e. 15:45 - 17:30)
Location:  Matrix 1.64

Exam

(The course will consist of lectures and instructions. See detailed schedule below)

Instructors:  Nikhil Bansal -   MF 4.095

Ph: 040 247 2299. Email:  n dot bansal at tue dot nl

Jesper Nederlof    Email: j.nederlof at tue.nl

Teaching Assistant: Shashwat Garg - MF 4.145.  Email:  s.garg  at tue dot nl,   Office Hours:   12:30 -  13:30  on Thursdays

Prerequisites: This is a masters level class and a basic background in algorithms and discrete mathematics is expected.  Above all, the most important prerequisite is mathematical maturity. If you are not familiar with certain topics, you can contact me after the class to extra background reading material.

Goals:  At the end of the course, the student should be well-versed in basic concepts of graph theory such as coloring, planarity, independent sets, flows etc. They should understand basic proof techniques in graph theory such as the probabilistic method. They should also be able to use various algorithmic techniques.

Grading Policy: The final grade will be based on homeworks (20%), midterm exam (30%) and final exam (50%).

Homeworks: There will be three homeworks, which can be done in groups of up to 2 people. All homeworks must be written in Tex, and the proofs must be clearly written.

Exercise Sessions: The exercises consists of basic problems which you should master. The exercises sessions are for solving exercises, discussing homework problems (after their due date).

Study material:

There is no particular textbook for the course. The relevant reading material will be provided during the course.

Tentative Topic List:

• Concepts from Graph Theory
• Matchings: Bipartite and general graphs, related min-max theorems. Applications. Chinese Postman Problem, TSP.
• Planarity:  Duality, finding max cut in planar graphs, planarity testing algorithm, planar separator theorem and applications.
• Flows: Max-flow Min-cut, min-cost circulations and their various applications, connectivity results.
• Operations on Graphs:  Line Graphs. Application to independent set hardness.
• Probabilistic Methods: First and second moment methods, Karger's min-cut, polynomial identity testing.
• Extremal graph theory: Basic results
• Algebraic Methods: Graph expansion, Determinants, Permanents
• Algorithmic Concepts:
• Min-max relaxation and polynomial time algorithms
• Dynamic Programming
• Exact Algorithms: Color coding, algebraic techniques

Note: The above list is tentative.

Lectures:

(Tentative Plan,  will be updated as the course proceeds)

 Lecture Date/Location Topic Reading Material L1 Feb 3, We Introduction, basic graph concepts, Matchings, (N) Lecture 1 (pdf),    Exercise 1 (pdf); Nice slides on Hall's theorem; its proof and applications L2 Feb  5, Fr Maxflow-mincut, applications (N) Exercise 2  (pdf);  basics of max-flow (pdf)  (first 3 sections) Applications of max-flow and circulations (pdf) Feb  5, Fr Homework 1 released HW 1  (pdf) ;   Sample solutions from previous year (pdf) Feb 10, We no class Feb 12, Fr no class L3 Feb 17, We Planarity testing and planar separator theorem  (N) Lectures 3 and 4 (pdf).  Ex 3 (pdf) (there are no separate exercises for L4 other than in the slides) Section 1.5.1 here  has the planarity testing algorithm we discussed. L4 Feb 19, Fr Planar Duality and application to exact algorithm for planar  max-cut (N) Sariel Har-Peled's proof of planar separator thm. Feige's notes on planar max-cut (first page).  Excellent optional reading:  Has proof of Koebe's theorem! Feb 24, We Homework 1 due L5 Feb 24, We Exponential Time (J) Lecture 5 (pdf, ppt) exercise sols (pdf) L6 Feb 26, Fr Dynamic Programming and Inclusion-Exclusion (J) Lecture 6 (pdf, ppt), subsetsum.xls, exercise sols (pdf) Feb 28, Fr Homework 2 released HW 2 (pdf) L7 Mar 2, We First 2 hours: Midterm (J) Treewidth introduction (J) You are allowed to bring one sheet of paper written on both sides with notes to the midterm. From Jesper’s part (lecture 5 and 6), Section 5.6.2, Section 6.8 and parts of exercises 6.7 and 6.9 will not be examined. Mar 4, Fr Treewidth (J) Lecture 7 (pdf, ppt) exercise sols (pdf). For information on DFS, BFS see here and here. Only undirected graphs are relevant for us. L8 Mar 9, We Probabilistic arguments: First moment method; crossing number inequality, Ramsey results, tournaments with no winners. Discuss midterm solutions (N) Lecture 8 (pdf). Ex 8 (pdf), preliminaries on probability (pdf) Mar 11, Fr Homework 2 due L9 Mar 11, Fr Probabilistic arguments: alterations, stable sets, Ramsey results (N) Lecture 9 (pdf). Ex 9 (pdf). L10 Mar 16, We Algebraic algorithms: PIT, dense 3-colorable graphs, 2SAT via random walks (N) Last 2 hours (15:45 - 17:30): midterm resit (N) Lecture 10 (pdf) L11 Mar 18, Fr Probabilistic Exponential Time Algorithms (J) Lecture 11 (pdf,ppt) exercise sols (pdf) Mar 19, Fr Homework 3 released HW 3 (pdf) L12 Mar 23, We Vector coding, Bjorklund's algorithm (J) Lecture 12 (pdf,ppt) exercise sols (pdf) L13 Mar 30, We Matrix Multiplication, APSP (J) Lecture 13 (pdf,ppt) exercise sols (pdf) Apr 01, Fr Problem session / question hour / margin for going to slow (J) Extra practice exercises (pdf) sols (pdf) Apr 04, Mo Homework 3 due Apr 14, Th Exam