Scalable Parallel Algorithms and Data Structures

CMSC858N: Spring 2023

Time and Location: Tuesday/Thursday, 2–3:15pm, CSI 2107

Instructor: Laxman Dhulipala (IRB 5150); Office hours 3:15--4:15pm Tu/Th in IRB 5150

TA: Kishen Gowda (IRB 2104); Office hours 4--5pm Wed outside IRB 2104



Course Description

This is a research-oriented course on parallel algorithms. The main goal is to develop a rigorous understanding of parallel algorithm design and analysis. The later parts of the course will study a variety of applications which can benefit from fast, scalable, and theoretically-efficient parallel implementations.

This course qualifies as a theory concentration requirement.

Prerequisites: You should be comfortable with algorithm design and analysis (e.g., you should be comfortable with the material from CMSC451). Prior experience with C++ will be helpful, but you should be able to pick up everything you need to know during this course.



Date Topic Readings Notes
Jan 26 (Th) Brief History of Parallel Computing and Parallel Models  ParAlg [Ch.1--2]  Notes
lgorithms on Sequences      
Jan 31 (Tu) Parallel Building Blocks, Basic Algorithms  ParAlg [Ch.4]  Notes
Feb 02 (Th) Merging and Sorting  ParAlg [Ch.4]  Notes
Feb 07 (Tu) Integer Sorting: Counting and Radix Sort
[HW1(W) out]
RegionsSort  Notes
Algorithms on Trees      
Feb 09 (Th) List Ranking and Tail Bounds  ParAlg [Ch.3]  Notes
Feb 14 (Tu) Euler Tours and Parallel Tree Contraction    Notes
Feb 16 (Th) LCA and RMQ
[[HW1(P)] out]
Feb 21 (Tu) [No Class -- Prerecorded Lecture] Parallel Cartesian Trees
[HW1(W) due]
Algorithms on Graphs      
Feb 23 (Th) BFS and Low-Diameter Decomposition    Notes
Feb 28 (Tu) No Class    
Mar 02 (Th) LDD Continued    Notes
Mar 07 (Tu) LDD Applications    Notes
Mar 09 (Th) Luby's Algorithm
[HW1(P) due]
Mar 14 (Tu) Randomized Algorithms Recap
Mar 16 (Th) Random Incremental Algorithms
Spring Break      
Scheduling and Models      
Mar 28 (Tu) Work-Stealing and Analysis    
Mar 30 (Th) Parallel Cache-Oblivious Algorithms
[HW2(W) due]
Apr 04 (Tu) Parallel In-Place Algorithms    
Apr 06 (Th) Massively Parallel Computation (MPC): Basics    
Other Topics and Applications (subject to change)      
Apr 11 (Tu) Optimal Binary-Forking
[Project Check-in]
Apr 13 (Th) Parallel Batch-Dynamic Trees    
Apr 18 (Tu) Graph Compression: Formats and Reordering    
Apr 20 (Th) Parallel Graph Processing: Julienne and GBBS    
Apr 25 (Tu) Guest Lecture by Brian Wheatman: SIMD and Vectorization    
Apr 27 (Th) Parallel Algorithms for Ordered Sets and Maps
[Project Check-in]
May 02 (Tu) Compressed and Augmented Maps    
May 04 (Th) Batch-Dynamic Algorithms: Forest Connectivity    
May 09 (Tu) Batch-Dynamic Algorithms: Dynamic Connectivity    
May 11 (Th) Project Presentations    


Mask Policy

We will follow the masking and health guidelines laid out by the University. Note that masking is still recommended: “Effective Monday, August 29, wearing a mask will not be required while indoors in most situations, including classrooms. However, wearing a KN95 mask is recommended while indoors for added protection.”

Our Pledge to the Students

Your education is very important to us, and we respect each of you regardless of how you do in the class. Our expectations of you are that you attend class and pay full attention, and give enough time to the course. We strongly encourage you to ask questions in class, and to come to the office hours (the instructors’ or the TAs’) with any further questions. We can have a very enjoyable educational experience if you pay attention in class, give sufficient time to our course, and bring any difficulties you have promptly to our attention. We look forward to our interaction both inside and outside the classroom.

Academic Accomodations for Disabilities

Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.


Some topics are drawn from recent courses by Umut Acar, Soheil Behnezhad, Guy Blelloch, Mohsen Ghaffari, Yan Gu, Julian Shun, and Yihan Sun. I am grateful to my colleagues for making their courses publicly available, and encourage you to make course material for new courses freely available (e.g., not on Piazza) as much as possible.

Web Accessibility