Recurring courses
Usually in the summer semester
Lecture 2 HPW, Tutorial 2 HPW
5 CP
Content
This module covers basic knowledge from the following areas.
• searching in graphs
• topological sorting
• connectivity problems
• shortest path problems
• minimal spanning trees
• network flow problems
• matching problems
Learning Outcomes
After completing the course, students are able to
• describe and explain the discussed graph algorithms,
• allocate the discussed algorithms to different problem settings and apply them adequately,
• analyze the discussed algorithms with respect to their running time and correctness and
• design and analyze easy new graph algorithms.
Bibliography
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. De Gruyter Oldenbourg. 2017. 4. Auflage.
• Ravindra Ahuja, Thomas Magnanti, James B. Orlin: Network Flows: Theory, Algorithms and Applications. Prentice Hall. Englewood Cliffs, 1993. 1. Ausgabe
Module compatibility
• Elective Area Bachelor study programme PO 2021
• Elective Area and Major Subject Bachelor study programme PO 2013 and PO 2016
• Application subject Bachelor study programme Mathematics and Applied Fields
• Minor subject Bachelor study programme Physics
• Minor subject Bachelor study programme Medical Physics
Prerequisites
• Contentual: Contents of modules Programming, Algorithms and Data Structures and Mathematics for Computer Science 1
Conditions for awarding credit points
• actively participate in tutorials
• hand in exercises
• final written exam
Lecture 2 HPW, Tutorial 2 HPW
5 CP
Content
This course is an advanced algorithms lecture which introduces basic concepts from the area of approximation algorithms. Approximation algorithms are algorithms with a polynomial time bound for difficult optimization problems which satisfy a provable guarantee on the quality of the solution. The lecture
covers techniques for the design and analysis of approximation algorithms, in particular:
• greedy algorithms
• approximation algorithms for graph problems
• problems with Euclidean vs metric vs non-metric inputs
• (I)LP-based algorithms
• polynomial approximation schemes
Learning Outcomes
After completing the course, students are able to
• explain the concept ”approximation ratio”,
• formally define the discussed optimization problems,
• suitably summarize and explain complex proofs,
• apply basic techniques for the analysis of approximation ratios and
• apply basic design techniques for approximation algorithms.
Bibliography
• Vijay Vazirani: Approximation Algorithms. Springer-Verlag, Berlin, 2003. 1. Ausgabe
• David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, Cambridge, 2011, 1. Ausgabe.
Module compatibility
• Elective Area Theoretical Computer Science
• Major Subject
• Individual Supplement
• Application subject for Minor area Master study programme Mathematics
Prerequisites
• Formally: Bachelor’s students must meet the requirements for the anticipation of Master’s modules.
Conditions for awarding credit points
• Active participation in the exercises
• handing in the exercises
• passing the written exam at the end of the semester
Content
In this module, students should be able to carry out independent scientific Acquire work and prepare for the master’s thesis. The content therefore depends very much on the respective subject area and the areas of interest of the person.
Learning Outcomes
After completing the course, students are able to
• summarize and illustrate the important concepts of the subject area of the project or future master’s thesis
• identify important articles and books for specific problems in the field
• question concepts of the subject and decide which ones are suitable for a future master’s thesis
• describe and apply the scientific methods of the department
Bibliography
• In agreement with the supervisor.
Module compatibility
• Projektarbeit
Prerequisites
• None
Conditions for awarding credit points
• The specific requirements depend on the task to be processed. Therefore, the criteria for acquiring the credit points must be determined individually at the beginning of the project work.
3 CP
*: During the Master's thesis, students take part in the Final Seminar for Bachelor's students or the Oberseminar by arrangement.
Content
Within the framework of the graded final seminar, the subject and results of the Thesis are presented in front of the corresponding working group (or a merger of such) with subsequent scientific discussion.
Learning Outcomes
After participating in the final seminar, the students are able to
• present an independently developed topic in a talk
• to follow scientific talks of other graduates
• get involved in discussions about scientific presentations by others students
Module compatibility
• Bachelorarbeit
Prerequisites
The thesis must be registered.
Conditions for awarding credit points
Active participation in the final seminar and presentation of your own topic in an oral presentation with discussion.
The Oberseminar 'Algorithms and Data Structures' features lectures on current algorithmic topics presented by members of the chair and guests, as well as discussions on current research topics.
During the Master's thesis, students take part in the Final Seminar for Bachelor's students or the Oberseminar by arrangement.
Usually in the winter semester
Lecture 4 HPW, Tutorial 2 HPW, Projektseminar 6 HPW
10 CP
Content
This module showcases a selection of fundamental algorithms and data structures from theory and practice. By analyzing these basic algorithms and data structures, the lecture explains how resource consumption (running time and memory requirements) may be theoretically analyzed and predicted.
• Foundations of algorithms
• Models of computation and complexity measures
• Search strategies (binary search)
• Algorithms for sorting (quicksort, heapsort, merge sort, …)
• Fundamental data structures (array lists, linked lists, stacks, queues)
• Search trees (binary search trees, balanced trees)
• Dictionaries (open and closed hashing)
• Managing systems of sets (union find)
• Amortized analysis
• Algorithms on graphs (depth first search, breadth first search, spanning trees, shortest paths)
• Design patterns (greedy, divide-and-conquer, dynamic programming)
• Limits of efficient algorithms (outlook)
Learning Outcomes
After completing the course, students are able to
• apply, analyze and explain the algorithms/data structures discussed in this module,
• recognize a suitable algorithm/data structure for a given problem and to select one from a repertoire,
• develop a specification for an algorithm or a data structure based on an informal description, and to explain a given specification and answer questions on a given specification
• use the fundamental techniques from the lecture to analyze, to predict and to compare the resource consumption of algorithms and data structures
• prove and convince others that a given algorithm works correctly and
• modify and combine the algorithms and data structures presented in the module.
Bibliography
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. De Gruyter Oldenbourg. 2017. 4. Auflage.
• Robert Sedgewick, Kevin Wayne: Algorithmen. Pearson Studium. 2014. 4. Auflage.
• Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. Spektrum. 2012. 5. Auflage.
• Jon Kleinberg, Eva Tardos: Algorithm Design. Addison Wesley. 2006.
Module compatibility
• Compulsory Area Bachelor study programme PO 2021
• Compulsory Area Bachelor study programme PO 2016, 2013
• Application subject Bachelor study programme Mathematics and Applied Fields
• Minor subject Bachelor study programme Physics
• Minor subject Bachelor study programme Medical Physics
• Module CL6 Bachelor study programme Computer Linguistics
Prerequisites
• Contents of module Mathematics for Computer Science 1
Conditions for awarding credit points
• active participation in the tutorials
• handing in the homework
• written exam
Lecture 2 HPW, Tutorial 2 HPW
5 CP
Content
This course is a lecture on advanced algorithms and deals with clustering algorithms. In this lecture, we discuss combinatorial clustering problems and related algorithms. In particular, we discuss:
• hierarchical clustering
• algorithms for the k-center problem
• algorithms for the k-supplier problem
• similarity-based clustering procedures
Learning Outcomes
After completing the course, students are able to
• describe and develop combinatorical arguments,
• apply the discussed clustering algorithms,
• discuss and evaluate hierarchical clustering methods, and
• analyse clustering precedures.
Bibliography
• Selected publications regarding the topic of the course.
• Lecture Notes
Module compatibility
• Elective Area Bachelor study programme PO 2021
• Elective Area and Major Subject Bachelor study programme PO 2013 and PO 2016
• Application subject Bachelor study programme Mathematics and Applied Fields
• Minor subject Bachelor study programme Physics
• Minor subject Bachelor study programme Medical Physics
Prerequisites
• Contentual: Contents of module Mathematics for Computer Science 1
Conditions for awarding credit points
• actively participate in tutorials
• successfully work on exercises
• final exam
Content
In this module, students should be able to carry out independent scientific Acquire work and prepare for the master’s thesis. The content therefore depends very much on the respective subject area and the areas of interest of the person.
Learning Outcomes
After completing the course, students are able to
• summarize and illustrate the important concepts of the subject area of the project or future master’s thesis
• identify important articles and books for specific problems in the field
• question concepts of the subject and decide which ones are suitable for a future master’s thesis
• describe and apply the scientific methods of the department
Bibliography
• In agreement with the supervisor.
Module compatibility
• Projektarbeit
Prerequisites
• None
Conditions for awarding credit points
• The specific requirements depend on the task to be processed. Therefore, the criteria for acquiring the credit points must be determined individually at the beginning of the project work.
3 CP
*: During the Master's thesis, students take part in the Final Seminar for Bachelor's students or the Oberseminar by arrangement.
Content
Within the framework of the graded final seminar, the subject and results of the Thesis are presented in front of the corresponding working group (or a merger of such) with subsequent scientific discussion.
Learning Outcomes
After participating in the final seminar, the students are able to
• present an independently developed topic in a talk
• to follow scientific talks of other graduates
• get involved in discussions about scientific presentations by others students
Module compatibility
• Bachelorarbeit
Prerequisites
The thesis must be registered.
Conditions for awarding credit points
Active participation in the final seminar and presentation of your own topic in an oral presentation with discussion.
The Oberseminar 'Algorithms and Data Structures' features lectures on current algorithmic topics presented by members of the chair and guests, as well as discussions on current research topics.