1. The following program computes 2ⁿ:

   int power2(int n) { if (n==0) return 1; return power2(n-1)+power2(n-1); }

   1. Find a recurrence formula as we learned in class. Find the runtime. What is the big problem with this function? (hint: We discussed something similar in class).

   2. Introduce a small modification that makes the function run in linear time. Show why the runtime is linear.

2. Designing a Java class. A combination lock has the following basic properties: the combination (a sequence of three numbers) is hidden; the lock can be opened by providing the combination; and the combination can be changed, but only by someone who knows the current combination. Design a class with public methods open and changeCombo and private data fields that store the combination. The combination should be set in the constructor. Do not compile and run your code, just show it in your homework paper.

3. Review Java OO principles, specifically the idea that all Java classes are subclasses of the Object class, and thus must have all the methods of the Object class. You can see the Object class API (and any other standard class) by following the link "JDK API" on the class web page under Resources, or at the Piazza site. Choose Object in the pane titled All Classes, and the API will be displayed on the right.

   1. What are the three most important Object methods? (Hint: their names start with e, h, and t). Because all objects have these methods, we can use HashSet to contain any set of objects (we'll stick to sets of same-type objects in our work).
   2. Show equals in use by writing one if () that checks whether s String s is equal to a String t, character by character. Explain what this comparison is doing if s = abc and t = abx. Compare this to what happens in if (s == t).
   3. Find the hashCode and toString values for String s = abc. Also for the Integer of value 6.

4. Interfaces

   1. What is a Java interface?
   2. What members may be in an interface?
   3. Write a Java interface source file UnionFind.java to express the API on page 219, the union-find interface. Also rewrite just the first line of UF.java to assert that class UF implements this interface.