ICS 443: Parallel Algorithms
Description: Introduction to parallel models of computation and design and analysis of parallel algorithms.
- The students will be aware of current models of parallel computation
- The students will be proficient with algorithmic techniques for designing parallel algorithms
- The students will be able to apply these techniques to design new parallel algorithm
- The students will be able to analyze the efficiency of parallel algorithms
Course Learning Outcomes
- Students will be able to identify various models of parallel computation
- Students will be able to list fundamental parallel algorithms
- Students will be able to use learned techniques to implement parallel algorithms on modern many-core architectures
- Students will be able to carry out analysis of parallel algorithms
- Students will be able to differentiate between efficient and inefficient parallel algorithms
- Students will be able to design efficient parallel algorithms
- Students will be able to check parallel algorithms for correctness
- Students will be able to analyze the runtime and efficiency of parallel algorithms.
Program Learning Outcomes
- a. Students can apply knowledge of computing and mathematics appropriate to the discipline
- b. Students can analyze a problem, and identify and define the computing requirements appropriate to its solution
- c. Students can design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs
- d. Students can function effectively on teams to accomplish a common goal
- f. Students can communicate effectively with a range of audiences
- h. Students can recognize the need for and an ability to engage in continuing professional development
- i. Students can use current techniques, skills, and tools necessary for computing practice
Prerequisites: 311 with C or better
Textbook(s): Joseph Jaja, Introduction to Parallel Algorithms, Addison Wesley, 1992.
Grading: The students will be graded on class participation (20\%), homeworks (40\%), and the final exam (40\%).
Policies: Late homework policy: Homeworks are due on Thursday at 1:30pm (the beginning of the lecture). Late homeworks can be emailed to the instructor. Penalty for late homeworks is a letter grade reduction (e.g. from A to B) for within each 24 hours that it is late. For example, submission of homework that deserves a letter grade A will be graded B if submitted between Thursday 1:30pm and Friday 1:30pm; will be graded C if submitted before Saturday 1:30pm; and will be graded D if submitted before Sunday 1:30pm. Extenuating circumstances do arise, therefore, a single homework will be accepted up to 72 hours late without any reduction in grade.
- Week 1: Introduction, models of parallel computation, Brent’s scheduling principle
- Week 2: Parallel scan, prefix sums
- Week 3: Searching, selection, basic sorting
- Week 4: Sorting networks, 0-1 principle
- Week 5: List ranking, pointer jumping, symmetry breaking
- Week 6: Tree algorithms
- Week 7: Lowest common ancestors, range minima queries
- Week 8, 9: Graph algorithms: Connected and biconnected components, minimum spanning trees, shortest paths
- Week 10,11:Computational Geometry: convex hull, half-plane intersection, planesweep
- Week 12-13: Linear algebra: matrix-matrix and matrix-vector multiplication
- Week 14: Numerical algorithms
- Week 15: String algorithms
- Week 16: Advanced models of computation, limits of parallelism, P-completeness