Algorithms Core 15-750  PROBLEM SET # 6  Spring 1998

DUE: 10:30AM Monday 27 April 1998

Answer each question on separate sheets of paper for grading purposes. Make sure that each page has your name and email address.

Make sure that each algorithm you consider includes the following three bullets.

DESCRIPTION: A high level description of the algorithm. CORRECTNESS: At least a high level outline of how the full proof would go. Possibly citing

lemmas from class. TIMING: A timing analysis.

The algorithms will be graded based on what you put in each bullet.

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))

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. If v is good then P rob(v ∈ N(I)) ≥ 1/5

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

Finally show that There exist a constant c independent of n such that the probability that after c log n calls MIS is not finish is at most 1/n

2 Toeplitz Matrices

An n × n matrix A is Toeplitz if A_{ij} = A_{i+1,j+1} for 0 ≤ i, j ≤ n − 2.

Is the sum (product) of Toeplitz matrices Toeplitz? Give a representation of Toeplitz matrices so that the sum is O(n) time. Give an O(n log n) time algorithm for multiplying an n × n Toeplitz matrix by a length n column vector. Give an efficient algorithm for multiplying two n × n Toeplitz matrices.