2MMD30: Graphs and Algorithms (Semester B Quartile 3, 2016)

Nikhil Bansal and Jesper Nederlof

 

 

 

 

 

Course Summary

       This course will have multiple objectives. First, we will study several basic concepts in graph theory, getting a broad introduction to the area and the different techniques used. Next, we will study the algorithmic aspects of various graph theoretic problems. The focus will be on understanding how structural results in graph theory are useful in designing algorithms for various fundamental  and practical optimization problems.

For more details, see previous editions of the course (2012, 2013, 2014, 2015) 

Administrative Information

Lectures

Wednesdays  hours 5-6 ( i.e., 13:45 - 15:30)
Location:  Matrix 1.50

 

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  

 

Fridays  (Hours  4, i.e. 11:45 - 12:30)  
Location: Paviljoen a12b

Exam

Thursday 14-04-2016 at 09:00-12:00

(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:

 

 

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