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
Lecture 4 HPW, Exercises 4 HPW
10 CP
Learning results & Competences
After completing the first part the students can
- reproduce algorithmic and programming principles, and explain technical terms and basic methods,
- describe known algorithms and new algorithms based on pseudocode and Python code and apply them exemplarily to adequate problem settings,
- implement algorithms in Python and apply selected software engineering tools,
- distinguish between data structures (theoretically and in Python) and apply them in adequate contexts,
- interpret and visualise different types of data,
- analyse algorithms (e.g., compute and classify their running time) and prove their correctness,
- test their code and apply test driven development,
- evaluate code and apply refactoring techniques in order to improve code quality,
- operate a version control system and develop in groups,
- evaluate the quality of a given piece of code and provide reviews for improvement,
- create reproducible environments and build data science workflows, and
- design and develop algorithms based on known methods.
After completing the second part the students can:
- reproduce further algorithms, programming principles, and data structures,
- implement further algorithms in Python and apply selected software engineering tools,
- match algorithms to different algorithmic design paradigms and apply them exemplarily,
- adapt algorithms and data structures and transfer them to new contexts,
- design algorithms according to adequate design paradigms,
- classify and evaluate algorithms according to further analysis techniques, and
- classify algorithmic problems according to basic complexity classes.
Content
This course consists of two parts about algorithm design and programming. It provides an insight into algorithmic and programming tools, combining theoretical and practical methods that build a foundation for further courses in the Master of Articficial Intelligence and Data Science programme.
Winter term:
- Algorithmic foundations and data structures
- Introduction to the Python programming language
- Algorithm analysis (running time analysis, correctness proofs)
- Software engineering methods for code quality (software testing, code review, refactoring)
- Version control systems (e.g., git) and continuous integration
- Classic algorithms (e.g., sorting algorithms, graph algorithms) and data streams
- Selected packages (e.g., numpy, matplotlib, pandas)
- Data science workflows (e.g. snakemake), reproducible environments (e.g. docker)
Summer term:
- Algorithmic design principles (recursion, divide-and-conquer, dynamic programming, greedy algorithms) and their analysis
- Further application of Python programming and software development methods
- Further algorithms (e.g., sorting, search, graph algorithms, pattern matching)
- Further data structures (e.g., search trees, splay trees, B-trees, suffix trees, heaps, hashing)
- Object oriented programming
- Computational complexity (e.g., P vs. NP, NP-completeness)
Teaching
Lecture with (theoretical and practical) exercises
Prerequisites for attending
Formal: Admission to master studies in „Artificial Intelligence and Data Science“.
Contentual: none
Examination
Written examination after both courses about content of lectures and exercises
Prerequisites for receiving credit points
- Regular and active participation in the exercises
- Passing the examination
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
Lecture 4 HPW, Exercises 4 SWS
10 CP
Learning results & Competences
After completing the first part the students can
- reproduce algorithmic and programming principles, and explain technical terms and basic methods,
- describe known algorithms and new algorithms based on pseudocode and Python code and apply them exemplarily to adequate problem settings,
- implement algorithms in Python and apply selected software engineering tools,
- distinguish between data structures (theoretically and in Python) and apply them in adequate contexts,
- interpret and visualise different types of data,
- analyse algorithms (e.g., compute and classify their running time) and prove their correctness,
- test their code and apply test driven development,
- evaluate code and apply refactoring techniques in order to improve code quality,
- operate a version control system and develop in groups,
- evaluate the quality of a given piece of code and provide reviews for improvement,
- create reproducible environments and build data science workflows, and
- design and develop algorithms based on known methods.
After completing the second part the students can:
- reproduce further algorithms, programming principles, and data structures,
- implement further algorithms in Python and apply selected software engineering tools,
- match algorithms to different algorithmic design paradigms and apply them exemplarily,
- adapt algorithms and data structures and transfer them to new contexts,
- design algorithms according to adequate design paradigms,
- classify and evaluate algorithms according to further analysis techniques, and
- classify algorithmic problems according to basic complexity classes.
Content
This course consists of two parts about algorithm design and programming. It provides an insight into algorithmic and programming tools, combining theoretical and practical methods that build a foundation for further courses in the Master of Articficial Intelligence and Data Science programme.
Winter term:
- Algorithmic foundations and data structures
- Introduction to the Python programming language
- Algorithm analysis (running time analysis, correctness proofs)
- Software engineering methods for code quality (software testing, code review, refactoring)
- Version control systems (e.g., git) and continuous integration
- Classic algorithms (e.g., sorting algorithms, graph algorithms) and data streams
- Selected packages (e.g., numpy, matplotlib, pandas)
- Data science workflows (e.g. snakemake), reproducible environments (e.g. docker)
Summer term:
- Algorithmic design principles (recursion, divide-and-conquer, dynamic programming, greedy algorithms) and their analysis
- Further application of Python programming and software development methods
- Further algorithms (e.g., sorting, search, graph algorithms, pattern matching)
- Further data structures (e.g., search trees, splay trees, B-trees, suffix trees, heaps, hashing)
- Object oriented programming
- Computational complexity (e.g., P vs. NP, NP-completeness)
Teaching
Lecture with (theoretical and practical) exercises
Prerequisites for attending
Formal: Admission to master studies in „Artificial Intelligence and Data Science“.
Contentual: none
Examination
Written examination after both courses about content of lectures and exercises
Prerequisites for receiving credit points
- Regular and active participation in the exercises
- Passing the examination
Lecture 2 HPW, Tutorial 2 HPW
5 CP
Content
This course is a lecture on advanced algorithms and deals with randomization as a method of algorithm design and analysis. The goal is to obtain efficient algorithms via randomized decisions that run faster than their deterministic variants and at the same time provide precise results with high probability.
• models of randomized algorithms (Las-Vegas and Monte-Carlo algorithms)
• running time and accuracy analysis
• randomized approximation algorithms (e.g., for SAT and graph problems)
• methods for probability amplification
• randomized design paradigms (e.g., probabilistic method, fingerprints, hashing)
• randomization in data analysis
Learning Outcomes
After completing the course, students are able to
• describe technical terms and basic methods of randomization in algorithms,
• match algorithms to different design paradigms and apply them examplarily,
• analyse, evaluate and compare properties such as running time and accuracy and
• design first randomized algorithms according to adequate design methods.
Bibliography
• Juraj Hromkovi¬: Randomisierte Algorithmen: Methoden zum Entwurf von zufallsgesteuerten Systemen für Einsteiger. Teubner-Verlag. Wiesbaden, 2004. 1. Ausgabe
• Michael Mitzenmacher and Eli Upfal: Probability and Computing. Cambridge University Press. Cambridge, 2017. 2nd Edition.
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 Algorithms and Data Structures, Theoretical Computer Science and Mathematics for Computer Science 3
Conditions for awarding credit points
• actively participate in tutorials
• successfully work on exercises
• final exam (written or oral 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.