> Sample questions
 
> 1. For the 8queen and Maze examples, describe:
> (a) what the base case is in each

8queen: you are in column 8 (that is, the ninth column) and have
placed all the queens.

Maze: you are at the end of the maze

> (b) how the recursive case is in some sense "simpler"
>     In the Maze example, consider moves to a square that
>     is a step in the right direction and also moves to a 
>     square that's in a dead-end direction.
 
8queens: simpler case is the next column to the right, with one more
queen in position

Maze: simpler case is whichever neighboring square is closer to
the exit point.


> 2. (a) Write a recursive function that satisfies the following
>    rules:
> 	f(0) = 1
> 	f(n) = 2*f(n-1) -1, if n>0

int f(int n) {
    if (n==0) return 1;
    else return 2*f(n-1) - 1;
}

>    (b) find f(100) (Hint: try a few and see)

f(0)=1, f(1) = 2*f(0)-1 = 2*1 - 1 = 1; f(2) = 1 for the same reason, etc.
f(3) = f(4) = ... = f(100)= ... = 1

>    (c) What happens if you change it so f(n) = 2*f(n-1)+1?

Then f(1) = 3, f(2) = 2*3+1 = 7, ...


> 3. Rewrite the following while loop as a for loop:
> 
> 	int i=0;
> 	int sum=0;
> 	while (i<100) {
> 	    a[i] = Keyboard.readInt();
> 	    sum += a[i];
> 	    i++;
> 	}

int i;
int sum = 0;
for (i=0; i<100; i++) {
    a[i] = Keyboard.readInt();
    sum += a[i];
}


> 4. Consider the following IntList class, implementing a linked list
> of integers:
> 	class IntList {
> 	    private class IntListNode {
> 	       public int _data;
> 	       public IntListNode _next;
> 	       public IntListNode(int d, IntListNode iln) {
> 	           _data = d;
> 		     _next = iln;
> 		 }
> 	    }
> 
> 	    private IntListNode _head;
> 
> 	    ...
> 	}
> Write an add(int i) method that adds the integer i to the front
> of the list.

(inside the class)
          public void add(int i) {
              _head = new IntListNode(i, _head);
          }


> 5. Consider the following three classes:

> public static class Foo {
>     private int _i;
>     public Foo (int i) {_i = i;}
>     public int f() {return _i;}
> }

> public static class Bar extends Foo {
>     public Bar(int i) { super(i);}
>     public int g() {return 2*f();}
> }

> public static class Baz extends Bar {
>     private int _j;
>     public Baz(int x, int y) { super(x); _j = y;}
>     public int f() {return 667;}
>     public int g() {return super.g() + _j;}
> }
> 
> (a) Give the output of:
> public static void main(String[] s) {
>     Bar a = new Bar(2);
>     Bar b = new Baz(2,1);
>     System.out.println(a.f());
>     System.out.println(a.g());
>     System.out.println(b.f());
>     System.out.println(b.g());
> }

// the first two don't involve "inheritance" at all
2 	// straightforward
4 	// straightforward: 2*f() = 2*2 = 4
// The next two are trickier:
667 	// ie we call Baz.f() even though b is of type Bar.
1335 	// Baz.g() says this is 2*Bar.g() + _j = 2*f()+1. 
// Baz.f() is the f used; it returns 667 and the final result is 2*667 + 1

> (b) Explain why we can't declare a and b to be of type Foo, ie
>     Foo a = new Bar(2);
>     Foo b = new Baz(2,1);

Because class Foo doesn't know about the function f(), which is called.