Assignment 3, due Oct. 12, 2005

READ:
B. Yurke, A. P. Mills Jr., S. L. Cheng, "DNA implementation of addition in which the input strands are separate from the operator strands", BioSystems, vol. 52, 1999, pp. 165--174. (Link at course home page --> reading: click here; Dr. Yurke is our visitor next Wednesday.)

Note: Don't worry if you don't get all of this paper---after all, it is a recent technical paper in a scientific journal. You should get the main ideas, however, and then be able to follow the presentation. The paper uses some Boolean algebra, which we haven't gotten to yet in class because of the timing of Dr. Yurke's visit. I'll try to arrange a quick introduction to Boolean algebra at the beginning of the class, by either Dr. Yurke or me. We'll go into it in much more detail the next couple of weeks.

Problems

1. Suppose we are given a list of n integers, and we want to find the largest. Describe an algorithm, step by step, as precisely as you can without a specific computer language. Then determine the time complexity of your algorithm in big-oh notation.

2. Repeat for this problem: We are given a list of the birthdays of everyone in a class of n students, in the form of integers, 1 for January 1, 2 for January 2, etc. The number of students n might be very large, and the list is not in any particular order. Find out if there are two students who have the same birthday.

3. Repeat for this problem: We are given a list of n integers, where n is even, and we want to find out if there is some subset of them that add up to exactly n/2.

4. Suppose we want to choose between two algorithms for sorting. The first, INSERTION SORT, takes O(n²) time; and the second, MERGE SORT, takes O(n log n) time. Under what circumstances might we prefer to use INSERTION SORT instead of MERGE SORT? Explain your answer in as much detail as necessary to be convincing (to yourself and me).

5. In class I mentioned this little piece in Science's 125th anniversary issue: C. Siefe, "What are the limits of conventional computing", Science, vol. 309, July 1, 2005, p. 96 click here. Here's an excerpt from paragraph 3:

For example, theorists can now classify computational problems into broad categories. P problems are those, broadly speaking, that can be solved quickly, such as alphabetizing a list of names. NP problems are much tougher to solve but relatively easy to check once you've reached an answer.

Find the mistake.