1. Write a parallel algorithm to compute all x1
, …, x1000 for some given x, assuming that you have k
processors. Please analyze the complexity of your algorithm in terms of the runtime and the total work time. Is it
2. Given a list of n numbers, please develop a parallel algorithm to find the maximum of the list. Please analyze the
complexity of your algorithm in terms of the runtime and the total work time. Is it optimal?
3. Given a linked list of n items, please develop a parallel algorithm to compute the rank of each item the list.
The rank is defined to be the distance to the end of the list. Please analyze the complexity of your algorithm
in terms of the runtime and the total work time. Is it optimal?
4. Please implement Problem #2 in HW2 (histogram computation) using MPI with the assumption that the N
elements in the input are (roughly) evenly distributed over k processors. Please make your implementation
as efficient as possible.
5. Consider the basic matrix multiplication algorithm for two NxN matrices using KxK processors connected
using a 2D mesh network. Please derive the isoefficiency relation and the scalability function. Assuming all
data is stored in the processor 0 in the beginning so that you have to distribute them to each processor first.
You may assume communication time needed to broadcast L data in 2D mesh network is O(L).
6. (Bonus problem, 20 points) Assuming that we have p processors, please write a parallel algorithm that runs
faster than O(logn) to search integer y in a sorted list of integers x1, x2, …, xn, and output index i such that xi
<= y < xi+1. Please make your algorithm as fast as possible. You may assume all processors can read from
a memory space in constant time (CREW model). Is your algorithm optimal?
** For problems 1, 2, 3, and 6, you are encouraged to write a pseudo-code of your parallel algorithm followed
by a concise explanation of how your algorithm works. Also, please answer any additional questions in the
problem. Please write a C code with MPI APIs for problem 4.
Late submission policy:
We allow 16 hours delay until 8am Tues. Feb. 12 with 10 points penalty. After that, no submission will be
accepted beyond that time. We’ll post the solution for preparation of midterm at that time.