Lectures Fundamentals of Algorithms and Data Structures Efficient Algorithms and
Data Structures II Complexity Theory Proseminar Graph Drawing Seminar / Master Seminar Approximation-Algorithms Lab Course Discrete Optimization Courses for PhD Students Oberseminar

Efficient Algorithms and Data Structures II

News

• The room of Thursday's lecture changed to 00.08.038.

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, 10:00–12:00, MI HS 2
  Thursday, 10:00–12:00, 00.08.038
• Exercises:
  Tuesday, 14:00–16:00, MI 01.06.020
  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: Thursday, 04 Jul 2013

• Whole document: [1-443] (lecture - print1 - print4)
• Part 1. Organizational Matters [2-9] (lecture - print1 - print4)
  1. Contents [8-8] (lecture - print1 - print4)
  2. Literatur [9-9] (lecture - print1 - print4)
• Part 2. Linear Programming [10-241] (lecture - print1 - print4)
  1. Introduction [11-38] (lecture - print1 - print4)
  2. Simplex Algorithm [39-62] (lecture - print1 - print4)
  3. Duality [63-99] (lecture - print1 - print4)
  4. Degeneracy Revisited [100-115] (lecture - print1 - print4)
  5. Klee Minty Cube [116-130] (lecture - print1 - print4)
  6. Seidels LP-algorithm [131-157] (lecture - print1 - print4)
  7. The Ellipsoid Algorithm [158-200] (lecture - print1 - print4)
  8. Karmarkars Algorithm [201-241] (lecture - print1 - print4)
• Part 3. Approximation Algorithms [242-442] (lecture - print1 - print4)
  1. Introduction [243-250] (lecture - print1 - print4)
  2. Integer Programs [251-265] (lecture - print1 - print4)
  3. Basic Techniques [266-289] (lecture - print1 - print4)
     1. Deterministic Rounding [266-269] (lecture - print1 - print4)
     2. Rounding the Dual [270-274] (lecture - print1 - print4)
     3. Primal Dual Technique [275-276] (lecture - print1 - print4)
     4. Greedy [277-281] (lecture - print1 - print4)
     5. Randomized Rounding [282-289] (lecture - print1 - print4)
  4. Scheduling on Identical Machines: Local Search [290-297] (lecture - print1 - print4)
  5. Scheduling on Identical Machines: Greedy [298-302] (lecture - print1 - print4)
  6. TSP [303-318] (lecture - print1 - print4)
  7. Rounding Data plus Dynamic Programming [319-363] (lecture - print1 - print4)
     1. Knapsack [319-323] (lecture - print1 - print4)
     2. Scheduling Revisited [324-335] (lecture - print1 - print4)
     3. Bin Packing [336-344] (lecture - print1 - print4)
     4. Advanced Rounding for Bin Packing [345-363] (lecture - print1 - print4)
  8. MAXSAT [364-385] (lecture - print1 - print4)
  9. Facility Location [386-401] (lecture - print1 - print4)
  10. Integer Multicommodity Flows [402-408] (lecture - print1 - print4)
      1. Chernoff Bounds [402-408] (lecture - print1 - print4)
  11. Primal Dual Revisited [409-442] (lecture - print1 - print4)