Parallel and Distributed Algorithms

CS 6/76105

Spring 2010

Reading Assignments:

Problem Assignments:

Set Number	Date Assigned	Problems	Presentation Date
1	2/19	Problems 1.3, 1.5, 2.2 in Casanova & 2.6, 2.7, 2.8, 3.3 in Akl; Hints-doc Hints-pdf	~2/26
2	3/20	Problems Assigned --1-new, 4.9-Akl, 7.1-Akl, 7.10-Akl, 7.12-Akl, 3.2-CLR

Presentation Slides:

Date Started	Title	Main References	Last Update
1/18/10	Course Syllabus & Overview	Slides
1/20/10	Introduction and General Concepts	Related material in Ch 1-2 of Akl Text	5/07
1/30/10	The PRAM Model	Ch 2, 4-6 of Akl Text, Ch 1 of Casanova Text, Akl's first-listed book chapter	2/05
1/8/10	Combinational Circuits & Sorting Networks	Ch 2, 3 of Akl Text, Ch2 of Casanova text, Akl's first-listed book chapter	5/07
1/19/10	Message-passing Interconnection Network and Communications	Chapter 3 of Casanova, et.al. (CLR)	3/17
3/07/10	Midterm Preparation Comments	Covers through Ch 3.4.2 in CLR
3/17/10	Linear Arrays - Akl	Chapter 7 in Akl Textbook	3/17
4/05/10	Message-Passing Ring Algorithms	Chapter 4 in CLR Textbook	4/05
4/19-4/23	Student Presentations Exercise 2	1, 2(4.9-Akl), 3(7.1-Akl), 4(7.10.a-Akl), 5(7-10.b-Akl), 6-first-sec(7.12Akl), 7-first-sec-third(3.2.a-CLR), 8(3.2.2-CLR), 9- first-sec-third(3.2.3-CLR)
4/26/10	Mesh Model Algorithms	Chapter 8 in Akl Textbook; Comments & earlier copy with better page breaks
4/30/10	Message-Passing Grid Algorithms	Chapter 5 in CLR Textbook	5/07
5/3/10	SIMD and Associative Models	Partially covered in class and a reference
5/5/10	Comparison of SIMD and MIMD using Air Traffic Control
5/7/10	Study Guide for Final Exam

Textbook References:

1. Selim Akl, Parallel Computation: Models and Methods, Prentice Hall, 1997.
   • An updated ONLINE VERSION of this textbook will be provided for this class, but requires a password to access.
2. Parallel Algorithms, Henri Casanova, Arnaud Legrand, and Yves Roberts, CRC Press, 2009.
   • This textbook was ordered by bookstore for class.

Other Primary References:

1. Michael Quinn, Parallel Programming in C with MPI and OpenMP, McGraw Hill, 2004.
   • Copies of needed reference material will be made available or posted on website
2. Selim Akl, The Design of Efficient Parallel Algorithms, Chapter 2 in “Handbook on Parallel and Distributed Processing” edited by J. Blazewicz, K. Ecker, B. Plateau, and D. Trystram, Springer Verlag, 2000, pg 18-91,
   • SELECTED READINGS from Chapter 2 (password required).
   • This lengthy book chapter contains a lot of the material that will be covered from Akl's textbook.

My Reference List for Course: (May expand during course. )