# Paralelní algoritmy (B4M35PAG), Parallel Algorithms (BE4M35PAG)

## Summary

In the introductory lectures, we will focus on general approaches to design of parallel algorithms and their properties important for understanding the fundamental principles of parallel and distributed algorithms. Subsequently, we will talk about fundamental parallel algorithms; typically constituting cornerstones of algorithms for real-world problems. The laboratory exercises will be aimed at hardware platform commonly used in practice (multi-core CPUs).

## Prerequisities

C/C++, basic Linux skills, algorithms

## Lectures

No. Title Notes Handouts
1 Introduction to Parallel Computing Chapter 2
2 Principles of Parallel Algorithms Design Chapter 3
3 Basic Communication Operations Chapter 4
4 Analytical Modeling of Parallel Algorithms Chapter 5
5 Matrix Algorithms Chapter 8
6 Algorithms for Linear Algebra Chapter 8
7 Sorting Chapter 9
8 Parallel Accelerators TEST Parallel Accelerators
9 Combinatorial Algorithms Chapter 11
10 Graph Algorithms I. Chapter 10
11 Graph Algorithms II. Chapter 10
12 Dynamic Programming Chapter 12
13 Fast Fourier Transform Chapter 13

To get an ungraded assessment the following requirements have to be met:

• obtain at least 25 points during the semester:
• 35 points for homework assignments No. 1 to 4 (8+8+11+8 points per assignment)
• Up 5 bonus points for extra task
• 10 points for the Test
• The test starts at the beginning of the lecture and takes approximately 30 minutes. It focuses on knowledge from the lectures and labs already taught.

To pass the exam it is necessary to get at least 20 points (maximum 45 points) from the written exam. The oral exam is mandatory and gives 10 points at maximum.

Extension of the homework deadlines is not possible! The only exception is a serious health or family issue proven, for example, by a medical certificate. We also do not award assessments (zápočety) after the examination period starts.

points [0,50) [50,60) [60,70) [70,80) [80,90) [90,100]
grade F E D C B A

For the written and oral exams, you will need a pen and pencil. The exam tests both the knowledge from lectures and seminars.

## Literature

[1] Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing, Second Edition, Addison Wesley, 2003.

[2] Georg Hager, Gerhard Wellein: Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2011.

[3] James Reinders, Jim Jeffers: Intel Xeon Phi Coprocessor High-Performance Programming, Newnes, 2013.