LTI
LTI

Efficient Algorithms and Data Structures II

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:
    Wednesday, 12:00–14:00, 00.13.009A
    Friday, 10:00–12:00, MI HS3
  • Exercises:
    Monday, 14:00–16:00, MI 03.11.018
    Teaching Assistant: Richard Stotz
  • 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

help   Slides: Friday, 13 Jul 2018

  • Whole document: [1-554] (std · pr4 · pr1 · lec · two)
  • Part 1. Organizational Matters [2-10] (std · pr4 · pr1 · lec · two)
    1. Contents [8-8]
    2. Literatur [9-10]
  • Part 2. Linear Programming [11-258] (std · pr4 · pr1 · lec · two)
    1. Introduction to Linear Programming [12-52] (std · pr4 · pr1 · lec · two)
    2. Simplex Algorithm [53-76] (std · pr4 · pr1 · lec · two)
    3. Duality [77-116] (std · pr4 · pr1 · lec · two)
      1. Weak Duality [77-81] (std · pr4 · pr1 · lec · two)
      2. Simplex and Duality [82-84] (std · pr4 · pr1 · lec · two)
      3. Strong Duality [85-102] (std · pr4 · pr1 · lec · two)
      4. Interpretation of Dual Variables [103-109] (std · pr4 · pr1 · lec · two)
      5. Computing Duals [110-116] (std · pr4 · pr1 · lec · two)
    4. Degeneracy Revisited [117-132] (std · pr4 · pr1 · lec · two)
    5. Klee Minty Cube [133-147] (std · pr4 · pr1 · lec · two)
    6. Seidels LP-algorithm [148-166] (std · pr4 · pr1 · lec · two)
    7. The Ellipsoid Algorithm [167-217] (std · pr4 · pr1 · lec · two)
    8. Karmarkars Algorithm [218-258] (std · pr4 · pr1 · lec · two)
  • Part 3. Approximation Algorithms [259-554] (std · pr4 · pr1 · lec · two)
    1. Introduction to Approximation [260-275] (std · pr4 · pr1 · lec · two)
    2. Integer Programs [276-289] (std · pr4 · pr1 · lec · two)
    3. Basic Techniques [290-316] (std · pr4 · pr1 · lec · two)
      1. Deterministic Rounding [290-293]
      2. Rounding the Dual [294-298]
      3. Primal Dual Technique [299-300]
      4. Greedy [301-306]
      5. Randomized Rounding [307-316]
    4. Scheduling on Identical Machines [317-330] (std · pr4 · pr1 · lec · two)
      1. Local Search [317-324]
      2. Greedy [325-330]
    5. Rounding Data + Dynamic Programming [331-377] (std · pr4 · pr1 · lec · two)
      1. Knapsack [331-335]
      2. Scheduling Revisited [336-348]
      3. Bin Packing [349-358]
      4. Advanced Rounding for Bin Packing [359-377]
    6. Randomized Rounding [378-432] (std · pr4 · pr1 · lec · two)
      1. Chernoff Bounds [378-390]
      2. Integer Multicommodity Flows [391-395]
      3. MAXSAT [396-417]
      4. MAXCUT [418-432]
    7. Primal Dual Techniques [433-466] (std · pr4 · pr1 · lec · two)
      1. Primal Dual Revisited [433-439]
      2. Feedback Vertex Set for Undirected Graphs [440-447]
      3. Primal Dual for Shortest Path [448-454]
      4. Steiner Forest [455-466]
    8. Cuts & Metrics [467-480] (std · pr4 · pr1 · lec · two)
    9. Hardness of Approximation [481-554] (std · pr4 · pr1 · lec · two)

July 2022: Jens Quedenfeld completed his doctoral degree.

June 2022: Maximilian Janke completed his doctoral degree.

March 2022: Alexander Eckl completed his doctoral degree.

June 2021: Leon Ladwig completed his doctoral degree.

February 2020: The Program Committee of SWAT 2020 is chaired by Susanne Albers.

February 2020: Susanne Albers is invited speaker at the ACM India Annual Event.

ESA/ALGO 2019 will be organized by Susanne Albers and her group.

May 2019: Susanne Albers is invited speaker at the symposium 50 Years Informatics

July 2019: Susanne Albers is invited speaker at SIROCCO 2019, Italy.

December 2017: Susanne Albers will give keynote address at the Graduation Day, Department of Computer Science at RWTH Aachen University.

April 2017: New Research Training Center AdONE, funded by the German Research Foundation.

Susanne Albers receives ERC Advanced Grant. Press release of the Bavarian State Ministry of the Sciences, Research and the Arts.

August 2016: Susanne Albers is keynote speaker at Euro-Par 2016, Grenoble.

Susanne Albers, Nicole Megow and Andreas S. Schulz will organize MAPSP 2017.

Juni 2016: Susanne Albers gives an invited lecture at the Academy of Sciences and Literature, Mainz.

September 2015: Susanne Albers is invited speaker at MPI-INF – 25th Anniversary. The program features several Turing Award winners, Leibniz Prize winners, Humboldt Prize winners and ERC Grant winners.

June 2015: Susanne Albers is keynote speaker at the 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.

June 2015: Susanne Albers is invited speaker of the tutorial on Network Creation Games: How Does the Internet Form? organized by Erik D. Demaine (MIT) and MohammadTaghi Hajiaghayi (University of Maryland). 16th Conference on Electronic Commerce (EC15), Portland, Oregon.

Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail
News