Lectures Introduction to Theory of Computation Discrete Probability Theory Efficient Algorithms and
Data Structures II Online and Approximation Algorithms Complexity Theory Proseminar Graph Drawing Lab Course Algorithms for Programming Contests

Efficient Algorithms and Data Structures II

News

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:
  TBA
• Exercises:
  Tuesday, 16:00–18:00, MI 01.06.011
  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 (IN2003) advantagious, but not necessary.
• Recommended for:
  In-depth knowledge in topic Algorithms
• Related and Advanced Lectures:
  Internet algorithmics
  Randomized Algorithms (IN2160)
  Complexity Theory (IN2007)
  

Slides: Friday, 17 Jul 2015

• Whole document: [1-491] (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-252] (lecture - print1 - print4)
  1. Introduction [12-49] (lecture - print1 - print4)
  2. Simplex Algorithm [50-73] (lecture - print1 - print4)
  3. Duality [74-120] (lecture - print1 - print4)
     1. Weak Duality [74-79] (lecture - print1 - print4)
     2. Simplex and Duality [80-82] (lecture - print1 - print4)
     3. Strong Duality A [83-84] (lecture - print1 - print4)
     4. Strong Duality B [85-99] (lecture - print1 - print4)
     5. Interpretation of Dual Variables [100-113] (lecture - print1 - print4)
     6. Computing Duals [114-120] (lecture - print1 - print4)
  4. Degeneracy Revisited [121-136] (lecture - print1 - print4)
  5. Klee Minty Cube [137-151] (lecture - print1 - print4)
  6. Seidels LP-algorithm [152-170] (lecture - print1 - print4)
  7. The Ellipsoid Algorithm [171-222] (lecture - print1 - print4)
  8. Karmarkars Algorithm [223-252] (lecture - print1 - print4)
• Part 3. Approximation Algorithms [253-491] (lecture - print1 - print4)
  1. Introduction [254-269] (lecture - print1 - print4)
  2. Integer Programs [270-283] (lecture - print1 - print4)
  3. Basic Techniques [284-310] (lecture - print1 - print4)
     1. Deterministic Rounding [284-287] (lecture - print1 - print4)
     2. Rounding the Dual [288-292] (lecture - print1 - print4)
     3. Primal Dual Technique [293-294] (lecture - print1 - print4)
     4. Greedy [295-300] (lecture - print1 - print4)
     5. Randomized Rounding [301-310] (lecture - print1 - print4)
  4. Scheduling on Identical Machines: Local Search [311-318] (lecture - print1 - print4)
  5. Scheduling on Identical Machines: Greedy [319-324] (lecture - print1 - print4)
  6. TSP [325-340] (lecture - print1 - print4)
  7. Rounding Data plus Dynamic Programming [341-387] (lecture - print1 - print4)
     1. Knapsack [341-345] (lecture - print1 - print4)
     2. Scheduling Revisited [346-358] (lecture - print1 - print4)
     3. Bin Packing [359-368] (lecture - print1 - print4)
     4. Advanced Rounding for Bin Packing [369-387] (lecture - print1 - print4)
  8. Integer Multicommodity Flows [388-405] (lecture - print1 - print4)
     1. Chernoff Bounds [388-405] (lecture - print1 - print4)
  9. MAXSAT [406-427] (lecture - print1 - print4)
  10. Primal Dual Revisited [428-461] (lecture - print1 - print4)
  11. Cuts \& Metrics [462-475] (lecture - print1 - print4)
  12. Facility Location [476-491] (lecture - print1 - print4)