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: Thu, 13:15 -15:45, F2.211
- Tutorial: Wed 11:15-12:45, F1.110 (starts in the third week of the semester)
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: 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 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.