Discrete Mathematics for Bioinformatics

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.

Homework Assignment Date Due
A1 26 Oct 2007
A2 02 Nov 2007
A3 09 Nov 2007
A4, Graph, Laptops, ZIB Optimization Suite 16 Nov 2007
A5, porta_example.poi 23 Nov 2007
A6 07 Dec 2007
Solutions to the first review, Results 30 Nov 2007
A7 14 Dec 2007
Linear Algebra  
A8 21 Dec 2007
A9 18 Jan 2008
A10 01 Feb 2008
A11 08 Feb 2008
Second Review Results 28 Jan 2007

Exams

Main exam (14 Feb 2008) 14 Feb 2008, 15:29

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

This topic: Main > GunnarKlau > GunnarKlauP1winter0708
Topic revision: 19 Jun 2008, GunnarKlau
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback