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.
