HW 1 Solutions. Mail bugs to brudno@cs.berkeley.edu

1.
a:
static int exp (int x, int y) {
  if (y==0)
    return 1;
  return x*exp(x,y-1);
}

static int exp2 (int x, int y) {
  int rval=1;
  for (; y > 0; y--)
   rval *= x;
  return rval;
}

b.
if (x < 0) return h0(-x);
if (x < 10) return h1(x);
if (x < 1000) return h2(x);
else return h3(x);

c. Impossible in Java: can't have function with different 
return values. 

d. switch(c) {
     case 'u': case 'U': up(); return;
     case 'd': case 'D': down(); return;
     case '=': drop(); return;
     case '+': shoot(); return;

2.
2 possible answers:
1) if init declares a variable, it is available to morestatements
in the while example, but not the for.
2) if statements contains a "continue" update will be executed in
the for loop, but not the while.

3. 
class Arrays {

/** The largest value in the array A. */
   static int maximum(int[] A) {
     int max=A[0];
     for (int i = 1; i < A.length; i++)
       if (max < A[i])
         max=A[i];
     return max;
   }

/** Returns the mathematical average (mean)  of the elements of 
     * the array A. */
   static double mean(int[] A) {
     double sum=0;
     for (int i = 0; i<A.length; i++)
       sum += A[i];
     return sum/A.length;
   }

/** A new array with 1 more element than A, consisting of the elements
    *  of A except that A[w]==b and all elements at indices > w are
    *  located one index higher than previously. */
   static int[] insert(int[] A, int b, int w) {
     int[] n = new int[A.length+1];
     for (int i = 0; i < w; i++)
       n[i] = A[i];
     n[w] = b;
     for (int i = w; i < A.length; i++)
       n[i+1] = A[i];
     return n;
   }

/** The number of pairs i,j such that i < j and A[i] > A[j] */
   static int inversions(int[] A) {
     int inv=0;
     for (int i = 0; i < A.length; i++)
       for (int j = i; j < A.length; j++)
         if (A[i] > A[j])
           inv++;
     return inv;
   }

/** The transpose of A: all rows become columns and all columns 
     * become rows. */
   static int[][] transpose(int[][] A) {
     int[][] tr = new int[A[0].length][];
     for (int i =0; i < tr.length; i++)
       tr[i] = new int[A.length];
     for (int i = 0; i < A.length; i++)
       for (int j = 0; j < A[0].length; j++)
         tr[j][i] = A[i][j];
     return tr;
   }
}


4. 
class Fibs {
  /** Returns the nth fibonacci number without allocating any arrays or
    *  making any recursive calls. For uniformity, fib(0)==0, fib(1)==1 */
  static int getFib(int n) {
    int j=0, k=1, t; 
    if (n==0 || n==1)
      return n;
    for (int i= 2; i <= n; i++) {
      t = j+k;
      j = k;
      k = t;
    }
    return k;
  }

  /** Returns the sum of the first n fibonacci numbers. Feel free to 
   * use the method defined above */ 
  static int sigmaFib(int n) {
    return getFib(n+1)-1;
   }
}

5.
class Strings {
  /** The number of words in string S.  A "word" is a sequence of
   *  non-whitespace characters that is bounded on both sides by
   *  by whitespace or an end of S.  Here, whitespace characters 
   *  are defined by the Java function Character.isWhitespace. */
  static int numWords(String S) {
    int total = 0;
    boolean inside;
    inside = false;
    for (int i = 0; i < S.length(); i += 1) {
      if (Character.isWhitespace(S.charAt(i)))
        inside = false;
      else {
        if (!inside)
          total += 1;
        inside = true;
      }
    }
    return total;
  }

  // [Alternative implementation]
  static int numWords2(String S) {
    return (new java.util.StringTokenizer (S, " \t\n\r")).countTokens ();
  }

  /** The string S with all sequences of adjacent blanks replaced
   *  by a single blank.  Thus, squeeze("This  is     a test") 
   *  is "This is a test".
   */ 
    static String squeeze(String S) {
    String result = "";
    boolean inBlanks;
    inBlanks = false;
    for (int i = 0; i < S.length(); i += 1) {
      if (S.charAt(i) ==  ' ') {
        if (!inBlanks)
          result = result + ' ';
        inBlanks = true;
      }
      else {
        result = result + S.charAt(i);
        inBlanks = false;
      }
    }
    return result;
  }  
}

6.
class LetterStream {
  String mystring;
  int currindex;

  /** Creates a new LetterStream */
  public LetterStream(String s) {
    mystring = s;
    currindex = 0;
  }

  /** Returns the next letter from the stream, if any. */
  public char letter() {
    if (empty())
       throw new IllegalStateException();
    return mystring.charAt(currindex);
  }

  /** returns the number of times letter() appears in the remaining 
   *  part of the stream. Letters of different cases are considered 
   *  different. */

 public int count() {
    if (empty())
       throw new IllegalStateException();
    char c = letter();
    int cnt = 0;
    for (int i = currindex+1; i < mystring.length(); i++)
      if (mystring.charAt(i) == c)
        cnt++;
    return cnt;
  }

  /** Updates letter() and count() to the next letter */
  public void next() {
    if (empty())
       throw new IllegalStateException();
    currindex++;
  }

  /** tests whether all the letters have been delivered. It becomes 
   *  true when you call next(), but there is no next value for 
   *  letter(), and it is always true when the argument to the 
   * constructor was the empty string. */
  public boolean empty() {
    return (currindex >= mystring.length());
  }

  /** returns the stream to initial condition, with factor()
   *  being the first letter of the arg to the constructor. */
  public void reset() {
    currindex = 0;
  }
}

class Letters {
  public static void main(String[] args) {
    LetterStream str = new LetterStream(args[0]);
    boolean[] seen = new boolean[128];
    while (!str.empty()) {
      if (!seen[str.letter()]) {
        seen[str.letter()]=true;
        System.out.print(str.letter()); 
      }
      str.next();
    }
  }
}