392108 Dynamic Programming (V) (SoSe 2002)

Dynamic Programming is concerned with the optimization problems defined over search spaces of exponential size, yet allowing exact solution in polynomial space and time. It is on of the earliest computational paradigms, in fact developed by mathematicians before the term computer science had been established. Interest in dynamic programming has increased dramatically, as manyfold problems arising in biosequence analysis lend themselves to dynamic programming solutions. Still, the successful construction of a dynamic programming algorithm is a matter of experience, talent and luck.

The lecture will introduce dynamic programming using classical examples from biosequence analysis. It will then introduce the recent algebraic method of dynamic programming, which increases programming productivity by an order of magnitude.

Requirements for participation, required level

This lecture will be given in English.

Bibliography

• Richard Bellman: Dynamic Programming, Princeton University Press, 1975
• Dan Gusfield: Algorithms on strings, trees and sequences, Cambridge University Press, 1997
• Durbin, Eddy, Krogh, Mitchell: Biological Sequence Analysis, Cambridge University Press, 1998

External comments page

http://www.TechFak.Uni-Bielefeld.DE/ags/pi/lehre/S02.html#392108