Module: Efficient Algorithms
|Efficient Algorithms||Lecture||2||Winter Semester|
|Efficient Algorithms||Recitation Section (small)||2||Winter Semester|
Prof. Siegfried Rump
Recommended Previous Knowledge:
Programming in Matlab and/or C
Basic knowledge in discrete mathematics
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.
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.
The students have the skills to solve problems together in small groups and to present the achieved results in an appropriate manner.
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:
Workload in Hours:
Independent Study Time: 124, Study Time in Lecture: 56
Course: Efficient Algorithms
- Linear Programming
- Data structures
- Leftist heaps
- Minimum spanning tree
- Shortest path
- Maximum flow
- NP-hard problems via max-cut
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.<