CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

Monthly Archives: April 2011

Final exam

on the webpage, or here. Good luck!

Update: Remember it’s due 48 hours after you start, or Friday May 6, 11:59pm, whichever comes first.

Fixes: 1(b): “feasible solution to the LP plus the odd cycle inequalities.” And you need to only show the value is m(1 - O(\varepsilon)) whp.

FCEs, Final, etc.

Thanks for the great presentations yesterday, everyone!

The final will be posted on the course webpage Friday 4/29 evening at the latest, I will post something on the blog once we’ve done so. You can take it in any contiguous 48 hour period of your choice — just download it when you are ready, and hand in your solutions within 48 hours of that. Slip it under my door (preferably), or email it to me otherwise. We’ll stop accepting solutions at 11:59pm on Friday 5/6.

The course FCEs are now online: please give us your feedback!!

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.

HW #6 Open Thread

HW#6 is out, it’s a short one. Due next Wednesday April 27th.