Homework 2
Assigned 9 March 06
Due 17 March 2006
25 points

Problems 11-5 and 11-15, page 367

Problems 4-1 and 4-2, page 133


Problem M1:

Give three examples of problems that are parallelizable but not
"embarrassingly parallel", and for each, explain why they are not.


Problem M2:

Suppose you have a message-passing system with p processors
and an additional processor with a bitmap display organized
as a 2^k by 2^k array.  Suppose that the time to set a pixel
on the display processor is just the time to write a word to
memory. The display processor sends and receives messages in
the same way as the others.

Consider the problem of calculating the Mandelbrot set in
four stages, with the resolution doubled at each stage and
ending at the maximum display resolution.  The idea is that
the image is displayed relatively quickly at low resolution
and then improves as you watch it.

  (a) sketch out pseudo-code to do this
  (b) analyze the time complexity of your code
  (c) compare the time complexity of this with the one-stage
      Mandelbrot calculation at the maximum resolution