15-859HH: Parallel and Concurrent Algorithms
Carnegie Mellon University, Computer Science Department
Spring 2021


Instructor: Guy Blelloch
Time: Tuesday and Thursday 4:00 - 5:20
Place: Zoom (contact instructor for link)
Office Hours: Wednesday 2pm (same zoom link)
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).

Announcements:

Feb 1: The first reading are sections 1-3 of the this introduction to parallel algorithms. We will be covering this material this week. I sent out a zoom link to the course to everyone who is registered. If you would like it please contact me via email.

Schedule:

A rough schedule can be found here.

Course Description:

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.

Method of Evaluation:

The course grade will be based on three assignments, the course presentation, a final project report, and a take-home final. The assignments will mostly be theoretical, but for some there will be an option of doing an implementation instead of some of the theoretical questions. Students will be expected to present at least one algorithm from a research paper during the semester. The final project will be over 5 weeks and can be either a pure theory project, a systems project, or a combination of both.

Course Outcomes:

The course outcome will ideally be the ability to design your own efficient parallel and concurrent algorithms for topics you are working on or are interested in.

Specific Topics:

Expected course topics Include: Parallel models, work-stealing scheduling, list-ranking, merging, sorting, Euler trees, dynamic algorithms, suffix arrays, cartesian trees, balanced trees, low-diameter graph decomposition, connectivity and biconnectivity, maximal-independent sets, strongly-connected components, graph spanners, set cover, convex-hulls, closest pairs, and Delaunay triangulation. All of these, of course, are in the context of parallelism and concurrency.


Guy Blelloch, guyb@cs.cmu.edu.