|
|
ICS 556 Parallel Algorithms Winter 2007 |
|||||
| Exams | ||||||
|
|
ICS 556 Parallel Algorithms Winter 2007 |
|||||
| Exams | ||||||
|
Instructor: |
|
|
Office: |
Bldg 22 (124-8), ICS - KFUPM |
|
Phone: |
860-3819 |
|
E-mail: |
malalla@ccse.kfupm.edu.sa |
|
Office Hours: |
SMW 12:30 – 2, and whenever you catch me. |
Description
After introducing some basic parallel computing concepts, parallel computational models (PRAM, Meshes, Trees, Hypercubes, Shuffle-Exchange, Mesh-of-Trees) and the complexity measures, the course covers various parallel algorithms design techniques such as: divide-and-conquer, parallel prefix, pointer jumping, list ranking, and Euler’s path technique. The parallel algorithms studied in the course span different applications ranging from classical problems such as selection, merging, sorting, searching, graph problems, and computational geometry to some advance and current problems in scientific computations, signal processing, and simulations. The students will study also parallel computational complexity classes: equivalence of Boolean circuits and the PRAM models, the NC class, and P-complete problems. Here is the course syllabus.
Prerequisites
ICS 553 Advanced Computer Algorithms (or any equivalent course)
is the only official prerequisite for this course. However, a good background in probability, discrete mathematics, data structures, and design and analysis of algorithms will be very helpful.Course Objectives
To know the fundamental concepts and techniques of parallel computing.
To learn how to design and analyze parallel algorithms to solve given problems in specific parallel computation models.
Course Learning Outcomes
Upon completion of this course, the student should be able to:
define and compare between the structures of classical parallel computation models.
use the metrics of cost, speed-up and efficiency to analyze the performance of given parallel algorithms and compare between them and their sequential counterparts.
|
Assignments |
20% |
|
Major Exam I Mon Apr 2nd |
25% |
|
Major Exam II Mon May 21st |
30% |
|
Presentation |
25% |
Textbooks
|
We will follow mainly this the textbook by Selim G. Akl, Parallel Computation: Models and Methods, Prentice Hall, 2nd Ed., 1997.
However, we will cover some extra topics from other references and select some papers from current literature. Supplementary lecture notes and handouts will be given as the course progress.
|
 |
Other References
 |
J. Jaja, Introduction to Parallel Algorithms, Addison Wesley, 1992. |
|
|
C. Xavier and S. S. Iyengar, Introduction to Parallel Algorithms, John Wiley & Sons, Inc, 1998. |
|
|
B. Wilkinson & M. Allen, Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers, 2nd Ed., Pearson Education Inc, 2004. |
|
|
F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays . Trees . Hypercubes, Morgan Kaufmann Publishers, 1992. |
|
|
A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing: Design and Analysis of Algorithms, 2nd Ed., Addison-Wesley, 2003. |
|
|
K. Berman and J. Paul, Algorithms: Sequential, Parallel and Distributed, Thomson-Course Technology, 2005. |
|
|
R. Miller and L. Boxer, Algorithms Sequential and Parallel-A Unified Approach, Prentice Hall Inc, 2000. |
|
| Sequential Algorithms Textbooks |
 |
The Design and Analysis of Computer Algorithms, by Aho, Hopcroft and Ullma. |
|
|
The Design and Analysis of Algorithms, by D. Kozen. |
|
|
The Art of Computer Programming, by D. Knuth. |
|
|
Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein. |
|
|
An Introduction to the Analysis of Algorithms, by Sedgewick and Flajolet. |
|
|
Algorithms, by S. Dasgupta, Papadimitriou, and Vazirani. |
