Running dynamic programming algorithms on a DNA computer
Authors: E. Baum and D. Boneh
Abstract:
We show that DNA computers are especially useful for
running algorithms which are based on dynamic programming. This class
of algorithms takes advantage of the large memory capacity of a DNA
computer. We present algorithms for solving certain instances of the
knapsack problem using a dynamic programming approach.
Unlike other algorithms
for DNA computers, which are brute force, dynamic programming
is the same approach one would use to solve (smaller) problems on a
conventional computer.
Reference:
In proceedings of the 2nd annual conference on DNA computing, 1996
Full paper: gzipped-PostScript