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.