Module Theory of efficient algorithms, INFM (ER 6)Module Theory of efficient algorithms, Master Course Computer Science (ER 6)

Module summary
Module name:
Internal number:
Coordinator:
Extent:
Semester:
Pre-requisites with regard to content: none
Pre-requisites according to the examination regulations:
none
Competencies:

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.

Assessment:
Written Exam 90 Min. (graded)
Course: Graph Algorithms
Internal number: INFM111SE.a Type/mode: Lecture
Lecturer:
Prof. Dr. Heiko Körner
Language of instruction:
German
Credits (ECTS): 3 Contact hours: 2
Assessment: Module exam
Content:

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.

Recommended reading:

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.

Comments:

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

Course: Modeling and Simulation
Internal number: INFM111SE.b Type/mode: Lecture
Lecturer:
Prof. Dr. Britta Nestler
Language of instruction:
German
Credits (ECTS): 2 Contact hours: 2
Assessment: Module exam
Content:

Recommended reading:

Comments:

Course: Modeling and Simulation Exercise
Internal number: INFM112SE Type/mode: Exercise
Lecturer:
Prof. Dr. Britta Nestler
Language of instruction:
German
Credits (ECTS): 2 Contact hours: 1
Assessment: Exercise 1 Semester (not graded)
Content:
Recommended reading:
Comments: