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)
·
SSSP
inside a polygon (This presentation was revised after class to clarify some
questions that came up)
·
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 4 (I corrected
mistakes in q. 4 and q. 5)
Selected solutions (by you
guys), please use with care, answers often are not perfect but the best we
could find
Bibiliography lists
·
Totally monotone matrices and the SMAWK
algorithm
·
Finger trees,
optimal search trees, splay trees, and maximum flow