Posted by: atri | November 8, 2010

Lect 29: Cut Property Lemma

In today’s lecture, we quickly proved the optimality of Prim’s algorithm using the “cut property” lemma. Then we proved the cut property lemma. The slides have been uploaded. (Feel free to use the comments section if you figured out the mother-father-son trio on slide 6.)

Next lecture, we will quickly see how to get rid of the assumption that all the edge costs are distinct and then move on to the next algorithmic technique, which will be divide and conquer. The latter material will be from Sec 5.1 in the book.

Below are links to the student blog posts for this lecture:


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s


%d bloggers like this: