Course outline

• Parallel Machine Models
  • Parallel Random Access Machine (PRAM)
  • Vector Random Access Machine (VRAM)
  • Brent's Theorem
  • Complexity Measures
  • Message Passing Models
• The NESL Language
  • Parallel Primitives
  • Nested Parallelism
  • Typing Scheme
  • Combining Complexity
• Operations on Sequences and Sets
  • Summing and Scans
  • Selecting (Pack)
  • Append, Reverse
  • Removing Duplicates
  • Union, Intersection and Difference
  • Power Sets
• Sorting, Merging and Medians
  • Selection Sort
  • Quicksort and Quickmedian
  • Radix Sort
  • Halving Merge and Mergesort
  • Sorting nested structures
  • Optimal Median
• Operations on Strings
  • String matching
  • Breaking Text Into Words and Lines
  • Parenthesis Matching
  • Hashing and Searching
  • Line Breaking
• Linked Lists and Trees
  • List Ranking
  • Euler Tour Order of a Tree
  • Rootfix and Leaffix Operations on a Tree
  • Deleting Vertices from a Tree
• Representing and Manipulating Graphs
  • Representations
  • Maximal Independent Set
  • Breadth First Search
  • Connected Components
  • Minimum Spanning Tree
  • Biconnected components
• Computational Geometry and Graphics
  • Quickhull
  • Merge Hull
  • Closest Pair
  • Figure Drawing
  • Hidden Surface Removal
  • Clipping
• Sparse and Dense Matrices
  • LUD Decomposition
  • Sparse Linear Systems
  • Simplex
  • Strassen's Matrix Multiply