LTI
LTI

Advanced Algorithms

Course

  • Lecturer:
    Prof. Dr. Susanne Albers
  • Module:
    IN2360, TUMonline
  • Area:
    3+2 SWS in the area Informatik III (Theoretical Computer Science)
  • Time and Location:
    The course will be held online using recorded lecture, which will be released each week.
  • Exercises:
    The exercises will be held as online sessions on Monday at 2pm (14:00).
    The first session is on November 16, 2020.
    Teaching Assistants: Dr. Waldo Galvez, Sebastian Schubert
  • Audience:
    Graduate students of computer science
    Students with computer science as minor
  • ECTS: 6 Points
  • Prerequisites:
    1st and 2nd year courses
  • Exam:
    On-site exam, date TBA
Content

The modul covers fundamental and classical results in the area of advanced algorithms. Specifically, the course focuses on basic algorithm design and analysis principles. It addresses greedy approaches, divide and conquer, dynamic programming, randomization and amortization. These techniques are applied to develop solutions to cornerstone algorithmic problems.

Divide and Conquer: Introduction: deterministic Quicksort. Geometric divide and conquer: closest pair problem; line segment intersection; Voronoi diagrams. Fast Fourier Transform (FFT).

Randomized Algorithms: Las Vegas and Monte Carlo algorithms. Randomized Quicksort. Randomized primality test with applications to public-key cryptosystems. Verifying matrix multiplication.

Data Structures: Treaps – randomized search trees. Suffix trees.

Amortized Analysis: Dynamic tables. Fibonacci heaps.

Greedy Algorithms: Introduction. Interval scheduling. Scheduling to minimize lateness. Shortest paths in a graph.

Dynamic Programming: Introduction: weighted interval scheduling. Matrix-chain multiplication. Construction of optimal search trees. Segmented least squares. Subset sums and knapsacks.

Graph Algorithms: Computation of minimum cuts. Maximum-flow problem.

Further Topics: Median Computation. The probabilistic method.


Slides


Literature

  • Th. Cormen, C. Leiserson, R. Rivest and C. Stein. Introduction to Algorithms. Third Edition, MIT Press, 2009.
  • J. Kleinberg and E. Tardos. Algorithm Design. Pearson. Addison Wesley, 2006.
  • M. Mitzenmacher and E. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Second Edition, Cambridge University Press, 2017.
  • Th. Ottmann und P. Widmayer. Algorithmen und Datenstrukturen. 6. Auflage, Springer Verlag, 2017.

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