| 
      
       Lecturer: 
       Prof. Dr. Ernst W. Mayr
       
        | 
     
     
      
        
       | 
      
       Area: 
       4 hours per week in area III (Theoretical Computer Science) 
       advanced course
       
        | 
     
     
      
        
       | 
      
       Time and Place: 
        Tue 08:30 - 10:00, Room 2770 
	Fri 08:30 - 10:00, Room 1100 
	Start: May 2nd
	
        | 
     
     
      
        
       | 
      
       Tutorials: 
       2 hours per week 
       Tu 10:15 - 12:15, Room S2225 
       Teaching Assistant:
       Tom Friedetzky 
       Course Certificate: To get a course certificate students must
       get at least 40% on the homework assignments and pass the final exam.
       
        | 
     
     
      
        
       | 
      
       Audience: 
       3rd and 4th year students in computer science 
       students with computer science as minor
       
        | 
     
     
      
        
       | 
      
       Prerequisites: 
       2nd year courses 
       Parallel Algorithms
       is recommended.
       
        | 
     
     
      
        
       | 
      
       Contents: 
       The purpose of this course is to study some of the fundamental concepts
       in parallel computation. These include parallel machine models, the
       design of parallel algorithms, and the basis of parallel complexity
       theory. Especially, it will be focused on the following topics:
       
        | 
     
     
      
        
       | 
      
       List of Topics:  
       
       
-  Hypercubes and related networks
-  Shuffle exchange and de-Bruijn networks
-  Definitions and basic properties
 -  The Diaconis card tricks:
-  A shuffling trick
 -  A mind-reading trick
  
 -  Simulation of normal hypercube algorithms
 -  More containment and simulation results
  
 -  The discrete Fourier transformation (DFT)
-  The algorithmic fundamentals
 -  Implementation on the butterfly and SE network
 -  Applications: convolution, polynomial arithmetics
 -  Bit complexity of the DFT
  
 -  Algorithms for packet routing
-  Definitions, models
 -  Greedy algorithms, worst-case instances
 -  A lower bound for oblivious routing
 -  Concentration and monotone routing
-  Concentration routing on the hypercube
 -  Concentration routing on the butterfly
 -  Inverse concentration routing
 -  Monotone routing
 -  Generalized monotone routing
  
 -  Randomized routing on the butterfly
-  Analysis of the node congestion
 -  Analysis of the running time
 -  Other contention resolution protocols
 -  Application to the hypercube
  
 -  Changing worst-case instances into average-case instances
-  Hashing, r-wise independent hash functions
 -  Randomized routing
  
 -  Complements: Ranade's algorithm, combining, multiple copies
  
 -  Sorting
-  Odd even merge sort
 -  Sorting small sets
  
  
 -  The PRAM model
-  Basic discussions
 -  The variants of the PRAM model
 -  Basic algorithms
-  Census functions and prefix computation
 -  Accelerated cascading
-  Maximum in constant time
 -  Algorithm with double logarithmic running time
 -  Accelerated cascading
  
 -  Partitioning
-  Simple merging algorithm
 -  Optimal EREW merging algorithm
  
 -  Symmetry breaking
-  The basic routine
 -  A fast 3-coloring algorithm
 -  An optimal 3-coloring algorithm
  
  
 -  Lists and trees
-  List ranking
-  A simple LR algorithm
 -  An optimal LR algorithm, with analysis
  
 -  Euler tour
-  Definition, simple algorithm
 -  Computation of tree functions
-  Rooting of a tree
 -  Postorder numbering
 -  Level of a node
  
  
 -  Tree contarction
-  The rake operation
 -  Evaluation of arithmetic expressions
  
 -  Lowest common ancestors
-  Definitions
 -  The Schieber/Vishkin algorithm
  
 -  Sorting algorithms
-  Definitions
 -  Merging based algorithms
 -  Cole's merge sort
  
 -  Lower bounds for the PRAM
-  Basics
 -  The general method
 -  Bounds for specific problems
  
  
 -  P-completeness
-  Concepts of parallelizabilty
 -  CVP ist P-complete
 -  Applications: DFS, LP
  
  
  
       
       
       
        | 
     
     
      
        
       | 
      
       Related and Advanced Lectures: 
       Efficient Algorithms and
       Data structures II
       
        | 
     
     
      
        
       | 
      
       Lecture Notes: 
       not available
       
        | 
     
     
      
        
       | 
      
       References: 
        
	 - F. Thomson Leighton:
	 
 - Introduction to Parallel Algorithms and Architectures:
 
             Arrays - Trees - Hypercubes 
	     Morgan Kaufman Publishers, San Mateo, CA, 1992
	  - Joseph JáJá:
	 
 - Parallel Algorithms
 
                Addison Wesley Publishing Company, 1992
	  
	
        | 
     
     
      
        
       | 
      
       Office Hours: 
       look here
       
        |