Dynamic Programming

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

Algorithms
 glossary
 Dynamic P'
  Edit dist'
  Hirschberg's
 Graphs

Dynamic Programming refers to a very large class of algorithms. The idea is to break a large problem down (if possible) into incremental steps so that, at any given stage, optimal solutions are known to sub-problems. When the technique is applicable, this condition can be extended incrementally without having to alter previously computed optimal solutions to subproblems. Eventually the condition applies to all of the data and, if the formulation is correct, this together with the fact that nothing remains untreated gives the desired answer to the complete problem.

It is often the case in D.P. that the intermediate desirable condition implies more than seems to be strictly needed for the final answer. For example, the linear-time Fibonacci function, recursive or iterative, could be said to be a DPA. It holds (at least) two values, fib(i-1) and fib(i). When `i' gets to `n', only one of these values is needed, fib(i)=fib(n). However it is possession of the two values that allows the linear-time algorithm.

Examples of dynamic programming include

  • [edit-distance], longest common subsequence, spelling correction, and similar problems on strings; also Hirschberg's space-efficient [version], a functional programming [version] and
    a longest common subsequence (LCS) (LCSS), algorithm using bit operations for speed-up [HTML],
  • shortest path algorithms on [graphs],
  • [segmentation] of a time series,
  • some [spanning-tree] algorithms.


L.A., Department of Computer Sci. University of Western Australia 1984-1986, Department of Computer Sci. Monash University 1986, and (HTML) School of Comp Sci & SWE, Monash University 1999
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Tuesday, 19-Mar-2024 19:11:16 AEDT.