Settings
Module Theory of efficient algorithms, Master Course Computer Science (ER 7)
Module summary

Theory of efficient algorithms

INFM110SE

Prof. Dr. Heiko Körner

7 ECTS points / 5 Contact hours

All semesters

none

none

The three courses in this module teach the design of efficient algorithms in theory and practice. By presenting numerous examples of numerical and graph theory problems, students will learn typical methods for their solution and also how to implement them. Techniques for proving the correctness of an algorithm will be presented. Also, methods for analysing their computational complexity will be given. Moreover, this module attaches importance to modeling and simulation methods. These algorithms are used in many areas of research and industry and enable a computer-assisted design of processes. Therefore, students are introduced to numerical algorithms for interpolation and approximation of mathematical models. The students will implement several corresponding technical problems with parallelized programs on modern high performance computers.

Written/verbal Exam 120/20 Min. (graded)
Course Graph Algorithms

INFM111SE.a

Lecture

Prof. Dr. Heiko Körner

German

3/2

Module exam

This couse gives an overview of some basic graph algorithms and their applications. The students learn to apply further algorithms and how to implement them. Furthermore, techniques for proving the correctness and complexity of algorithms are thoroughly studied.

After a brief theoretical introduction to graphs some fundamental algorithms like depth first search and breadth first search are presented. Other algorithms deal with the detection of strongly connected components, topological sorting and the calculation of shortest paths. Efficient tests concerning the existence of circuits in a graph are also discussed.

For this course some basic knowledge of programming and the safe handling of the O-calculus are necessary. Furthermore, the participant is assumed to be familiar with inductive proofs. Both topics are handled in an appendix of the lecture notes.

The substance of the lecture will be discussed at the blackboard. Lecture notes containing the complete material are also available. Lecture notes, exercises and their solutions are available online.

 

Literature: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2001, ISBN 0-262-03293-7.

Classical lecture. Several exercises deepen the field of study and are discussed in the classroom if desired.

Course Modeling and Simulation

INFM111SE.b

Lecture

Prof. Dr. Britta Nestler

German

2/2

Module exam

Course Modeling and Simulation Exercise

INFM112SE

Exercise

Prof. Dr. Britta Nestler

German

2/1

Exercise 1 Semester (not graded)