Date : 29.08.2008
Duration : 40 Minutes
Max. Marks : 10

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?