CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

Category Archives: Homework

HW #6 Open Thread

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


HW #4 Open Thread

Please ask your HW#4 questions here. Here’s one:

For Exercise 2, Part A, the algorithm says to “Choose 2m+1 elements S uniformly at random…”. Does this mean with replacement, or without replacement? In other words, are we choosing 2m+1 elements one at a time, each with equal probability of picking any of the elements from A, such that S might be a multiset? Or, are we choosing a set of 2m+1 elements from A, where each set has probability 1 / binom(n, 2m+1) of being picked?

It does not matter; you can do it either way. Though the analysis for the process where you choose independently with replacement is slightly simpler.

Update: the phrasing for problem #2(b) was ambiguous, and has been fixed. (Thanks Kevin!)

Update #2: the indices in the algorithm in problem #2 were off by 1 and have been fixed. (Thanks Favonia!)

Homework #3 Open Thread

Homework #3‘s now online.

Please post questions and clarifications in the comments…

Homework #2 open thread

Ask yr HW2 questions here…

Homework #1 Open Thread

Jeremiah just pointed out that Problem 2(a) analyzing the 3SAT algorithm was missing a couple terms from the summation. The online version has been fixed.