MW 5:00-6:20

Office: TBA

Office hours: TBA

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