1.Consider a 3D stack of cylinders; each cylinder is given as three [x, y, z] coordinates. Assume that all cylinders are the same size. A configuration is valid iff:

There is at least one cylinder on the floor (i.e., the z axis is zero for one of its faces)

Every other cylinder is lying, at least partially, on top of another cylinder, such that there is a path to the floor (i.e., the cylinders are stacked, not floating in mid-air).

Let isValid(A) be a function that takes in an n 3 3 array and outputs whether or not it consists of a valid configuration.

(a) Write pseudocode for a sequential version of isValid

(b) Write pseudocode for a parallel version of this algorithm. Assume that you have as many processors available as needed.

(c) Analyze (i.e., prove) the running time of both algorithms and the work of the parallel one

(d) Assume that the cylinders can have different sizes. Write pseudocode for a parallel algorithm that can solve this version of the problem.

Note that the most efficient algorithms (relative to others in the class) will receive full marks; less efficient ones will be marked down.

2. Suppose that two n n matrices A and B are stored on a mesh of n 2 processors such that Pi,j holds A[i, j] and B[j, i]. Write pseudocode for an asynchronous algorithm that computes the product of A and B in O(n).

3. We discussed the WT scheduling principle in the context of PRAM algorithms. Prove that this principle will always work for the dag model.