Planar graphs arise in applications such as road map navigation and logistics, graph drawing, and image processing. Our focus will be on recent research results for classical problems that exploit planarity, for example: Travelling Sales Person, Shortest Paths, Multicommodity Flow, and Maximum Flow. We will also cover the data structures that are commonly used by these algorithms, for example: Dynamic Trees.

This class will emphasize using the structure of a problem to design the best (fastest and simplest) algorithm to get the job done.

The class is a lecture class complete with homeworks (about 8 over the semester) and exams (2 testing basic course material).  There are two types of questions for the homeworks: "Prove ...." and "Give an algorithm for ....".  Algorithms must be given by detailed pseudocode.  For extra credit, you can implement the algorithms (instead of giving pseudocode).

Prerequisite: CS 157 or equivalent
(introductory algorithms).

News:

11/10: The final exam is scheduled for December 13 at 2.30.  Please let us know if there is a conflict.  Also, the scribe notes are up to date.

10/19: I've added a link to "19 proofs of Euler's formula" to the calendar page.  There is a midterm on Tuesday.  We also have to schedule the final exam:  check your schedule for the week of December 12.

09/22: Lots of updates: see the course calendar.  There is no homework this week.

09/16: Homework 2 is out.  More utility code for implementations will be available soon.

09/13: We will have an OCaml tutorial after class on Thursday 09/15 in CIT 506.

09/12: There is now an example of OCaml code using the utility code provided as well as updated utility code.

09/11: Please see the coding guidelines and a description of how graphs are implemented before handing in your assignments. OCaml implementations have an extension until the start of class on the 20th.

09/08: Homework assignments are posted on the course calendar. They will be due by the start of class a week later. Note that the first homework is out.

09/07: If you have questions, please email both .

09/06: First class at 2.30 in CIT 506