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

- 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.

- Parallel Computing: Theory and Practice (TAPP)
- Algorithms: Parallel and Sequential (PA)
- Parallel Algorithms
- MIT 6.886 Algorithm Engineering Spring 2019
- CMU 15-897 Parallel Computing: Theory and Practice

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 |