Massachusetts Institute of Technology Handout 56 6.042J/18.062J: Mathematics for Computer Science November 20, 1998 Professors Nancy Lynch and Srini Devadas

Problems for Recitation 11 (11/20/98)

1 Team Problem

Problem 1. Consider the scenario considered earlier: a quiz problem has an error with probability 10%, the TA says whether or not there is an error, answering correctly with probability 80%, and the lecturer answers correctly with probability 75%. The three events of existence of an error, the TA responding correctly and the lecturer responding correctly are mutually independent.

Is the event T, “the TA says that there is an error”, independent of the event L, “the lecturer says that there is an error”?

Problem 2. This is a real problem that came from a research project in computational biology last year.

It is known that atoms occur in different isotopes. For example, Carbon atoms usually have 6 protons and 6 neutrons, but occasionally they have 7 neutrons. In fact, 1.11% of all Carbon atoms have 7 neutrons and 98.89% have 6. From what we know, the appearance of the different isotopes seems to be a random event, unrelated to the functionality of the atom. We can tell which Carbon atoms have an extra neutron only by their atomic weight. The atomic weight of the generic Carbon atom is 12 while the weight of its rarer isotope is 13.

The research team is studying proteins composed of Carbon, Oxygen, Nitrogen and Hydrogen (the four building blocks of life). Their atomic weights and isotopes are listed below. The second column is the atomic weight and the third column is the frequency of the isotope. Assume that the probability of an unlisted isotope ocurring is zero (i.e., no tritium in our model).

Hydrogen 1 P_{H,1}
2 P_{H,2}
Carbon 12 P_{C,12}
13 P_{C,13}
Nitrogen 14 P_{N,14}
15 P_{N,15}
Oxygen 15 P_{O,15}
16 P_{O,16}
17 P_{O,17}

Suppose we want to predict the distribution of atomic weights for any protein. Describe a simple algorithm for computing the weight distribution of any protein that contains n_{C} carbon atoms, n_{O} oxygen atoms, n_{N} nitrogen atoms and n_{H} hydrogen atoms. [Hint: Use generating functions!]