Page 11 - Krész, Miklós, and Andrej Brodnik (eds.). MATCOS-13. Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science. Koper: University of Primorska Press, 2016.
P. 11
find blocks, then decide to use either X or G, whichever
has fewer blocks. However, in most dynamic programming
applications, the minimum computation that we study is
used as a subroutine. In these cases, X changes between
calls to the subroutine, whereas G remains static. Hence,
it makes sense to analyze G, especially since it tends to
be a particular mathematical function. However, working
on X would have its merits if one could show that, for a
given application, the number of blocks B in X between
subroutine calls can be bounded by some value.
Similar techniques could perhaps be applied to other dy-
namic programming algorithms that operate on the (min, +)
semi-ring. One notable example is (min, +) matrix multipli-
cation.
5. REFERENCES
[1] Z. Galil and R. Giancarlo. Speeding up dynamic
programming with applications to molecular biology.
Theoretical Computer Science, 64(1):107 – 118, 1989.
[2] D. S. Hirschberg and L. L. Larmore. The least weight
subsequence problem. In Proceedings of the 26th
Annual Symposium on Foundations of Computer
Science, SFCS ’85, pages 137–143, Washington, DC,
USA, 1985. IEEE Computer Society.
[3] D. Sankoff and J. B. Kruskal. Time warps, string edits,
and macromolecules. Cambridge University Press,
Cambridge, England, 2000.
[4] M. S. W. T. F. Smith. New stratigraphic correlation
techniques. Journal of Geology, (88):451 – 457, 1980.
[5] F. F. Yao. Speed-up in dynamic programming. SIAM J.
on Alg. Discr. Meth., (3):532 – 540, 1982.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 11
Koper, Slovenia, 10-11 October
has fewer blocks. However, in most dynamic programming
applications, the minimum computation that we study is
used as a subroutine. In these cases, X changes between
calls to the subroutine, whereas G remains static. Hence,
it makes sense to analyze G, especially since it tends to
be a particular mathematical function. However, working
on X would have its merits if one could show that, for a
given application, the number of blocks B in X between
subroutine calls can be bounded by some value.
Similar techniques could perhaps be applied to other dy-
namic programming algorithms that operate on the (min, +)
semi-ring. One notable example is (min, +) matrix multipli-
cation.
5. REFERENCES
[1] Z. Galil and R. Giancarlo. Speeding up dynamic
programming with applications to molecular biology.
Theoretical Computer Science, 64(1):107 – 118, 1989.
[2] D. S. Hirschberg and L. L. Larmore. The least weight
subsequence problem. In Proceedings of the 26th
Annual Symposium on Foundations of Computer
Science, SFCS ’85, pages 137–143, Washington, DC,
USA, 1985. IEEE Computer Society.
[3] D. Sankoff and J. B. Kruskal. Time warps, string edits,
and macromolecules. Cambridge University Press,
Cambridge, England, 2000.
[4] M. S. W. T. F. Smith. New stratigraphic correlation
techniques. Journal of Geology, (88):451 – 457, 1980.
[5] F. F. Yao. Speed-up in dynamic programming. SIAM J.
on Alg. Discr. Meth., (3):532 – 540, 1982.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 11
Koper, Slovenia, 10-11 October
