Takehome Midterm and Assignment 4

Hi,

The take home midterm is available on the website and is due Monday before class. The scoring formula is mentioned once again on the first page.

Also, the due date of homework 4 is moved back to Wednesday.

Several people have asked about one complication resulting from question 2.1 on homework 4. The issue is about how to insert vertices in front of other vertices in the ordering and still be able to query whether one vertex comes before another in the ordering. There is a way to get around this issue by processing the entire graph again globally after building partial information. However, you can also use a data structure by Dietz and Sleator that supports both operations in O(1) worst case time. It can be found at http://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf if you are interested.

Richard,