Parallel Programming Minor Test – I

1. Give a CREW PRAM algorithm to merge two sorted lists.

2. Define shuffle and exchange connections in a shuffle-exchange network. Prove that if a shuffle link connects nodes i and j, then j is single-bit left cyclic rotation of i.

3. What is the average number of communication links in the use during Johnsson and Ho’s one-to-all broadcast algorithm on the hypercube?