# Parallel Algorithms

Yihan Sun

MW 5:00-6:20

Office: TBA

Office hours: TBA

## 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-4 homework sets. Students should complete them independently, without any discussion with other students (discussing with the lecturer or TAs is encouraged).
• 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.

## (Draft) Syllabus

 Date Content Slides Reading Homework Week 1: Jan 6 (M) Course introduction and policy. Work-depth model. Reduce and scan algorithms. Homework 1 out Week 1: Jan 8 (W) No class Week 2: Jan 13 (M) Basic concepts. PRAM, nested parallelism and fork-join. Solve recursion. Parallel programming tools. Week 2: Jan 15 (W) Sorting and semi-sorting. Week 3: Jan 20 (M) No class. Martin Luther King, Jr holiday. Week 3: Jan 22 (W) Sorting and semi-sorting. Homework 1 due Week 4: Jan 27 (M) Deterministic parallelism. Homework 2 out Week 4: Jan 29 (W) Parallel data structures. Week 5: Feb 3 (M) Parallel data structures. Week 5: Feb 5 (W) Parallel data structures. Course project proposal due Week 6: Feb 10 (M) Locality and I/O efficient parallel algorithms Homework 2 due Week 6: Feb 12 (W) Locality and I/O efficient parallel algorithms Homework 3 out Week 7: Feb 17 (M) No class. Presidents' Day holiday Week 7: Feb 19 (W) Parallel graph algorithms Week 8: Feb 24 (M) Parallel graph algorithms Week 8: Feb 26 (W) Scheduling Week 9: Mar 2 (M) Scheduling Homework 3 due Week 9: Mar 4 (W) TBA Week 10: Mar 9 (M) Project presentation Week 10: Mar 11 (W) Project presentation Week 11 Take-home final exam