Homework 2
        CMPS 102 - F05 - M. Warmuth

Handed out: Th Sept 29
Due: Th Oct 6 at beg. of class

1. 3.2, p58
2. 4.1-5, p67
3. 4.2-2, p72
4. 4-4, a), c) p86

Remember: T(1)=1 is the default initialization

5. You have 70 coins that are all supposed to be gold coins
of the same weight, but you know that one coin is fake and
weights less than the others. You have a balance scale;
you can put any number of coins on each side of the scale
at one time, and it will tell you if the two sides weigh
the same, or which side is lighter if they don't weigh
the same. Outline an algorithm for finding the fake coin. How many
weightings will you do?

6 EC. The first n cells of an array E contain integers sorted
in increasing order. The remaining cells all contain some
very large integer that we may think of as infinite
(call it maxint). The array may be arbitrarily large (you may
think of it as infinite), and you dont know n. Give
an algorithm for finding a given integer x (x < maxint)
in the array in O(log n) time.