· 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.
· 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
· 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)
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