Lecturer: Prof. Dr. Christian Scheideler

Language: English

Module information:

• Module II.2.1 (MuA)
• 3V + 2Ü SWS
• 6 ECTS Credits

Time and Location:

• Lecture: Thu, 8:15 -10:45, F2.211
• Tutorial: Thu 11:15-12:45, FU.511 (starts in the second week of the semester)

Exams:

To be admitted to the exams, at least 40% of the points on the exercise sheets must be achieved and a solution has to be presented at a tutorial. To be eligible for a bonus point (which would raise the grade by 0.3 if the exam is passed), at least 60% of the points must be achieved.

1st Exam: TBA

2nd Exam: TBA

Only a handwritten DIN A4 sheet (both sides can be used) will be allowed in the exam.

Contents:

The slides will be posted in Panda.

• Introduction
• Advanced Heaps
    - Binomial Heaps
    - Fibonacci Heaps
    - Radix Heaps
    - Applications
• Advanced Search Structures
    - Splay Trees
    - (a,b)-Trees
    - Applications
• Graph Algorithms
    - Shortest Paths Revisited
    - Matchings
• Network Flows
    - Ford-Fulkerson Algorithm
    - Preflow-Push Algorithm
    - Applications
• Linear Programming
  - Definitions
  - Applications
  - Duality Theory
  - Solving LPs
• String Matching
  - Knuth-Morris-Pratt Algorithm
  - Boyer-Moore Algorithm
  - Aho-Corasick Algorithm

Homework assignments:

• Will be posted in PANDA.

A new exercise sheet will be published every Thursday after the lecture, starting in the first week of the semester, and the solutions have to be submitted by Wednesday midnight of the following week. The solutions can be submitted by a team of up to 3 people and will be discussed in the tutorials.