Discrete Mathematics for Bioinformatics WS 07/08, G. W. Klau, 18.
Oktober 2007, 13:36 1
Discrete Mathematics for Bioinformatics (P1)
Lecture & Tutorials (4 + 2)
Winter 2007/08, FU Berlin
Dr. Gunnar Klau
gunnar <AT> [Link]-berlin dot de
Web page at [Link]
Organizational issues
Lecture and slides will be in English.
Credits. The slides are mostly taken 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.
• For all current information please check frequently [Link]
~gunnar/teaching/WS0708/[Link].
Lectures
Lectures take place
• Tuesdays from 10-12 am in SR 006 (Takustraße 9)
• Thursdays from 10-12 am in SR 032 (Arnimallee 6)
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 (2)
Discrete Mathematics for Bioinformatics (P1), G. W. Klau, 18. Oktober 2007, 13:36 2
Exercises will be held once weekly in room SR 119 (Fridays from 10-12 am).
First meeting: Friday, 26 Oct 2007
Office hours
Gunnar Klau: Thu, 16:30-17:30 + open door
Abdelhalim Larhlimi: open door
Content
The schedule is copied from last year. I will try to stick to this plan, but some changes may occur.
1. Linear Programming
(a) (L1, 16 Oct) Optimization problems
(b) (L2, 18 Oct) Polyhedra
(c) (L3, 23 Oct) Simplex Algorithm
(d) (L4, 25 Oct) Duality
2. Combinatorial Optimization
(a) (L5, 30 Oct) Branch-and-Cut (Intro)
(b) (L6, 1 Nov) B&C for sequence alignment (Modelling)
(c) (L7, 6 Nov) B&C for sequence alignment (Algorithms)
(d) (L8, 8 Nov) B&C for sequence alignment II
(e) (L9, 13 Nov) B&C for RNA alignment
(f) (L10, 15 Nov) Lagrangian Relaxation for RNA alignment
(g) (L11, 20 Nov) Constraint programming I
(h) (L12, 22 Nov) Constraint programming II
(i) (L13, 27 Nov) Local search and metaheuristics I
(j) (L14, 29 Nov) Local search and metaheuristics II
3. Graph algorithms
(a) (L15, 4 Dec) Overview and rehearsal (DFS, BFS, Dijsktra, Topsort, Spanning trees)
(b) (L16, 6 Dec) Shortest Path (A*,Floyd-Warshall)
(c) (L17, 11 Dec) Network flow
(d) (L18, 13 Dec) Bipartite Matching
Discrete Mathematics for Bioinformatics (P1), G. W. Klau, 18. Oktober 2007, 13:36 3
4. Data structures and analysis methods
(a) (L19, 18 Dec) Hashing
(b) (L20, 20 Dec) Hashing II
(c) (L21, 8 Jan) Random search trees/skiplists (KR)
(d) (L22, 10 Jan) Randomized analysis, Chernoff bounds I (KR)
(e) (L23, 15 Jan) Randomized analysis, Chernoff bounds II
(f) (L24, 17 Jan) ≈ Review 2
(g) (L25, 22 Jan) Locality sensitive hashing and applications
(h) (L26, 24 Jan) Tree decompositions and applications I
(i) (L27, 29 Jan) Tree decompositions and applications II
5. Complexity, Approximation, and Online-Algorithms
(a) (L28, 31 Jan) Complexity I
(b) (L29, 5 Feb) Complexity II
(c) (L30, 7 Feb) Approximation and online algorithms I
(d) (L31, 12 Feb) Approximation and online algorithms II (AB)
6. (L32, 15 Feb) Written examination
Discrete mathematics
What is discrete mathematics? (discrete, from lat. discernere, to discern, to separate)
From [Link]
Discrete mathematics is the branch of mathematics dealing with objects that can assume only distinct,
separated values. The term “discrete mathematics” is therefore used in contrast with “continuous
mathematics”, which is the branch of mathematics dealing with objects that can vary smoothly (and which
includes, for example, calculus). Whereas discrete objects can often be characterized by integers, continuous
objects require real numbers.
The study of how discrete objects combine with one another and the probabilities of various outcomes is
known as combinatorics. Other fields of mathematics that are considered to be part of discrete mathematics
include graph theory and the theory of computation. Topics in number theory such as congruences and
recurrence relations are also considered part of discrete mathematics.
The study of topics in discrete mathematics usually includes the study of algorithms, their implementations,
and efficiencies. Discrete mathematics is the mathematical language of computer science, and as such, its
importance has increased dramatically in recent decades.
Why is it important in bioinformatics?