CS 509: Syllabus

  • Parallel algorithms on the PRAM (shared-memory) model, including algorithms for sorting and searching, for computational geometry, for graph problems, for linear algebra, and for string manipulation. (Approximately 10 weeks.)
  • How to map PRAM algorithms on realistic interconnection topologies, including hypercubic topologies (hypercubes, omegas, etc.) and meshes, so that algorithms studied in part (1) can be used on real machines. (Approximately 3 weeks.)
  • A high-level overview of parallel complexity theory: what can complexity theory tell us about the parallelization of problems? (Approximately 2 weeks.)
    • Part (2), which is not covered in the text, will be covered through lectures and handouts. The course does not include any programming: its emphasis is on design and analysis.

    The main prerequisite for the course is some undergraduate class in data structures and algorithms that included analysis of algorithms (asymptotic notation and solution methods for recurrences) and some basic graph and other algorithms; CS 461, as well as EECE 331, fulfill this prerequisite.

    Back to CS 509 home page

    HTML 2.0 Checked! Last updated and validated January 20, 1997, by moret@cs.unm.edu