CS 336: Homework

Homeworks for Fall 2008

Homework Assignment 1 (due Tues Sep 9)

Textbook problem Ch1 #2: Describe how the pair-wise summation computation can be changed to find the maximum element of an array. Describe what computionation must be done at each node in the tree and work through on example (for an array of 8 entries).

Textbook problem Ch1 #3: Reformulate the pair-wise summation program to solve the Count3s computation in log n time, assuming the number of processors P is n/2 (like in class today). The Count3s problem is simply to count the number of threes in an integer array. Like the summation problem, the result is a scalar.

Homework Assignment 2 (due Thurs Sept. 18)


Homework Assignment 3 (due Thurs Sept. 18)


Homework Assignment 4 (due Thurs Sept. 25)


Homework Assignment 5 (due Sat Oct. 4)


Example Write-Up


Throughout the MPI section of the course, we will be reading a journal article that compares different sorting algorithms on a supercomputer called the Connection Machine 2 (CM-2). For background on the CM-2, see its entry in Wikipedia. For an interesting article from Physics Today about physicist Richard Feynman's involvement check out this link. The Richard Feynman article and the sorting algorithm paper are both required reading, but only the Feynman article is to be read in one sitting.

Note: If the above link is broken, search for the sorting paper on Google. Its reference is :
G.E. Blelloch, C.E. Leiserson, B.M. Maggs, C.G. Plaxton, S.J. Smith, M. Zagha, A Comparison of Sorting Algorithms for the Connection Machine CM-2, Proc. 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991.

Reading Assignment 1 (due Thurs Oct. 23)

Read sections 1 and 2 in Blelloch et. al (1991) along with the Feynman arcticle. Come to class with a substantive question or comment.

Homework Assignment 6 (due Thurs Nov. 6)


Reading Assignment 2 (due Thurs Nov. 6)

Read section 3 in Blelloch et. al (1991). It describes their implementation of Batcher's bitonic sort -- an algorithm we will be going over in class on Thursday. Come to class with a substantive question or comment. This is a 5-pt homework assignment.

Homework Assignment 7 (due Thurs Nov. 20)


Homework Assignment 8 (due Thurs Dec. 4)