##
CS 662: Theory of Parallel Algorithms

Final Exam 1994

[To Course Home Page]

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.