Module Description

Module: Efficient Algorithms

Courses:

TitleTypeHrs/WeekPeriod
Efficient AlgorithmsLecture2Winter Semester
Efficient AlgorithmsRecitation Section (small)2Winter Semester

Module Responsibility:

Prof. Siegfried Rump

Admission Requirements:

None

Recommended Previous Knowledge:

Programming in Matlab and/or C

Basic knowledge in discrete mathematics

Educational Objectives:

Professional Competence

Theoretical Knowledge

The students are able to explain the basic theory and methods of network algorithms and in particular their data structures. They are able to analyze the computational behavior and computing time of linear programming algorithms as well network algorithms. Moreover the students can distinguish between efficiently solvable and NP-hard problems.

Capabilities

The students are able to analyze complex tasks and can determine possibilities to transform them into networking algorithms. In particular they can efficiently implement basic algorithms and data structures of LP- and network algorithms and identify possible weaknesses. They are able to distinguish between different efficient data structures and are able to use them appropriately.

Personal Competence

Social Competence

The students have the skills to solve problems together in small groups and to present the achieved results in an appropriate manner.

Autonomy

The students are able to retrieve necessary informations from the given literature and to combine them with the topics of the lecture. Throughout the lecture they can check their abilities and knowledge on the basis of given exercises and test questions providing an aid to optimize their learning process.

ECTS-Credit Points Module:

6 ECTS

Examination:

Oral exam

Workload in Hours:

Independent Study Time: 124, Study Time in Lecture: 56


Course: Efficient Algorithms

Lecturer:

Siegfried Rump

Language:

German

Period:

Winter Semester

Content:

- Linear Programming

- Data structures

- Leftist heaps

- Minimum spanning tree

- Shortest path

- Maximum flow

- NP-hard problems via max-cut

Literature:

R. E. Tarjan: Data Structures and Network Algorithms. CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.

Wesley, 2011 http://algs4.cs.princeton.edu/home/

V. Chvátal, ``Linear Programming'', Freeman, New York, 1983.<

Back to Overview