1. 1. Show that log_a(x) =c*log_b(x) for some constant c (expressed only in terms of the constants a and b). Hint: This is probably easier than you think... It follows quite directly from the log properties. You should, though, prove that its true for any a and b and not prove by an example.

2. 1. Rank the following three functions: log N, log(N²), log²N. Explain.

3. 1. Find a big-O estimate for the running time (in terms of n) of the following function (with explanation)

      int mysterySum( int n ) { int i, j, s=0; for(i=0; i < n; i++) { for(j=0; j < i; j++) { s += i*i; } } }

   2. Is this version of mysterySum faster? Is the big-O analysis different?

      int mysterySum1( int n ) { int i, j, s=0; for(i=0; i < n; i++) { int i2 = i*i; for(j=0; j < i; j++) { s += i2; } } }

   3. Replace the inner loop in mysterySum by an O(1) expression and compute the running time of the new program.

   4. Find a single O(1) expression giving the same result (A mathematical expression, not code). Hint: Evaluate the function by hand (or compile and run the code) for a few values of n and try to see the pattern.

      Notice: You have to find a mathematical formula, not a piece of code. Start with the expression you derived in part c above (hint: It is a series) and find the sum of the series any way you want (including looking it up).

4. 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.

5. 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.

6. 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.

7. 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.