Posted by: atri | December 2, 2010

Lect 37: Weighted Interval Scheduling

In today’s lecture, we looked at how we can use memory to implement the recursive algorithm for the weighted interval scheduling problem faster. We also saw how to construct the optimal schedule just from the optimal values. The slides have been uploaded.

Next lecture, we will study an iterative version of the recursive algorithm. This material is from Sec 6.2 in the book. Then we will start talking about the problem of shortest path in graphs with negative edge lengths. This material is from Sec 6.8 in the book.

There will be no student blog post for this lecture.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: