Course: Parallel Algorithm, MSc in Computer Engineering
Semester: Fall
Credits: 9 CFU

Requirements

Calculus I and II, Probability Theory. Programming skills and working knowledge of the C programming language.



Learning outcomes

The course provides a modern introduction to design, analysis and implementation of sequential and parallel algorithms. In particular, the course is based on a pragmatic approach to parallel programming of message-passing algorithms through the C language and the MPI library.

After the course the student should be able to:

1) Describe and use the main design techniques for sequential algorithms;
2) Design, prove the correctness and analyze the computational complexity of sequential algorithms;
3) Understand the differences among several algorithms solving the same problem and recognize which one is better under different conditions;
4) Describe and use basic sequential algorithms;
5) Describe and use basic data structures; know about the existence of advanced data structures;
6) Understand the difference between sequential and parallel algorithms;
7) Design, implement and analyze message-passing based parallel algorithms in C using the MPI library;
8) Describe and use basic parallel algorithms.

Examination

Oral exam. Optionally, a student may be assigned a small project. During the exam the student is asked to illustrate theoretical topics in order to verify his/her knowledge and understanding of the selected topics. The student may also be asked to design a very simple algorithm in order to assess his/her ability to identify and use the relevant design techniques; alternatively, the student may be asked to analyze the complexity of a small code fragment.

Course web site

http://sara.unisalento.it/moodle/


Syllabus


Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer. Divide and conquer. Recurrences. (7 hours)

Randomized algorithms. (5 hours)

Transform and conquer. (2 hours)

Lower bound for sorting. Linear time sorting algorithms: Counting sort, Radix sort and Bucket sort. (3 hours)

Order statistics. Selection in expected and worst case linear time. (2 hours)

Dynamic programming. (4 hours)

Greedy algorithms. (3 hours)

Complexity and computability. NP-Completeness. (7 hours)


Parallel Algorithms

Introduction. The transition from sequential to parallel computing. Parallel complexity. (2 hours)

Parallel architectures. (5 hours)

Parallel algorithm design. Message-Passing programming. (12 hours)

Sieve of Erathostenes. (2 hours)

Floyd all-pairs shortest path algorithm. (2 hours)

Performance analysis. (7 hours)

Matrix-vector multiplication. (3 hours)

Document classification. (2 hours)

Matrix multiplication. (2 hours)


Drills (21 hours)


Textbooks

Introduction to Algorithms. Third edition. Cormen, Leiserson, Rivest, Stein. The MIT Press

Parallel Programming in C with MPI and OpenMP International Edition (2004) Michael J. Quinn McGraw-Hill