Parallel Algorithms

Consider a 3D stack of blocks; each block is a cube given as eight [x; y; z] coordinates.

Assume that all cubes are the same size. A configuration is valid if and only if:

There is at least one block on the "floor" (i.e., the z-axis is zero for one of its surfaces)

Every other block is lying exactly on top of another block, such that there is a path to a floor block(i.e., the blocks are stacked, not floating in mid-air).

LetisValid(A) be a function that takes an n x 8 x 3 (n by 8 by 3) array and outputs whether or not it consists of a valid configuration.

a) Write pseudocode for a sequential version of isValid

b) Write a 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 cubes can have different sizes. Write a pseudocode for a parallel algorithm that can solve this version of the problem. Here, a cube is considered supported iff it lies completely on top of another one (i.e., a big cube cannot lie on top of a smaller one).

Would you please provide a clear solution to the problem, please please DO NOT answer the question if you don't know the right answer. Parallel Algorithms