ENEE 759K: Parallel Algorithms

Course Goals

• Introduction to the theory of parallel algorithms. The course will highlight parallel algorithmic thinking for obtaining good speed-ups with respect to serial algorithms.
• To put parallel algorithmics in the context of state-of-the-art parallel computing, and the challenges parallel computing is facing.

Course Prerequisites

• ENEE759F (the new core course), or any course on Algorithms.

Prerequisite Topics

• Elementary algorithms and data structures.

Course readings:

• Class notes and research papers will be provided by the instructor.
• Reference book: J. JaJa, An Introduction to Parallel Algorithms, Addison Wesley, 1992.

Some Core Topics:

• Introduction to Parallel Processing: Principles of available, as well as evolving, parallel computer systems; this includes multi-processing and instruction-level parallelism. Parallel Models of computation.
• Introduction to Parallel Algorithms: Performance of Parallel Algorithms, Optimality Notions
• Basic Techniques: Balanced Trees, Pointer Jumping, Divide-and-Conquer, Partitioning, Pipelining, Accelerated Cascading, Breaking Symmetry
• Trees and Lists: List Ranking, The Euler Tour Techniques, Tree Connection, Evaluation of Arithmetic Expressions
• Searching, Merging and Sorting
• Graphs: Connected Components, Transitive Closure, Paths Problems
• Strings: Some string matching algorithms

Grading method:

• Midterm and final exams and homework.