Parallel Algorithms

Yihan Sun

MW 5:00-6:20

Office: WCH308

Email: yihans [at] cs [dot] ucr [dot] edu / syhlalala [at] gmail [dot] com

Office hours: Wednesday 2:00pm-3:00pm

Overall Policy


The deadline of Homework 1 is in extended to 27th Jan. Also, please submit your code on iLearn before 23:59 on 27th Jan.

Recommended Textbooks and Courses


Date Content Slides Reading Homework
Week 1: Jan 6 (M) Course introduction and policy. Scheduler. Work-depth model. Reduce algorithms. L1 TAPP Section 3.1, 3.2, 5.1, 5.2, 13 and 17 Homework 1 out [Solution]
Week 1: Jan 8 (W) No class
Week 2: Jan 13 (M) Scan algorithms. Computational models: PRAM, nested parallelism and fork-join. Parallel programming tools. L2 TAPP Section 3.1, 3.2, 5.1, 5.2, 13 and 17
Week 2: Jan 15 (W) Matrix Multiplication. Solve recurrence. Master Theorem. L3 TAPP Section 14, [MSLLF2015], [RR1987], [GSSB2013]
Week 3: Jan 20 (M) No class. Martin Luther King, Jr holiday.
Week 3: Jan 22 (W) Sorting algorithms. L4 TAPP Section 14, [MSLLF2015], [RR1987], [GSSB2013]
Week 4: Jan 27 (M) Deterministic parallelism. L5 [BFGS2012], [SGBFG2015] [BGSS2020] Homework 1 due, Homework 2 out [Solution]
Week 4: Jan 29 (W) Parallel graph algorithms L6 [MS2003], [DBS2017], [SB2013], [Shun2017] (Chapters 7-8), [KS1997], [BGST2015], [MBBC2007], [EMRB2012], [YRB2018], [DBS2019]
Week 5: Feb 3 (M) Parallel graph algorithms L7 [MS2003], [DBS2017], [SB2013], [Shun2017] (Chapters 7-8), [KS1997], [BGST2015], [MBBC2007], [EMRB2012], [YRB2018], [DBS2019]
Week 5: Feb 5 (W) Parallel data structures. L7-2 L8 PA Part 9, [BFS2016], [Sun2019], [BFS2018], [SBLP2019], [SB2019], [DBS2019]
Week 6: Feb 10 (M) Parallel data structures. L9 PA Part 9, [BFS2016], [Sun2019], [BFS2018], [SBLP2019], [SB2019], [DBS2019]
Week 6: Feb 12 (W) Parallel data structures. L10 PA Part 9, [BFS2016], [Sun2019], [BFS2018], [SBLP2019], [SB2019], [DBS2019]
Week 7: Feb 17 (M) No class. Presidents' Day holiday Course project proposal due
Week 7: Feb 19 (W) Locality and I/O efficient parallel algorithms L11 [Demaine2002] Homework 2 due
Week 8: Feb 24 (M) No class Homework 3 out [Solution]
Week 8: Feb 26 (W) Locality and I/O efficient parallel algorithms L12 [Demaine2002]
Week 9: Mar 2 (M) Scheduling
Week 9: Mar 4 (W) No class - prepare for presentation L12-2 (IO)
L13 (scheduling)
Week 10: Mar 9 (M) Project presentation Homework 3 due
Week 10: Mar 11 (W) Project presentation
Week 11 Take-home final exam Course project report due