San Diego State University

The following are review questions for CS 662 offered in 1994. Not all topics covered then have been covered this year.

Know the ways of classifying Parallel machines: coarse-grain, shared-memory, message passing, SIMD, MIMD.

Measures of parallel algorithms: Speedup, cost, efficiency. Be able to compute the measures for an algorithm. Example: An algorithm uses N*lg(N) processors to sort N items in lg(N) time. Compute the speedup, cost, efficiency of the algorithm.

What is the cost of broadcasting a datum from one processor to all processors on an N processor CRCW (ERCW, CREW, EREW) machine?

Given an algorithm that runs in O(f(N)) steps on an CRCW machine. If we port the algorithm to a EREW machine with the same number of processors as the CRCW machine, what is an upper bound on the number step required by the ported algorithm?

Show how to implement quicksort with the scan operator.

Implement the +-scan operator.

Let

How would you compute in parallel? How many processors would you use? How long would it take?

Describe an O(1) sort on a CRCW machine

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

How many comparator circuits are required in the Batchers-even odd sort to sort a list of 2

What are the time complexity and cost of the above sorts.

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

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

You are playing a game of chance. You have a six sided die (the sides are numbered 1, 2, 3, ..., 6). You win the game if you throw the die and either a 5 or a 6 is on the top side. Give a bound on the probability of winning 10 or fewer times in 120 games. If you pay $1.00 to play the game and get $3.00 if you win the game. Give a bound on the probability of earning $50 or more profit in 100 games.

What is the diameter of a N-dimensional Hypercube? a N by K mesh? a complete binary tree with 2

Is it possible to embed a complete binary tree with 2

Is it possible to embed a complete binary tree with 2

Describe an algorithm and give the time complexity and number of processors used to:

a) evaluate a polynomial

b) multiple matrices

c) compute A

What is the characteristic polynomial of a matrix? How do you compute the characteristic polynomial of a matrix? How do you use the characteristic polynomial of a matrix to solve for x when Ax = b, where A is an N by N matrix and b is a vector.

How do you compute the ranks of items in a linked list?

Give an algorithm to compute suffix sums of a linked list.

Write a parallel algorithm to traverse a graph and list the nodes visited in postorder. What is the time complexity of the algorithm and how many processors do you use?