DNA Computing, 2002 version (solutions)

Feel free to work on the homework in groups. The work you hand in, however, should reflect your understanding of the material and be in your own words. Students who turn in identical (or close to identical) homework assignments will be asked to explain their answers orally to the TA or prof. A student who cannot explain how he or she arrived at a given answer will be charged with academic dishonesty.

You should justify all of your answers for full credit.

Dr. Giaever spoke about the traveling salesman problem and the related but simpler Hamiltonian path problem. The questions below should be answerable with only the information in the problem and/or the handout with the Scientific American article.

1. Explain why the traveling salesman problem is so difficult to compute.
The number of possibilities that needs to be examined grows exponentially. For problems of any size, it just takes too long.

2. Why did Prof. Giaever argue that DNA will not be used for real computers?
For a DNA computer, computing time does not increase exponentially, but the amount of material necessary does. For large problems, it would be impossible to gather enough DNA to guarantee a solution.

1.	Explain why the traveling salesman problem is so difficult to compute. The number of possibilities that needs to be examined grows exponentially. For problems of any size, it just takes too long.
2.	Why did Prof. Giaever argue that DNA will not be used for real computers? For a DNA computer, computing time does not increase exponentially, but the amount of material necessary does. For large problems, it would be impossible to gather enough DNA to guarantee a solution.