Parallel and Concurrent Algorithms

Course ID 15852

Doctoral Breadth Course: Algorithms and Complexity - (*)
Classes marked with "*" (star) are appropriate for any CSD doctoral or 5th year master's student.

This is an advanced course on the theory, and some practice, of parallel and concurrent algorithms. We will start by discussing models and then go through a variety of topics including algorithms for sorting, strings, graphs, and geometry. The focus will be on so-called work-efficient algorithms (i.e. algorithms that do more work than their sequential counterpart). The goal is both to get a broad view of the techniques used to design of such algorithms, as well as going into some depth on a handful of recent breakthroughs in the design of parallel algorithms. We will discuss practical implementations of most of the algorithms we cover.

Key Topics
Parallel models, parallel algorithms, concurrent algorithms..

Required Background Knowledge
Strong math skills. Upper-level undergraduate course in algorithms.

Course Relevance
Masters, PhD or upper level undergrad

Course Goals
The students should gain a strong background in parallel and concurrent algorithms, to the point that they could start research in the area.

Learning Resources
See course webpage

Assessment Structure
30 % Homework, 10 % presentation, 20% final project, 40% two exams

Extra Time Commitment
n/a

Course Link
https://www.cs.cmu.edu/~guyb/paralg/