## CS 662 Theory of Parallel Algorithms Assigment 2 and 3

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

Assignment 2

Redo problem 9.9 in The SR Programming Language.. Each worker needs to be in a separate VM. This means a worker needs to be in a in it's own resource. Time how long it takes the program to sort lists using 1, 2, 4 and 8 workers on rohan.
```
```
Assignment 3
1) Consider an EREW PRAM with P processors and M memory locations. We can emulate the EREW PRAM on a P-processor message-passing machine in which each processor has M/P memory locations. Let t be the run of an algorithm on the P-processor EREW PRAM. Give an upper bound on the run time of this algorithm on:
a) a P-processor ring
b) a P-processor mesh
c) a P-processor hypercube

2) Let A and B be two processors in a D-dimensional hypercube. Parallel paths between A and B are distinct paths connecting A and B with no common processors other than A and B. Show that the total number of parallel paths between any two processors is D.

3) One hundred dice are dropped on the floor. Give an upper bound on the probability that 30 or less of the dice show a 1 or a 2.

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

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

```
```