CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

Category Archives: Admin

Karger’s min-cut algorithm

Hey, it may be useful for today’s lecture if you have a quick read over Karger’s randomized algorithm for min-cuts. Just the basic algorithm and analysis—we won’t need the improved Karger-Stein variant.


HW3 Graders

Hi, if you volunteered to help grade HW3, please send me mail (if you haven’t already done so). Thanks! –Anupam

Heads-up for today’s lecture

Today’s lecture will not have notes (like the great ones Avrim’s been handing out), sorry! So you might want to bring along some paper and pencils to take your own notes. 🙂

Also, if you have a minute, look over the randomized rounding algorithm/proof for low-congestion routing we saw in the previous lecture: we’ll try to talk about its derandomization today (among other things).


This is the course blog for the Spring 2011 version of the CMU Randomized Algorithms course. Please watch this blog, and the course web page, for announcements and updates about the course.