Module Theory of efficient algorithms, Computer Science (Master) (ER 7)
The module deals with the design of efficient algorithms in theory and practice. Students learn proof techniques for graph-theoretical problems in order to show the correctness of algorithms with exact logical conclusions. To the end, they analyze runtimes of procedures and apply suitable analysis techniques. Using the example of numerical problems such as the interpolation and approximation of mathematical models, students also independently design solution methods and then implement them.
The iteration methods are implemented by the students for specific technical problems and parallelized for use on modern high-performance computers.
After completing the module, students will be able to analyze and evaluate algorithms theoretically, but also to apply modeling and simulation methods for the computer-aided design of process sequences in practice.
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.