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, F1.110
• Tutorials (start in the third week of the semester):
  - Group 1: Wed, 16:15-17:45, F2.211
  - Group 2: Fri, 14:15-15:45, F2.211

Lecture recordings from last year will be made available in PANDA to simplify attendance for those who cannot join the lectures in person.

Exams:

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: 25.02.2022, 9-11 am, C2

2nd Exam: 29.03.2022, 9-11 am, L1.201

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.