CPSC 626: Parallel Algorithm Design and Analysis
Homework Assignment #1
Fall 2008

Due: Thursday Sept 4, 2008 at the beginning of class.

General Guidelines for Homework

• Be clear and precise. Write neatly and legibly. Justify all answers, even if not specified in the question. Use good judgement concerning how detailed to make your answer.
• If the question is not fully specified, you may need to make some assumptions. In this case, you must state any assumptions you make, and justify why they are reasonable.
• Everyone must turn in their own copy of the assignment. You may consult outside material or work with others (this is encouraged), but you must reference your sources (people, texts, solutions, etc.). These must be listed on the cover sheet mentioned below.
• All assignments in this course must include a completed and signed cover sheet available on the course homepage. Any assignment turned in without a fully completed and signed coverpage will receive ZERO POINTS.

1. Computing the OR of n bits on a CRCW PRAM.
   (a) Describe the best algorithm you can, in terms of both time and work, for computing the OR of n bits on a CRCW PRAM.
   (b) Analyze your algorithm, showing its time, work and processor bounds.
   (c) Discuss the optimality of your algorithm.
2. Computing the Minimum of n integers on a CREW PRAM.
   (a) Describe the best algorithm you can, in terms of both time and work, for computing the Minimum of n integers on a CREW PRAM.
   (b) Analyze your algorithm, showing its time, work and processor bounds.
   (c) Discuss the optimality of your algorithm.

3. Computing the Minimum of n integers on a CRCW PRAM.
   Repeat problem 2, but this time for a CRCW PRAM.