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 no more work than their sequential counterpart). The goal is both to get a broad view of the techniques used to design 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.
The course grade will be based on a handful of assignments, a final project report, and a final. The final project will be over 5 weeks and can be either a pure theory project, a systems project, or a combination of both.
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.
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.
We will be using parlaylib for some of the assignments. It is based on C++. You can find many examples of parallel algorithms in parlaylib in the examples directory. See the .h files since the .cpp files are just drivers.