Lecturer
News
11.02.2009: A group for this lecture called colab-spring-2009 has been created. If you participate in the course, please join this group.
Description
This course is a combination of theory and practice in the intersection of Mathematics and Computer Science. That is, there will be alternating theoretical lectures and sessions in the lab. The lectures will cover classical problems in Combinatorial Optimization (correctness proofs and analysis of combinatorial algorithms). There will be theoretical exercises to recapitulate, contemplate, and prepare for the implementation of the learned algorithms. The lab sessions will be a mix of supervised self-study and group discussion. The students will learn the foundations of Algorithm Library Design by collaboratively developping a software toolbox for combinatorial optimization problems. Moreover, the principles of Algorithm Engineering will be taught and they will tie together the theoretical and practical part of this course. The connection between polyhedra and efficiency will be emphasized as well as their relation in practice. A further objective is to enhance the mathematical modeling skills of the students to enable them to recognize and exploit combinatorial optimization problems in broader contexts.
Topics
Graphs and their representations
Paths and Trees (Connectivity, Shortest Path, Minimum Spanning Tree)
Cycles and Flows (Negative Cycles, Minimum Mean Cycles, Max Flow, Min Cost Network Flow)
Matchings (Bipartite, Non-bipartite if time permits)
Prerequisites
Basic knowledge in Linear Programming will be required as well as knowledge of C++. The number of participants is limited to 15. If there is a higher demand, an entry test on the prerequisites will be held for qualification.
Examination
The examination for this course is distributed over the lab sessions during the semester. That is, the students will receive assignment sheets with theoretical and practical exercises that will be due after the first hour of the lab session. Theses sheets are published several days in advance such that the students are able to prepare themselves at home. The certificate is granted for those who achieve more than 50 percent of the total points over the semester. A student with more than 25 percent of the total points qualifies for an oral make-up exam. If a graded certificate is desired, the mark will be computed by the following formula: m = 0.5 * ceil( 10*p + 2 ) where p is the ratio of achieved points and total points and ceil rounds up to the next integer. If the make-up exam is taken, then the mark of this oral exam counts.
Credits
Time and Date
Tuesdays 10h – 12h in MA B1 486 (lab session)
Thursdays 10h – 12h in MA 10 (lecture)