
2MMD30: Graphs and Algorithms (Semester B Quartile 3, 2016)Nikhil Bansal and Jesper Nederlof 






Lectures 
Wednesdays hours 56 ( i.e., 13:45
 15:30)


Fridays hours 23 ( i.e., 9:45  11:30)

Instructions 
Wednesdays (Hours 78, i.e. 15:45  17:30) 

Fridays (Hours 4, i.e. 11:45
 12:30)

Exam 
Thursday 14042016 at
09:0012:00

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 wellversed
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:
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 
Maxflowmincut, applications (N) 
Exercise 2 (pdf); basics of maxflow (pdf) (first 3 sections) Applications of maxflow and circulations (pdf) 

Feb 5, Fr 
Homework 1 released 


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 maxcut (N) 
Sariel
HarPeled's proof of planar separator thm. Feige's notes on planar maxcut
(first page). Excellent optional reading: Has proof of Koebe's theorem! 

Feb 24, We 
Homework
1 due 

L5 
Feb 24, We 
Exponential Time (J) 

L6 
Feb 26, Fr 
Dynamic Programming and InclusionExclusion (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) 

L10 
Mar 16, We 
Algebraic algorithms: PIT, dense 3colorable
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) 


Mar 19, Fr 
Homework
3 released 
HW 3 (pdf) 
L12 
Mar 23, We 
Vector
coding, Bjorklund's algorithm (J) 

L13 
Mar 30, We 
Matrix Multiplication, APSP (J) 

Apr 01, Fr 
Problem session / question hour / margin for going to slow (J) 


Apr 04, Mo 
Homework 3 due 


Apr 14, Th 
Exam 
