Running dynamic programming algorithms on a DNA computer

Authors: 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