Running dynamic programming algorithms on a DNA computerAuthors: E. Baum and D. Boneh
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.
In proceedings of the 2nd annual conference on DNA computing, 1996
Full paper: gzipped-PostScript