## 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