Study Guide for Final Exam, Friday Dec 6, 2002, 2:30-4:30 pm in our usual classroom

Topics:
Chapter 2: 
	My guess is that at this point you know basics about variables
	and expressions pretty thoroughly. 

Chapter 3: 
	You'll still need to know about basic while and for loops, etc.
	The switch and do statements will not be on the exam.

Chapter 4: 
	The main topics are:
	* how to write a function (class method)
	* how to define a simple class 

Chapter 5:
      Main topics:
	* The fact that java variables are really "references" to objects
	* null
	* aliases
	* garbage collection
	* nested classes (may be used in examples)
 
Chapter 6, Arrays:
      * array basics
      * arrays of objects; need to allocate both array and the 
	  objects in it.
      * sorting examples of array manipulation.
      * ArrayLists. An ArrayList might be on the exam.

Chapter 7, Inheritance:
    We discussed the following four rules for inheritance:
    1. Classes inherit data and, by default, functions from the parent class
    2. Classes can *override* functions from the parent class, 
       redefining them. The parent function can be called using super;
       thus, the parent can either be completely replaced or partly
       recycled.
    3. Objects can be assigned to a variable of less-specific type.
	 (Note that this implicitly requires understanding how variables
	  are really references.)
    4. Rule 3 notwithstanding, objects remember *their* version of 
       any overridden functions, provided the less-specific type 
       at least "knew" about that function. That last clause is important
       for type checking of function parameters: at compile time we 
	 can verify that all parameter types are as expected.

	Some of all this is covered in 7.0 and some in 7.4.
	Interfaces, GUIs, and mouse events will *not* be on the exam.

Chapter 11, Recursion:
	Study 11.0-11.2. 
	* Understand how to identify the atomic (or base) case, and 
	  how the recursive case is simpler than the initial case.
	  For example, in the factorial function, the base case is n==0,
	  and otherwise the recursive case is invoked with a *smaller* n.
		public int factorial(int n) {
		   if (n==0) return 1;
		   else return n*factorial(n-1);
		}
	* Understand the examples we discussed in class. 
		fact, fib, sum
		maze (harder)
		tower of hanoi
		expressions (harder)
		8queens (harder)
		Koch snowflake
		Linked list (lab 11)
	* Understand why recursion is well-suited to problems involving
	  *backtracking*, that is, returning to an earlier point to pick up
	  where we left off. Examples include the maze and 8queens.

Chapter 12, data structures:
	We basically did section 12.1 in Lab 11; Lab 11 dealt
	with lists of String; section 12.1 deals with lists of
	Magazine.


======================

Sample questions

See also the sample questions on previous study guides

1. For the 8queen and Maze examples, describe:
(a) what the base case is in each
(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.

2. (a) Write a recursive function that satisfies the following
   rules:
	f(0) = 1
	f(n) = 2*f(n-1) -1, if n>0
   (b) find f(100) (Hint: try a few and see)
   (c) What happens if you change it so f(n) = 2*f(n-1)+1?

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++;
	}


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.

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());
}
(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);