Remark: I am trying an experiment this semester.

• I am going to try and keep my course notes (i.e., the notes I use to teach from during class) on line, using Word 6.0c on a PC, augmented with Microsoft Internet Assistant (IA).
• I will then use IA to convert the files from Word format to html, and post the resulting file on the Web (you are reading it now).
• I will continually do a subjective cost/benefit analysis and we will see how far things get.
  • Be aware that IA converts to HTML 2.0, which includes almost no interesting features.
  • In particular, HTML currently does not support any nontrivial math/symbols (e.g., no superscripts or subscripts, no Greek characters, no special symbols, etc.).
• I am skeptical about how far I will get in an algorithms-based course without support for mathematical expressions, in terms of the notes I am preparing being of use to the students. (Note: keeping my notes on-line only increases my course preparation time.)
• So, we will start with the course outline - notice the second line already has 2 symbols (Theta and Omega) missing, as do numerous other lines - and then I will move on to the first couple of days of lecture notes.

OUTLINE

1. Asymptotic Analysis: Review
   1. O, , and very briefly
   2. Handouts on notation
      1. Back of M&S text
      2. SIG handout - put on web (?)
      3. CLR book or other data structures/algorithms books (reference)
   3. Homework on notation
2. Sorting Networks
   1. Combinational Circuits
      1. Comparator
      2. Wire
   2. Batcher's Bitonic MergeSort
   3. Homework on Sorting Networks
3. Introduction to Parallel Algorithms and Architectures
   1. RAM (A, 36-39)
      1. Memory with m locations
      2. Processor (1)
      3. Memory Access Unit
      4. Each step of an algorithm:
         1. Read phase
         2. Compute phase
         3. Write phase
      5. Discuss time per step
   2. PRAM (A, 39-50)
      1. n identical processors
      2. A common memory with m locations
      3. Memory Access Unit
      4. Memory Access:
         1. Exclusive Read
         2. Concurrent Read
         3. Exclusive Write
         4. Concurrent Write
            1. Priority CW
            2. Common CW
            3. Arbitrary CW
            4. Random CW
            5. Combining CW
      5. Discuss time per step
      6. Simple examples on PRAM
         1. Minimum
         2. Broadcast
         3. Prefix
            1. Finding roots in a forest
            2. Running sum
            3. Running minimum
         4. Search
   3. Distributed Memory vs. Shared Memory
   4. Distributed Address Space vs. Global Address Space
   5. Interconnection Networks
      1. Measures
         1. Maximum degree of a processor
         2. Communication Diameter
         3. Bisection Width
         4. Time to perform basic operations
      2. Models (discuss: measure, searching, semigroup)
         1. PRAM (as means of comparison)
         2. Linear Array and Ring
         3. Mesh
         4. Mesh-of-Trees
         5. Pyramid
         6. Hypercube
   6. SIMD vs. MIMD
   7. Granularity
   8. General Performance Measures
      1. Running time:
      2. Cost:
      3. Work
      4. Speedup:
      5. Efficiency:
      6. Discuss relationship between measures and discuss goals of algorithm development
      7. Amdahl's Law: , where is the fraction of operations that must be performed sequentially.
   9. Homework on models of computation
4. Matrix Multiplication
   1. PRAM
   2. Mesh
5. Parallel Prefix (A, chapt 4)
   1. Review
   2. Problems that can be solved with prefix
      1. Maximum Sum Subsequence
      2. Array Packing
      3. Interval Broadcasting
      4. Computing Cliques of Circular Arcs
      5. Simple Point Domination
   3. Homework on Prefix Problems and their Applications
6. Pointer Jumping
   1. Parallel Prefix
   2. List Ranking
   3. Euler Tour (?)
      1. Depth-First Traversal and Applications
      2. Breadth-First Traversal and Applications
   4. Connected Components (?)
7. Divide-and-Conquer
   1. Define and give generic solution strategy
   2. Fundamental Problems :
      1. Mergesort
         1. Sequential Explanation and Analysis
         2. Mergesort on Linear Array
         3. Reminder of Bitonic Sort (i.e., parallel merge)
            1. Bitonic Sort on Hypercube
            2. Bitonic Sort on Mesh
      2. Quicksort
         1. Generic explanation and solution
         2. Array Implementation
            1. Worst-Case Analysis
            2. Expected-Case Analysis
         3. Medium-/Coarse-Grained Parallel Implementation
      3. Advanced Problems (sequential and parallel implementations):
         1. Image Processing
            1. Component Labeling
            2. Internal Distances
            3. Convex Hull
         2. Computational Geometry
            1. Convex Hull
            2. All-Nearest Neighbors
            3. Line Segment Intersection
      4. Homework problems on D&C
   3. The Greedy Method (B&P, chapt 12)
      1. Define and give generic solution strategy
      2. Examples (discuss sequential and parallel implementations):
         1. Optimal Sequential Storage Order
         2. Knapsack Problem
         3. Minimum Spanning Tree
            1. Kruskal's Algorithm
            2. Prim's Algorithm
         4. Shortest Path Algorithms
      3. Homework problems on Greedy Algorithms
   4. Mesh-of-Trees
      1. Enumeration Sort (n items on MOT of size n2)
      2. Convex Hull (Image)
      3. Convex Hull for planar point data (n items on MOT of size n2)
   5. Bus-Based Models
      1. Meshes with Buses
         1. Sample problems
      2. Reconfigurable Meshes
         1. Sample problems
      3. Homework problems for bus-based models
   6. Dynamic Programming (??)
      1. Sequential
      2. Mesh

   
   

   ---

   Russ Miller (miller@cs.buffalo.edu)
   
   

   ---

   Copyright © 1996-1997 by Russ Miller.

   All rights reserved. No part of this document may be used in any form by any electronic or mechanical means without permission in writing by the author.