| 
      
       Lecturer: 
       Prof. Dr. Angelika Steger
       
        | 
     
     
      
        
       | 
      
       Area: 
       4 hours per week in area III (Theoretical Computer Science) 
       advanced course
       
        | 
     
     
      
        
       | 
      
       Time and Place: 
       Thu 08:30 - 10:00, Room S1128 
       Fri 10:15 - 11:45, Room N1190 
       Start: May 2nd
       
        | 
     
     
      
        
       | 
      
       Tutorials: 
       2 hours per week 
       Thu 16:15 - 18:00, Room S2229 
       Start: May 15th  
       Teaching Assistant:
       Ulrich Voll 
       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 of computer science 
       students with computer science as minor
       
        | 
     
     
      
        
       | 
      
       Prerequisites: 
       2nd year courses 
       
       Efficient Algorithms and Datastructures is recommended
       
        | 
     
     
      
        
       | 
      
       Contents: 
       This lecture deals in particular with the following topics:
       
	-  Flow Problems
	
 -  Connectivity of Graphs
        
 -  Planar Graphs
	
 -  Matching Problems
	
 -  Linear Programming
	
 -  Approximation Algorithms
       
  
       
        | 
     
     
      
        
       | 
      
       Related and Advanced Lectures: 
       Parallel Algorithms II
       
        | 
     
     
      
        
       | 
      
       Lecture Notes: 
       Some attendees of the lecture are working on lecture notes.
       The current version can be found here.
       
        | 
     
     
      
        
       | 
      
       References: 
        
         - Christos H. Papdimitriou, Kenneth Steiglitz:
         
 - Combinatorial Optimization: Algorithms and Complexity
 
         Prentice-Hall, 1982
         - Emden-Weinert, Hougardy, Kreuter, Prömel, Steger:
        
- Einführung
in Graphen und Algorithmen
  
        Lecture notes, Berlin 1996
          
	
        | 
     
     
      
        
       | 
      
       Office Hours: 
       look here
       
        |