Parallel Algorithms

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

Paper Reading - 10%. On the course website, there are a list of related papers for each topic. The students need to submit paper reviews for three papers.
Homework - 40%. In total, there will be 3 homework sets. Students should complete them independently.
Course Project - 30%. Students need to work on simple implementations about the algorithms learned in the class.
Final Exam - 20%. The final will be a take-home exam. It will cover all topics in the course, mainly about concepts, proofs and algorithms discussed in the lectures.
Class Participation - 5% bonus. Students are encouraged to discuss the course material and ask questions during the lectures and office hours. The students involved in the class participation can get up to 5 bonus points.

Announcement

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

Syllabus

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) scheduling-full Review
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