Lectures Introduction to Theory of Computation Discrete Probability Theory Fundamentals of Algorithms and Data Structures Efficient Algorithms and
Data Structures II Online and Approximation Algorithms Complexity Theory Proseminar Graph Drawing Seminar / Master Seminar Approximation Algorithms Energy-efficient Algorithms Lab Course Algorithms for Programming Contests Courses for PhD Students Oberseminar

Efficient Algorithms and Data Structures II

News

There will be no lecture on Monday, May 5th

Course

• Lecturer:
  Prof. Dr. Harald Räcke
• Module: IN2004, TUMonline
• Area:
  4+2 lectures per week in area III (Theoretical Computer Science)
  advanced course, topic algorithms
• Time and Location:
  Monday, 12:00–14:00, 00.13.009A
  Friday, 10:00–12:00, 00.13.009A
• Exercises:
  Teaching Assistant: Chintan Shah
• Audience:
  graduate students of computer science
  students with computer science as minor
• ECTS: 8 points
• Prerequisites:
  1st and 2nd year courses
  Course Efficient Algorithms and Datastructures I advantagious, but not necessary.
• Recommended for:
  In-depth knowledge in topic Algorithms
• Related and Advanced Lectures:
  Internet algorithmics
  Randomized Algorithms
  Complexity Theory
  

Slides: Friday, 11 Jul 2014

• Whole document: [1-521] (lecture - print1 - print4)
• Part 1. Organizational Matters [2-10] (lecture - print1 - print4)
  1. Contents [8-8] (lecture - print1 - print4)
  2. Literatur [9-10] (lecture - print1 - print4)
• Part 2. Linear Programming [11-247] (lecture - print1 - print4)
  1. Introduction [12-43] (lecture - print1 - print4)
  2. Simplex Algorithm [44-67] (lecture - print1 - print4)
  3. Duality [68-104] (lecture - print1 - print4)
  4. Degeneracy Revisited [105-120] (lecture - print1 - print4)
  5. Klee Minty Cube [121-135] (lecture - print1 - print4)
  6. Seidels LP-algorithm [136-163] (lecture - print1 - print4)
  7. The Ellipsoid Algorithm [164-206] (lecture - print1 - print4)
  8. Karmarkars Algorithm [207-247] (lecture - print1 - print4)
• Part 3. Approximation Algorithms [248-521] (lecture - print1 - print4)
  1. Introduction [249-264] (lecture - print1 - print4)
  2. Integer Programs [265-278] (lecture - print1 - print4)
  3. Basic Techniques [279-305] (lecture - print1 - print4)
     1. Deterministic Rounding [279-282] (lecture - print1 - print4)
     2. Rounding the Dual [283-287] (lecture - print1 - print4)
     3. Primal Dual Technique [288-289] (lecture - print1 - print4)
     4. Greedy [290-295] (lecture - print1 - print4)
     5. Randomized Rounding [296-305] (lecture - print1 - print4)
  4. Scheduling on Identical Machines: Local Search [306-313] (lecture - print1 - print4)
  5. Scheduling on Identical Machines: Greedy [314-318] (lecture - print1 - print4)
  6. Rounding Data plus Dynamic Programming [319-365] (lecture - print1 - print4)
     1. Knapsack [319-323] (lecture - print1 - print4)
     2. Scheduling Revisited [324-336] (lecture - print1 - print4)
     3. Bin Packing [337-346] (lecture - print1 - print4)
     4. Advanced Rounding for Bin Packing [347-365] (lecture - print1 - print4)
  7. Integer Multicommodity Flows [366-383] (lecture - print1 - print4)
     1. Chernoff Bounds [366-383] (lecture - print1 - print4)
  8. MAXSAT [384-405] (lecture - print1 - print4)
  9. Primal Dual Revisited [406-439] (lecture - print1 - print4)
  10. Cuts \& Metrics [440-453] (lecture - print1 - print4)
  11. Probabilistically Checkable Proofs [454-521] (lecture - print1 - print4)