**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.

Semester: Fall

Credits: 9 CFU

Requirements

**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.**

Learning outcomes

Learning outcomes

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.

**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.**

Examination

Examination

**Course web site**

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

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

Syllabus

Sequential Algorithms

Syllabus

Sequential Algorithms

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)

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

Parallel Algorithms

Parallel Algorithms

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)

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

Drills (21 hours)

Textbooks

Drills (21 hours)

Textbooks

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