32 views

Skip to first unread message

Feb 3, 2010, 1:57:17 PM2/3/10

to CS 510 Randomized Algorithms

Hi class,

Here is your first homework assignment. Please write up your answers

neatly, or,

better still, type them up using something like Latex or Lyx. You can

turn in your

answers in class on the due date, Wed, Feb 24 (3 weeks from today), or

you can

email me your PDF file (by midnight of the same day), and save part of

a tree.

Here are the first two problems. I will send the rest in a follow-up

email later today.

1. Impoving Karger's algorithm.

(a) Decide how best to implement Karger's min-cut algorithm

using some sort mutable data structure to store the contracted

graphs as you go. What is the worst-case cost for doing the i'th

edge contraction, up to a constant factor (use big-O notation)?

Your answer should be a function of n and i only.

(b) Sum this over i, and multiply by n^2 to get an estimate for the

expected running time of Karger's min-cut algorithm as given.

(c) See Exercise 1.25(b) in the textbook for inspiration.

For each 1 <= i <= n, compute the probability that a particular

min-cut survives the first i steps of Karger's algorithm (i.e.,

has none of its edges contracted). Note that this function

decreases with i. This suggests that the first steps of Karger's

algorithm are more reliable than the last steps, and so perhaps

do not need to be redone as often. Use this idea to improve

Karger's algorithm as much as you can. Analyze:

(i) the failure probability.

(ii) the expected number of times an i'th edge will be chosen for

contraction in your algorithm.

(iii) the expected overall running time of your algorithm.

2. (a) Prove that, if A_1, A_2, ..., A_n are n independent events,

each of probability 1/2, defined over a probability space Omega,

then Omega has cardinality at least 2^n.

(b) See exercise 1.21 for warm-up.

We say events B_1, B_2, ..., B_n are PAIRWISE INDEPENDENT

if any two of them, say, B_i and B_j are independent, where

i, j are unequal. Construct, for any n, a probability space

Omega of size O(n^2) and pairwise independent events B_1, ..., B_n

defined on Omega, each having probability 1/2.

Feb 5, 2010, 1:08:43 AM2/5/10

to CS 510 Randomized Algorithms

Hi again,

Here is the rest of Assignment 1. 8 problems in all.

The numbered Exercises are from Mitzenmacher & Upfal.

I'll revise the due date to Friday, Feb. 26, so that you have

a full 3 weeks.

-- Tom

3. Let Omega be uniform probability space whose elementary

events are the graphs on n vertices. Define the random variable

f: Omega --> Reals as the number of triangles in the graph.

(a) Recall the expectation of f (computed in class).

(b) Calculate the variance of f. Hint: indicator variables.

Hint 2: some pairs of indicator variables will be independent,

and some will not.

(c) Apply Chebyshev's inequality to bound the probability

that a random graph has more than (3/16)(n choose 3) or

fewer than (1/16)(n choose 3) triangles. For what values of

n is this bound on the probability < 1/1000?

4. Exercise 1.6

5. Exercise 1.10

6. Exercise 1.22(b)

7. Exercise 2.18

8. Exercise 2.20

Also recommended for practice (but not to turn in):

Exercises 1.15 (try not to read the hint!) 1.18, 2.1, 2.3, 2.4, 2.8,

2.9, 2.10, 2.16, 2.17, 2.18, 2.19, 2.20, 2.26, 2.27, 2.31

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu