## CS 662: Theory of Parallel Algorithms Final Exam 1994

San Diego State University -- This page last updated March 21, 1995

The following final exam was given in CS 662 offered in 1994. Not all topics covered then have been covered this year.

1. Produce the dag with minimal depth that will evaluate 3x**8 + 5x**4 + 7x**2 + 2.

2. Explain how to evaluate the polynomial y = b[1]x**(n-1) + b[2]x**(n-2) + ... + b[n-1]x + bn for a given x using the scan operator.

3a. Describe the odd-even transposition sort on a linear array of processors.

b. What is the time complexity and speedup of the sort if N = P. When N < P?

4. We have N processors. Each processor flips a fair coin. Use the Chernoff bounds to produce an upper bound on the probability that N/4 or fewer of the processor's coin landed heads up?

5. Reduce the following to a first-order recurrence relation.

6. Explain how to compute in parallel A**-1 when A is a lower triangular matrix. How many processors are required? How long will it take?

7. Show how to solve for x when Ax = b using the characteristic polynomial of a matrix.

8. Give an algorithm to compute the rank of items in a linked list. Show how to avoid any concurrent reads or writes.

9. Explain why it is not possible to embed a complete binary tree with 2**k-1 nodes in a Hypercube with 2**k nodes.