## CS 662 Theory of Parallel Algorithms Past Exams

[To Lecture Notes Index]
San Diego State University -- This page last updated February 20, 1996, 1996 ## 1993-94

### Final

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 = b1x**(n-1) + b2x**(n-2) + ... + bn-1x + 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 nodes in a Hypercube with nodes.

## 1994-95

### Midterm

Answer any 8 of the following questions. Clearly indicate which 8 problems you wish to be graded.

1) State Amdahl's Law. Explain the law's consequences for massively parallel algorithms.

2) Given an algorithm of size N, optimal sequential time complexity A(N) and P processors, can we obtain a speedup greater than P? Explain your answer.

3) Give an algorithm to lexically compare strings of N characters in parallel. Give the time complexity of the algorithm.

4) Reduce the following to a first-order recurrence relation. 5) What are the important parameters (or characteristics) of a connection network. Give the values of the parameters for the hypercube and the shuffle-exchange networks.

6) What is the slow-down principle? Give an example. That is explain the effects of the slow-down principle on an algorithm covered in the course.

7) Explain the operation of guarded commands in SR.

8) Explain how to simulate the PRAM in SR.

9) Explain how to simulate a MIMD machine in SR.

10) Explain the operation of a semaphore. Why are semaphores not used in parallel programs?

11) Give an algorithm to broadcast an item on a hypercube.

12) Contrast the send and call operations in SR.

### Final

Answer any 8 of the following questions. Clearly indicate which 8 problems you wish to be graded.

1. Explain why it is not possible to embed a complete binary tree with nodes, (for k >= 6), in a mesh of any size.

2. Give a parallel algorithm to find a root of an equation of one variable. What is the time complexity and the cost of the algorithm.

3. Give a situation where N processors connected together as a binary tree will perform better than N processors connected as a mesh. Explain your answer.

4. Explain how to use the characteristic polynomial to compute A-1 where A is an N*N matrix.

5. We are on a CREW machine. We have P processors, a list, A, ... A[N], of N integers in random order, and b buckets, B, ..., B[b], into which we are to place the elements of the list. We have a sorted list of b-1 numbers S, S, ..., S[b-1]. Bucket B[j] (j = 2, ..., b-1) gets all elements of the list that are greater than S[j-1] and less than or equal to S[j]. Bucket B gets all elements of the list less than or equal to S. Bucket B[b] gets all numbers greater than S[b]. Give an efficient parallel algorithm to place the elements of A in the buckets.

6. a. What are the different types of computational models of parallel computing that use shared memory?

b. Algorithm X runs on an CRCW machine with time complexity of T(N). Algorithm X is ported to a EREW machine. What can we say about the time complexity of X on the EREW machine? Explain.

7. Contrast the "co" and "af" statements in SR

8. Explain how semaphores can be implemented with message queues in SR.

9. Describe a parallel algorithm to find the k'th smallest item in a random list of integers without sorting the entire list.

10. What is the difference between a Las Vegas and a Monty Carlo algorithm?

11. Describe a parallel quicksort. What is the time complexity and cost of the algorithm?

12. Describe an O(1) sort on an CRCW machine.

13. Describe the relationship between shuffing a deck of cards to data movements in a shuffle-exchange network.  