2004 F

Answer any six of the following eight questions. Each question is 17 points. (Note that the 7th & 8th answers, if any, in your answering order will NOT count.)

1. Find a Minimum Spanning Tree of the following graph using either Kruskal's or Prim's algorithm and detail your steps.

2. Give an algorithm that determines whether or not a given undirected graph G(V,E) contains a cycle. Your algorithm should run in O(V) time, independent of |E|. Assume that the input graph is represented using adjacency lists.

3. Prove or disprove the following statement: Dijkstra's algorithm for the single-source shortest path problem will still work correctly if there is only one edge of negative weight in the input graph and the rest of the edges all have positive weights.

4. Let S be a set of n integers where n is even. Suppose that the n numbers have to be paired up into n/2 pairs such that the maximum sum of a pair is minimized. Argue that there is a solution for which the biggest element in S is paired up with the smallest element in S.

5. Given a set S of n numbers and another number x. Describe a Θ(nlgn)-algorithm to determine whether or not there exist two elements in S whoose sum is x.

6. Let X[1...n] and Y[1...n] be two arrays, each containing n numers already in sorted order. Give an O(lgn)-time algorithm to find the median of all 2n leements in arrays X and Y.

7. Let X and Y be two arrays of n numbers, where $x_i$ and $y_i$ denote ther ith and jth numbers, respectively.One number in an array is allowed to pair with one or more numbers in the other array, subject to the constraints given below. For convenience, we use W=[$w_1, w_2, ..., w_m$] to signify a possible sequence of pairing's, where its kth number $w_k=(x_i,y_j)$ has pairing cost $|w_k|=(x_i,y_j)^2$, 1≤k≤m, n≤m≤2n-1. Any possible sequence must satisfy the constraints:

• $w_1=(x_1,y_1)$, $w_m=(x_n,y_n)$
• $w_k=(x_i,y_j)$⇒$w_{k-1}=(x_{i-1},y_{j-1}),(x_{i},y_{j-1}), or (x_{i-1},y_{j})$
• $w_k=(x_i,y_j)$⇒|i-j|≤R<n.

Given some constant R write an algorithm to compute the minimum overall cost, namely $min_{W} \sqrt{ \sum_{k=1}^m |w_k|}$, using Dynamic Programming approach.

8. Suppose we have a special hardware for multiplying two N*N matrices for some fixed constant N. Write an algorithm (based on Strassen's recursive algorithm, if possible) to take advantage of such hardware for multiplyng any two m*m matrices.