1)Consider the following interface:

public interface FlyingVehicle
{
  public void takeoff(); //set a boolean instance variable to true
  public void land(); //set a boolean instance variable to false
  public void setAltitude(double alt); //save altitude in an instance variable
  public double getaltitude();
}

Finish the following class

public class FlyingTruck extends Truck implements FlyingVehicle
{


}	

2) Given the following functions:

boolean isANumber(String s)     returns true if s can be converted to a double
boolean isAnOperator(String s)    returns true if s is "+" "-" "/" or "*"
double stringToDouble(String s)  returns the double value represented by s

And given a templatized Stack class

public Stack<T> which supports the standard stack operations...

write a function that will take as parameters an array of strings
and return the value of the postfix expression represented by those strings.

The first line should look like this:
public double postfix(String data[])

Example:
If you were to the follwoing

String[] d = new String[10];
d[0] = "10.3";
d[1] = "30.7";
d[2] = "+";
double answer = postfix(d);

You would expect answer to be 50.0

3) Implement any of the following tasks using recursion:

a) Given the root node of a binary tree, count the number of leaf nodes.

b) Given the root node of a binary tree, find the depth (number of steps 
from the root) of the deepest node.

c) Given a doubly linked list in which all of the current contents
are in sorted order, write a recursive function to insert a new element
into the proper location to maintain sorted order.

d) Efficiently raise a double to a (positive) integer power.


e) Consider the following family of drawings, and write a recursive program that for any N, will create draw(N)

draw(1)
*

draw(2)
*
**
*

draw(3)
*
**
*
***
*
**
*

draw(4)
*
**
*
***
*
**
*
****
*
**
*
***
*
**
*


4) Implement a single linked List class with methods addFirst() , 
getFirst() and removeFirst(). The data of the List nodes 
(the class Node() must be provided, too!) must be of type "char:.



5) Please give pseudo code for the insertion of a node at last position in 
a doubly linked list with reference(pointer) "last" to the final element.


  
6) What does it mean to say that a particular class implements the "Comparable" interface?

7) A particular algorithm is O(n*n*lg(n)) (n squared lg(N)). When run on a dataset of size 128 it requires 50 seconds to complete. Roughly how long would you expect it to take to process a dataset of size 1024?

____________ seconds

8) What is the "big oh-ness" of the following code fragment? 
Watch out! Please look carefully at the loop-control variables! 

int sum = 0;
for (int i = 0; i < n; i++)
{
  for (int j = 0; j < n/2; j++)
  {
    for (int k = 0; k < 3; k++)
    {
      sum = i + j + k;
    ]
  }
}
System.out.println("sum = " + sum);


Answer: O(___)

9) Draw all of the binary trees with three nodes



10) A binary tree with N nodes is at least how deep?

How deep is it at most?

11) Evaluate the following expression in postfix notation:
1, 3, +, 2, 4, +, *, 2, / 18 +

Answer: ____

12) A Binary Search Tree is a binary tree with what additional property?

13) Beginning with an empty binary search tree, insert the following values 
in the order given.  Draw the tree at each step of the process.

1 10 5 20 22 7

14) Now delete the value 10 from the tree in question T8.  Show each of 
two possible configurations the resulting tree could have.


What's correct?

	Static methods come with the JAVA distribution and can only be altered by SUN
	Static methods can not contain variables, they are for "static" purposes (like System.out.println)
	Static methods can not be overridden
	Static methods can only access static (class) variables  
	   
15) Traverse the tree of T14 in post-order and in-order:
Post-order


In-order



16) Bubble sort is a quadratic sort, i.e. it runs in O(n2). There are better, O(n log(n)) sorts. Why can it be advantageous to use Bubble Sort anyway?

17) A certain algorithm to determine the jitter in a data set consists of 2 steps: sorting data (n elements), using merge sort, and computing the sum of differences between all subsequent elements. What's the "big oh'ness" of that algorithm?