Publications

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