Algorithms Core 15-750  PROBLEM SET # 6  Spring 1999

DUE: 1:00PM Wednesday April 28 1999

1 Analysis of MIS Algorithm version 2

This problem is worth two problems.

Recall, version 2 of the Luby’s Maximal Independent set Algorithm: Let G = (V, E) be simple undirected graph Procedure: MIS(G = (V, E))

0) If |V | = 0 return.

1) For each vertex v pick a random number p_{v} in the range [0, 1]. You may assume the values p_{v} are distinct.

2) Place v in I if p_{v} < p_{u} for all u ∈ N(v).

3) V′ = V − N(I) − I and E′ = {(u, v) ∈ E | u, v ∈ V′}

4) return I ∗ MIS(G′ = (V′, E′))

The goal of this problem is to show that with high probability MIS will be called at most O(log n) times. In parts 2. and 3. below you need not use the constants that I have used.

For each call prove the following:

1. P rob(v ∈ I) = \frac{1}{d(v)+1}

2. Pick a definition of a “good” vertex and a “good” edge. I picked v is good if

∑_{u∈N(v)} \frac{1}{d(u) + 1} ≥ 1/3

3. If v is good then P rob(v ∈ N(I)) ≥ 1/9 Hint: Show that if u and w are two distinct vertices which do not share an edge then

Prob[u ∈ I & w ∈ I] = \frac{d(u) + d(w) + 2}{(d(u) + 1)(d(w) + 1)(d(u) + d(w) + 2 − k)}

where k is the number of vertices common to u andw.

3. The expect number of edges deleted is at least |E|/18

For each of the parts you may use results from Kozen.

2 Computing the minimum number of registers

Let T an arbitrary computation tree over the domain of integer Z with the operation at the internal nodes being {⊕} defined as following:

⊕(a, b) = \{ \begin{matrix}a + 1 & a = b \\ max(a, b) & otherwise \end{matrix}

Show that any tree over this operation can be evaluated in O(log n) time using n/ log n processors.

Hint: Consider the following class of function:

F = {f_{a,b} | a ∈ Z ∪ {−∞}, b ∈ Z, a ≤ b}

where

f_{a,b}(x) = \{ \begin{matrix}a & x < a \\ max(b, x) & otherwise \end{matrix}

3 Parallel Selection

Consider the O(n) deterministic sequential algorithm for section, see page 190 of CLR.

Problem 3.1 Write this algorithm as a parallel algorithm using the parallel constructs from class without changing the work performed. Analysis the asymptotic time for your parallel algorithm?

Consider the Randomized-selection algorithm, see page 187 of CLR.

Problem 3.2 Write this algorithm as a parallel algorithm using the parallel constructs from class without changing the work performed. Analysis the asymptotic expected time for your parallel algorithm? Instead of computing the expect time you may use Chernoff Bounds to bound the running time with high probability.