Fundamental Algorithms

Lecturer: Prof. Dr. Christian Scheideler

Language: English

Module information:

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

Time and Location:

• Lecture: Tue, 8:30 -11:00, via BBB, will be recorded
• Tutorials (start in the second week of the semester):
  - Group 1: Fri, 11:15-12:45, via BBB
  - Group 2: Fri, 14:15-15:45, via BBB
  Tutorials will not be recorded.

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

1st Exam: February 18, 2021, 4-6 pm, Audimax

2nd Exam: March 18, 2021, room: 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 Tuesday after the lecture, starting in the first week of the semester, and the solutions have to be submitted by Thursday 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.