Skip to main content
WueCampus
  • Nützliche Links
    Veranstaltungssuche
    Rechenzentrum
    Häufige Fragen
    Lehre Digital
    Forschung Digital
    Lecture - Videoupload
    CaseTrain
    Toolbox
  • More
English ‎(en)‎
Català ‎(ca)‎ Deutsch ‎(de)‎ Deutsch (du) ‎(de_du)‎ English ‎(en)‎ Español - Internacional ‎(es)‎ Français ‎(fr)‎ Italiano ‎(it)‎ Português - Portugal ‎(pt)‎ Svenska ‎(sv)‎ Türkçe ‎(tr)‎ Русский ‎(ru)‎ العربية ‎(ar)‎
You are currently using guest access
Log in
WueCampus
Nützliche Links Collapse Expand
Veranstaltungssuche Rechenzentrum Häufige Fragen Lehre Digital Forschung Digital Lecture - Videoupload CaseTrain Toolbox
Expand all Collapse all
  1. Home
  2. Wintersemester 2020/2021
  3. Master- und Aufbaustudiengänge
  4. Resources
 

Kursinformationen

 Kursbeschreibung

This course provides an overview of the different subject areas within algorithms, including a sampling of material on exact, approximation, geometric, and randomized algorithms and on advanced data structures. As such, the course is the basis of the corresponding master-level courses. The course covers improvements on classical algorithms as well as ways to approach NP-hard problems. These approaches range from understanding "good" algorithms to solve the problem exactly to efficient algorithms that solve the problem approximately, and also to randomized approaches which perform well in expectation. Along the way we will see some interesting data structures that can be leveraged. By the end of this course participants should have a broad overview of advanced topics concerning algorithms (i.e., regarding exact, approximate, geometric, and randomized computations) as well as some advanced data structures. They should be able to analyze and design algorithms of each type and understand the appropriate use of the data structures.

 Lehrende

Oksana Firman
Jonathan Klawitter
BK
Boris Klemz
Alexander Wolff
JZ
Johannes Zink

|

WS20: Advanced Algorithms

Section Name Description
Themen und Vorlesungen File Lecture #0: Intro
File Lecture video #0: Intro
File Lecture #1: The push-relabel algorithm for the maximum flow problem
File Lecture #1: The push-relabel algorithm for the maximum flow problem (long)
File Lecture #2: Exact algorithms
File Lecture #2: Exact algorithms (long)
File Lecture #3: Approximation Algorithms
File Lecture #3: Approximation Algorithms (long)
File Lecture #4: Quadratic Program for MaxCut
File Lecture #4: Quadratic Program for MaxCut (long)
File Lecture #6: Rearrangemnet distance of phylogenetic trees
File Lecture #6: Rearrangemnet distance of phylogenetic trees (long)
File Lecture #8: Online Algorithms
File Lecture #8: Online Algorithms (long)
File Lecture #9: Succinct data structures
File Lecture #9: Succinct data structures (long)
File Lecture #10: Optimal Binary Search Trees and Splay Trees
File Lecture #10: Optimal Binary Search Trees and Splay Trees (long)
Übungen und Übungsblätter File LaTeX Template for exercise submissions
Literatur und zusätzliche Materialien URL [Goldberg, Tarjan '88] A new approach to the maximum-flow problem
URL [Mann '17] The Top Eight Misconceptions about NP-Hardness
URL [GW '95] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
URL [BS '05] On the computational complexity of the rooted subtree prune and regraft distance
URL [RSW '06] The maximum agreement forest problem: Approximation algorithms and computational experiments
URL [Jacobson '89] Space-efficient static trees and graphs

Impressum | Datenschutzerklärung - WueCampus |  Erklärung zur Barrierefreiheit | Kontakt | Bildnachweise

Navigationsleiste - WueStudy: University icons created by justicon - Flaticon
Navigationsleiste - Rechenzentrum: Data center icons created by Eucalyp - Flaticon
Navigationsleiste - Website Support: Consultant icons created by Vitaly Gorbachev - Flaticon
Navigationsleiste - Häufige Fragen: Files and folders icons created by Freepik - Flaticon
Navigationsleiste - Lehre Digital: Training icons created by vectorspoint - Flaticon
Navigationsleiste - Forschung Digital: Research icons created by Eucalyp - Flaticon
Navigationsleiste - Lecture: Video icons created by Freepik - Flaticon
Navigationsleiste - Toolbox: Toolbox icons created by Freepik - Flaticon
Werbefeld 2 - WueLogin: Login icons created by Freepik - Flaticon
Werbefeld 3 - Upgrade WueCampus 4.4: Update icons created by Freepik - Flaticon