Assignment 1, due Sept. 28, 2005

READ: G. E. Moore, "Cramming more components onto integrated circuits", Electronics, vol. 38, no. 8, April 19, 1965. (home page: reading/moore65)

OPTIONAL READING: The dated but classic R. W. Keyes, "Miniaturization of Electronics and its Limits", IBM J. Res. Develop., vol. 32, pp. 24-28, 1988. (home page: reading/moore88)

ADVANCED READING, FOR THE BRAVE: Read and report on what is usually considered the second paper on DNA computing, R. J. Lipton's 1995 article in Science: R. J. Lipton, "DNA solution of hard computational problems", Science, vol. 268, pp. 542-545, April 28, 1995. (Science is online at our library's stupendous e-journal link: click here. Learn to use it if you haven't already.)

---

Problems

1. Estimate the area of a DVD disc, and from that, the number of bytes per pinhead. First guess, and then see how good your guess is. How close is today's DVD to Feynman's (home page: reading/feynman59) proposal to store the Encyclopedia Brittanica on the head of a pin? Use Feynman's estimate from (home page: reading/feynman59) "The head of a pin is a sixteenth of an inch across."

2. Consider the problem of finding a particular name in a phone book that is in alphabetical order. Starting at the beginning and examining every entry can take, in the worst case, n steps, where n is the number of names in the phone book. Describe an algorithm that takes fewer steps in the worst case. Does your algorithm resemble the one you use yourself when you look up a name in the phone book? (Or is there any such thing anymore as a phone book?)

3. Can you find the asymptotic time complexity of the algorithm you devised in the previous question? That is, if it isn't O(n), what is it?

4. Try to find an efficient algorithm for solving the any-path problem. Can you find one that takes time O(E+V), where E is the number of edges, and V is the number of vertices?

5. (a) Explain how Adleman's DNA computation that searches for a Hamilton path can be adapted to search for any path from a given vertex to another given vertex.

(b) A Hamilton cycle is a sequence of arcs in a graph that forms a single closed circuit and passes through every vertex exactly once. Repeat part (a) to find a DNA computation that searches for a Hamilton cycle.