Assignment #5 due Tues., April 23

1. Given a binary associative operator and item stored in processor on a hypercube of size n, give an efficient algorithm to solve the parallel prefix problem. When the algorithm terminates, processor must know the prefix, .
2. Show that the addition of n numbers has complexity on a PRAM with processors.
3. Give an efficient PRAM algorithm to multiply 2 matrices.