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.

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