Jan 16: 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.
Jan 24: Assignment 1 is now available and due on Thursday February 1.
February 15: Assignment 2 is now available and due on Thursday February 29.
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.
The course grade will be based on three assignments, the course presentation, a final project report, and a take-home final. 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.
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.