Advanced topics in algorithms

Spring 2011/2012, Tel Aviv University

Lecturer: Haim Kaplan
Time: Wednesday, 16-19
Place: Physics 222

Announcements:

         In response to a few questions we added some more information to the last presentation on planar graphs. In particular we tried to clarify the definition of a leftmost path from s to t in a general directed planar graph

         Homework 5 contains 2 problems on planar graphs, just for you to practice, don't hand it in. I added a sketch of the solutions below.

         Homework 3 and 4 are graded, you can pick it up at my office.

         Final exam is set to be on Friday July 20 at 9am

         The exam will take 3 hours. You would have to choose 3 questions out of 5

         This link contains 3 questions that you could use to prepare for the exam, I corrected a few minor mistakes in question 2 that you pointed out.

Tentative topics:

         Totally monotone matrices and some applications

         Splay trees.

         Dynamic trees

         Maximum flow

         Minimum cost flow

         Finger search trees and their applications

         Distances in graphs

         Persistent data structures

 

Presentations

 

         Totally monotone matrices and the SMAWK algorithm

         The concave least weight subsequence problem

         Submatrix maximum queries in Monge matrices

         Approximate optimal search trees (Following the class, I prepared an alternative presentation of the same algorithm that does not split the items into two equal halves to begin with, as I did in class. It may be more natural, take a look here)

         Finger search trees

         SSSP inside a polygon (This presentation was revised after class to clarify some questions that came up)

         Splay trees

         Maximum flow

         Dynamic trees

         Minimum cost flow

         Dynamic spanning forest (planar graphs)

         Dynamic connectivity (general graphs)

         Maximum flow in planar graphs

         More on maximum flow in planar graphs

 

List of homework

 

         Homework 1 (there were a few minor mistake in q. 4, now corrected.)

         Homework 2

         Homework 3

         Homework 4 (I corrected mistakes in q. 4 and q. 5)

         Homework 5

 

Selected solutions (by you guys), please use with care, answers often are not perfect but the best we could find

 

         Homework 1 c.1 c.2

         Homework 2 c.1 c.2

         Homework 3 c.1 c.2

         Homework 4 c.1 c.2

         Homework 5 (sketch)

 

Bibiliography lists

 

         Totally monotone matrices and the SMAWK algorithm

         Finger trees, optimal search trees, splay trees, and maximum flow

         Minimum cost flow, dynamic connectivity

         Maximum flow in planar graphs