Course: Parallel Algorithms, MSc in Computer Engineering
Semester: Spring
Credits: 9 ECTS

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.

Assessment

The exam consists of a written test and a prototype implementation of a parallel software. The written test (2 hours, 21 points out of 30) covers theoretical topics related to the design and analysis of sequential and parallel algorithms in order to verify the student’s knowledge and understanding of the materials. In order to pass the written test, students must obtain at least 9 points out of 21. The parallel software project (9 points out of 30) is meant to verify the practice of parallel programming and the ability of the student to implement theoretical parallel algorithms or to parallelize a sequential algorithm. In order to pass the parallel programming challenge, students must obtain at least 4 points out of 9. Both the written test and the prototype implementation of parallel software are mandatory. Students must pass both the written test and the parallel programming challenge; however, the overall exam is passed only if the sum of points obtained in the written test and the parallel programming challenge is greater than or equal to 18 points.

The problem to be solved in parallel (or a sequential algorithm to be implemented in parallel) is assigned upon request to the student. The assigned parallel software project can be discussed only if a written test has been successfully passed; moreover, the parallel software project must be mandatorily discussed into the same trial in which the written test has been passed.

Course web site

https://elearning.unisalento.it/enrol/index.php?id=692


Syllabus


Parallel Algorithms

Introduction. Parallel Architectures. Parallel algorithm design. Message-Passing Programming. Sieve of Erathostenes. Floyd all-pairs shortest path algorithm. Performance analysis. Matrix-vector multiplication. Document classification. Matrix multiplication. Linear Systems. Finite Difference Methods. Sorting.

Parallel Programming

Message-Passing programming using MPI.

Sequential Algorithms

Introduction. Order of growth. Analysis of algorithms. Decrease and conquer. Divide and conquer. Recurrences. Randomized algorithms. Transform and conquer. Dynamic programming. Greedy algorithms. Single Source Shortest Paths. Dijkstra algorithm. Breadth-First Search. Bellman-Ford Algorithm. Complexity and computability. NP-Completeness. The transition from sequential to parallel computing. Parallel complexity.

Textbooks

Introduction to Algorithms. Fourth edition. Cormen, Leiserson, Rivest, Stein. The MIT Press
Parallel Programming in C with MPI and OpenMP International Edition (2004) Michael J. Quinn McGraw-Hill