Workshop: Introducing Parallel Prefix-Sums Algorithm and Its Applications in an Undergraduate Course
Abstract: The parallel prefix-sums algorithm and its variations are often used as key substeps in more complex parallel computations. We have successfully introduced the parallel prefix-sum algorithm and its key ideas in a senior level undergraduate Computer Science course. To improve the understanding of these ideas, students were required to solve several problems using simple variations of the basic prefix-sums algorithm. They were also required to solve several non-trivial problems, including their 2-dimensional generalization. We briefly discuss four problems covered in the second category.