Schedule and Readings

Here is a rough schedule. Each item is meant to be about one lecture, but I expect some topics will go into a second lecture. I will fill this in over the next few days, and add readings as we approach the topic.

• Introduction and Models: PRAM, Vector Models, Circuits, MP-RAM
  Lecture Video and Lecture "Slides"
• Basic building blocks : e.g. scan, merging, searching

  Further readings (some original papers on topic)

  • Valiant, Merging (1975)
  • Shiloach and Vishkin, Early PRAM Merging and Sorting (1981)
  • Gil, Matias and Vishkin, Approximate Compaction (1991)
  • Goldberg and Zwick, Approximate Prefix Sums (deterministic) (1995)

• Sorting: mergesort, quicksort, sample sort, integer sort

  Further readings (some original papers on topic)

  • Cole, Mergesort (1988)
  • Rajasekaran and Reif, Integer Sorting (1989)
  • Blelloch, Gibbons, Simhadri, Cache Efficient Sample Sorting (2010)

• BFS and Low diameter decomposition

  Further readings (some original papers on topic)

  • Miller, Peng and Xu, Parallel Graph Decompositions Using Random Shifts (2013)

• Work efficient Graph Connectivity and MIS

  Further readings (some original papers on topic)

  • Shun, Dhulipala, and Blelloch, A simple and practical linear-work parallel algorithm for connectivity (2014)
  • Luby, A simple parallel algorithm for the maximal independent set problem (1986)
  • Blelloch, Fineman and Shun, Greedy sequential maximal independent set and matching are parallel on average (2012)

• Reachability and Shortest Paths (Transitive closure bottleneck)

  Further readings (some original papers on topic)

  • Ullman and Yannakakis, High Probability Transitive Closure Algorithms (1988)
  • Fineman, Nearly Work-Efficient Algorithms for Digraph Reachability (2018)

• Strongly Connected Components

  Further readings (some original papers on topic)

  • * Coppersmith, Fleischer, Hendrickson, and Pinar, A Divide-and-conquer Algorithm for Identifying Strongly Connected Components (2006)
  • Shudy, Finding Strongly Connected Components in Parallel using O(log^2 n) Reachability Queries (2008)
  • * Blelloch, Gu, Shun, Sun, Parallelism in Randomized Incremental Algorithms (2020) (Just sections 6.2 and 2.3, in that order, or interleaved).

• Least Elements Lists and Tree Embeddings

  Further readings (some original papers on topic)

  • Fakcharoenphol, Rao and Talwar, A tight bound on approximating arbitrary metrics by tree metrics (2003)
  • Blelloch, Gupta, and Tangwongsan, Parallel Approximate Tree Embeddings (2012)
  • * Blelloch, Gu, Shun, Sun, Parallelism in Randomized Incremental Algorithms (2020) (Just sections 6.1 and 2.3).
  • Michael Dinitz, Course Notes on Tree Embedings.

• Graph Spanners

  Further readings (some original papers on topic)

  • Miller, Peng, Vladu and Xu, Improved Parallel Algorithms for Spanners and Hopsets (2015) (Just the part about Spanners, i.e. up through Section 3).

• List ranking and tree contraction

  Further readings (some original papers on topic)

  • Miller and Reif, Parallel Tree Contraction (1989)
  • Blelloch, Fineman, Gu and Sun, Optimal Parallel Algorithms in the Binary Forking Model (2020) (Just sections 3 and 8)

• Minimum Spanning Trees

  Further readings (some original papers on topic)

  • Karger, Klein and Tarjan, A Randomized Linear Time Algorithm for Finding Minimum Spanning Trees (1995)
  • Cole, Klein and Tarjan, Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling (1996)

• Parallel Batch Dynamic Algorithms

  Further readings (some original papers on topic)

  • Tseng, Dhulipala, Blelloch, Batch Parallel Euler-Tour Trees (2019)
  • Acar, Anderson, Blelloch, Dhulipala, Parallel Batch-Dynamic Connectivity (2019)
  • Anderson, Blelloch, and Tangwonsan, Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model (2020)
  • Acar, Anderson, Blelloch, Dhulipala, and Westrick, Parallel Batch-Dynamic Trees via Change Propagation (2020)
  • Anderson, and Blelloch, Parallel Minimum Cuts in O(m log^2 n) Work and Low Depth (2021) (Just Section 3 on Batched Mixed Operations on Trees)

• Convex Hull

  Further readings (some original papers on topic)

  • Overmar and van Leeuwen's original paper on their algorithm
  • Notes from 15-750 on Sequential Incremental Convex Hull
  • Blelloch, Gu, Shun and Sun, Randomized Incremental Convex Hull is Highly Parallel (2020)

• Suffix Arrays and Suffix Trees

  Further readings (some original papers on topic)

  • Karkkainen and Sanders, Simple Linear Work Suffix Array Construction (2003)
  • Shun and Blelloch, A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction (2014)

• Works stealing scheduling

  Further readings (some original papers on topic)

  • Course Notes Section 8
  • Arora, Blumofe and Plaxton, Thread Scheduling for Multiprogrammed Multiprocessors (2001)

• Concurrent data structures

  Further readings (some original papers on topic)

  • Moir and Shavit, Concurrent Data Structures
  • Michael and Scott, Concurrent Queues
  • Harris, Sorted Lists

• Concurrent BSTs

  Further readings (some original papers on topic)

  • Natarajan and Mital, Fast concurrent lock-free binary search trees

• Parallel cache oblivious model

  Further readings (some original papers on topic)

  • Blelloch, Gibbons, Simhadri, Low Depth Cache Oblivious Algorithms (2010)