Web page for the course
Discrete Mathematics for Bioinformatics held in winter 2007/2008 at Freie Universität Berlin. The main page is located at
http://www.math.fu-berlin.de/~gunnar/teaching/WS0708/P1.html.
The course is divided into a lecture part (4h/week), given by
Dr. Gunnar Klau, and a tutorial part (2h/week), given by
Abdelhalim Larhlimi.
Important dates
| First lecture |
16 Oct 2007 |
| First review |
30 Nov 2007 |
| Second review |
25 Jan 2008 |
| Final written examination |
14 Feb 2008, 9:59-12 am |
| großer Physiologie-Hörsaal (Arnimallee 22) |
| results |
| Nachklausur |
17 Apr 2008, 9:59-12 am |
| Hörsaal B d. Physik R. 0.1.01 |
| results |
Time, date, and place
| Lecture |
Tue, 10-12 am |
SR 006 (Takustraße 9) |
| |
Thu, 10-12 am |
SR 032 (Arnimallee 6) |
| Tutorial |
Fri, 10-12 am |
SR 032 (Arnimallee 6) |
The lecture starts on Tue, 16 Oct 2007. Tutorials start on Fri, 26 Oct, the first assignments will be handed out one week before.
Contents
From the study regulations (the coloured part indicates roughly where we are):
- Introduction to linear programming and the Simplex algorithm
- Duality
- Integer linear programming and combinatorial optimization
- Cutting planes and Lagrangian relaxation
- Constraint programming
- Local search and metaheuristics
- Advanced graph algorithms
- Analysis of randomized data structures and algorithms
- Hashing
Organizational issues
- Lecture and slides will be in English.
- Credits. Many of the slides are from last year's lecture given by Prof. Alexander Bockmayr and Prof. Knut Reinert and include some slides by Prof. Daniel Huson (Tübingen)
- Please note the following:
- You can download all slides (also in script form) typically the day after the lecture. It is not necessary to copy the slides.
- However, the slides are not a complete script. Please take notes and maybe copy things on the blackboard.
- Exercises will be held by Abdelhalim Larhlimi.
- Important: Rules for active participation (tutorials)
- presence is absolutely required
- active participation (blackboard) in the tutorials
- half of the points in the reviews
- The final grade only depends on the exam. But you must have actively participated in order to be admitted to the exam.
- Every participant is now registered at the KVV page.
Slides
Slides will be available for download here. Mostly, this will happen after the lecture. However, last year's lecture slides (see Sect. Links) will often be a good basis for preparation.
| Description |
Slides |
condensed PDF |
date put here |
| Organizational issues, intro |
discMath_klau_intro.pdf |
discMath_klau_script_intro.pdf |
18 Oct 2007, 13:40 |
| Linear Programming, part I |
discMath_klau_linProg_I |
discMath_klau_script_linProg_I.pdf |
18 Oct 2007, 13:51 |
| Linear Programming, part II |
discMath_klau_linProg_II |
discMath_klau_script_linProg_II.pdf |
23 Oct 2007, 12:22 |
| Linear Programming (+ duality), part III |
discMath_klau_linProg_III |
discMath_klau_script_linProg_III.pdf |
25 Oct 2007, 15:28 |
| Linear Programming (+ duality), part IV |
discMath_klau_linProg_IV |
discMath_klau_script_linProg_IV.pdf |
31 Oct 2007, 09:33 |
| Combinatorial Optimization, part I |
discMath_klau_combOpt_I |
discMath_klau_combOpt_I.pdf |
6 Nov 2007, 12:22 |
| Combinatorial Optimization, part II |
discMath_klau_combOpt_II |
discMath_klau_combOpt_II.pdf |
14 Nov 2007, 10:56 |
| Combinatorial Optimization, part III |
discMath_klau_combOpt_III |
discMath_klau_combOpt_III.pdf |
15 Nov 2007, 16:32 |
| Solving ILPs, part I |
discMath_klau_ILP_I |
discMath_klau_ILP_I.pdf |
21 Nov 2007, 10:54 |
| Vienna slides (b&b) |
Powerpoint |
PDF |
21 Nov 2007, 11:37 |
| Solving ILPs, part II |
discMath_klau_ILP_II |
discMath_klau_ILP_II.pdf |
23 Nov 2007, 16:20 |
| Constraint Programming |
discMath_klau_CP |
discMath_klau_CP.pdf |
5 Dec 2007, 12:10 |
| Lagrangian Relaxation I (theory) |
discMath_klau_lag_I |
discMath_klau_lag_I.pdf |
18 Dec 2007, 14:24 |
| Lagrangian Relaxation I (practice) |
lara.pdf.gz |
|
4 Jan 2008, 11:31 |
| Skiplists |
discMath_klau_skiplists |
discMath_klau_skiplists.pdf |
14 Jan 2008, 16:23 |
| Maximum flow |
discMath_klau_maxflow |
discMath_klau_maxflow.pdf |
23 Jan 2008, 17:45 |
| Local search and Metaheuristics |
discMath_klau_meta |
discMath_klau_meta.pdf |
31 Jan 2008, 12:05 |
| Hashing I |
discMath_klau_hash_I |
discMath_klau_hash_I.pdf |
5 Feb 2008, 12:16 |
| Hashing II |
discMath_klau_hash_II |
discMath_klau_hash_II.pdf |
9 Feb 2008, 13:06 |
Exercises
- The exercises are mandatory and will be counted as active participation in the new three column model of the FU Berlin.
- Active participation = presence + reviews + some blackboard action.
- There will also be some practical exercices (programming).
- Reviews: 2 × 60 min (end-November, mid-January)
- Exercises will be available for download here.
Exams
Literature
Books
- Linear Programming
- V. Chvátal, Linear Programming, Freeman 1983
- D. Bertsimas, J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
- Walpole, Myers: Probability and Statistics for Engineers and Scientists.
- Algorithms
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press
Links and web resources
- last year's lecture page
- Linear Programming
- Combinatorial Optimization and Integer Linear Programming
- Chernoff bounds und moment-generating functions
- Metaheuristics