Parallel Algorithms (CS 388P)
Time/Location/Unique Number. TTh 3:30-5, BAT 207, #49365.
Instructor. Greg Plaxton (plaxton@cs), TAY 3.132, 471-9751, office
hours MW 4-5.
Course Description. We will study fast and
processor-efficient parallel algorithms for shared memory machines
(PRAMs) together with parallel complexity results and the relationship
of the PRAM model to other models of parallel computation. Specific
topics to be discussed include: prefix sums, connectivity, list ranking,
Euler tours, tree contraction, expression evaluation, least common
ancestors, ear decomposition, biconnectivity, chordal graphs, selection,
sorting, straight-line code evaluation, lower bounds, P-completeness,
maximum matching, the APRAM model, routing on hypercubic machines.
Required Text. J. H. Reif (Ed.), Synthesis of Parallel
Algorithms, Morgan Kaufmann, San Mateo, CA, 1993.
Grading. There will be four problem sets (each worth one-sixth of
the overall grade) and a take-home final exam (one-third of the overall
grade).
Problem Sets. Students may discuss the problem sets with one
another but are expected to write up their solutions separately. If a
key idea is obtained from the literature or from another person, then
the source of that idea should be cited. Here are the tentative dates on
which problem sets will be handed out/due: Problem Set 1 (out Th 2/4;
due Th 2/25), Problem Set 2 (out Th 2/25; due Th 3/25), Problem Set 3
(out Th 3/25; due Th 4/15), Problem Set 4 (out Th 4/15; due Th 5/6).
Final Exam. The take-home final exam will be handed out at the
last lecture (Thursday, May 6) and will be due by 5pm on Friday, May 14.
No collaboration is allowed on the take-home final.
Prerequisites. Graduate standing; a course on algorithm design
such as CS 357 or CS 388G.