CSE 17 FINAL  TUESDAY 20 DECEMBER 2005
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<SUGGESTED ANSWERS>>>>>>>>>>>>>>>>>>>>>>

1. For the following scenarios, what would be the best data structure to use
as the primary data structure in a Java implementation?  Justify your choice.
Choose from the following data structures: array, two-dimensional array,
linked list, stack, queue, binary tree, B-tree, hash table. Note that you DO
NOT have to write code - just pick the best data structure and justify that
it is indeed the best of these choices!
a. A tic tac toe game
b. A program that evaluates arithmetic expressions where *, / have precedence
   over +,-.
c. A grocery chain wants to run a simulation to see how the average customer
   wait time would be affected by changing the number of checkout lines in
   its store.
d. A data structure used to keep track of the return addresses for nested
   method calls while a program is running.
e. A major online shopping company that gives each customer a confirmation
   number that can be used to determine the status of recent or past orders.
f. A dictionary of words used by a spelling checker.     

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
a. two dimensional array
b. Stack
c. Queue
d. Stack
e. Hash Table
f. Binary Tree/B Tree
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2a. Below is the data structure developed in class for a linked list. Write a
recursive method in class LinkedList, called min(), that returns the minimum
value in an unsorted linked list.
public class LinkedList <T extends Comparable>{
private class Link
  {public Link(){this(null,null);}
public Link(T t){this(t,null);};
public Link(T t, Link nxt){data=t;  next=nxt;}
private Link next;
private T data;
}

private Link head;
public LinkedList(){head=new Link();}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
public T min()
{if(head.next==null)
   return null;  ///this is the case of an empty list
 return min(head.next);}

public T min(Link hd){
 if(hd.next==null)
   return hd.data;
 return min(hd.data,min(hd.next));
}

public T min(T a, T b)
{if(a.compareTo(b)<0)
  return a;
 return b;
}

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2b. Given the following function:
public static int Func (int num)
{
if (num == 0)
return 0;
else
return num*num + Func(num + 1);
}

a. Is there a constraint on the values that can be passed as a parameter
   for  this function to work properly.
b. Is Func(5) a good call? If not, why not? If so, what does Func(5) return?
c. Is Func(0) a good call? If not, why not? If so, what does Func(0) return?
d. Is Func(-5) a good call? If not, why not? If so, what does Func(-5) return?
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
a. Yes, the value passed to Func must be a negative number or 0
b. Infinite recursion
c. Zero
d. 55
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
3. Write a class that will read an input file called animals.txt that has no
more than 1000 words, one word per line. The class should then print to an
output file (revanimals.txt) the words in animals.txt in reverse order. For
example if the input had the following words (one word per line): dog cat
turtle squirrel, the output file would have the words (one word per line):
squirrel, turtle, cat, dog. Note, you do not have to prompt for the file
name, simply hard code the names of the input and output files.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
import java.io.*;
import java.util.Scanner;
public class Reverse <T extends Comparable>{
       public static void main(String[] args) {
           String x ="";
    	   	Scanner inputStream = null;
    	   	PrintWriter outputStream = null;
    	   	FileInputStream inputFile = null;
    	   	FileOutputStream OutputFile = null;

    	   try
    	   {
    	   	inputFile = new FileInputStream("animals.txt");
    	   	inputStream = new Scanner(inputFile);
    	   }
    	   catch(FileNotFoundException e)
    	   {
    	   	System.out.println("File animals.txt not found");
    	   	System.out.println("or could not be opened.");
    	   	System.exit(1);
    	   }
    	   try
    	   {
    		OutputFile = new FileOutputStream("ranimals.txt");
    	   	outputStream = new PrintWriter(OutputFile);
    	   }
    	   catch(FileNotFoundException e)
    	   {
    	   	System.out.println("File ranimals.txt not found");
    	   	System.out.println("or could not be opened.");
    	   	System.exit(1);
    	   }

    	   while(inputStream.hasNextLine())
                x=inputStream.nextLine()+"\n"+x;

           outputStream.println(x);


    	   inputStream.close();
    	   outputStream.close();
    	   	
    	   }
}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
4. The definition below uses an Array to implement a Stack. Write the push()
and pop() methods so that the following output is produced when the commands
are  typed into the interaction panel. Hint, do not move the data within
the array when pushing and popping.

>x = new ArrayStack <String> ()
{}
>x.push("Hello")
>x.push("World")
>x.pop()
World
>x
{Hello}

public class ArrayStack<E> 
{  public final int INITIAL_CAPACITY = 10;
   private E[] data;
   private int manyItems;	
   public ArrayStack()
   {
	   manyItems = 0;
	   data = (E[]) new Object[INITIAL_CAPACITY];
   }

public void push(E item)
   {
           check(manyItems < data.length,"Stack is full");
	   data[manyItems] = item;
	   manyItems++;
   }
   public E pop()
   {
           E answer;
           check(manyItems > 0,"Stack is empty");
	   answer = data[manyItems-1];
	   data[manyItems-1] = null;
	   manyItems--;
	   return answer;
   }
private void check(boolean b,String mess){
     if(!b)
       {System.err.println("ERROR: "+mess);
        System.exit(1);
       }
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
5.  Below is the data structure developed in class for the Binary Tree.
    Write a Bintree method, countLeaves(), that returns the number of
    leaves in the tree. Thus, if we have the declaration
      Bintree t=new Bintree();
    then the following code would display the number of leaves in the
    tree t.
      System.out.println("The tree has "+t.countLeaves()+" leaves\n");

public class Bintree <T extends Comparable>{
   public static final int LEFT=0, RIGHT=1;
     class Binode{
       public static final int LEFT=Bintree.LEFT,RIGHT=Bintree.RIGHT;
       protected Object [] child=new Object[2];
       protected T data;
       protected int height;
       public Binode(T d, Binode left, Binode right){
             data=d;
             child[LEFT]=left;
             child[RIGHT]=right;
             height=0;
      }
      public Binode(T d, Binode left){
             this(d,left,null);
      }
      public Binode(T d){
             this(d,null,null);
      }
   }

   private Binode root;
        ....//the rest of the stuff....
}
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	public int countLeaves()
	{return countLeaves(root);}
	
	private int countLeaves(Binode rt){
		if(rt==null)
			return 0;
		if(rt.child[LEFT]==null && rt.child[RIGHT]==null)
			return 1;
		return countLeaves( (Binode)(rt.child[LEFT]))+
		       countLeaves((Binode)(rt.child[RIGHT]));
	}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
6. a.  Assume the binary tree to the right is                  8
       being maintained as a balanced binary tree,           /   \
       using the algorithms discussed in class.             4    15
     i. Show the tree after the number 12 is                    /  \
        added to the tree (maintaining balance).              10   18
    ii. Starting with the original tree, show the
        tree after the number 17 is added to the
        tree (maintaining balance).
   b.  Assume the binary tree to the right is                  8
       being maintained as a B-tree, using the               /   \
       algorithms discussed in class.  Show the            -4    12
       tree after the numbers 20, 24, 25, and 27          / \    / \
       are added to the tree in that order              -8  -2  10  28
       (maintaining balance).
   c.  Assume you have a hash table of integers of
       size 11, and assume that the integers themselves
       serve as hash numbers. Show the status of the
       table after each of the following numbers is
       added to the table, using a quadratic probe:
       21, 44, 98, 65.
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
a.i.   8               10        a.ii.   8                15
      / \             /  \              / \              /  \
     4  15    ===>   8    15           4  15    ===>    8   18
       /  \         /    /  \            /  \          /\   /
     10   18       4   12   18          10  18        4 10 17
      \                                    /
       12                                 17

b.      8               8                  8                      8
      /   \           /   \              /   \                  /   \
    -4     12  ==>  -4     12 ==>      -4     12   ==>        -4    12,24
   /  \   /  \     /  \   /  \         /  \   /  \           /  \   / |  \
 -8  -2  10  28   -8  -2  10 20,28   -8  -2  10 20,24,28   -8  -2  10 20  28

           8                      8                          8
         /   \                  /   \                      /   \
  ==>  -4    12,24     ==>    -4    12,24        ==>    -4   12,24,27
      /  \   / |  \          /  \   / |  \             /  \  / |  |  \
    -8  -2  10 20  25,28   -8  -2  10 20 25,27,28    -8  -2 10 20 25 28
         
           8   24
        /    |   \
 ==>  -4     12    27     
     /  \   / \    / \
    -8  -2  10 20 25 28
c. Use quadratic probe (and note how it spreads out the data)
  0   1   2   3   4   5   6   7   8  9   10
---------------------------------------------
|   |   |   |   |   |   |   |   |   |   |21 |  21%11=10 ==>10
---------------------------------------------
|44 |   |   |   |   |   |   |   |   |   |21 |  44%11=0 ==>0
---------------------------------------------
|44 |   |   |98 |   |   |   |   |   |   |21 |  98%11==10 ==>(10+4)%11=3
---------------------------------------------
|44 |   |   |98 |   |   |   |   |65 |   |21 |  65%11==10 ==>(10+9)%11=8
---------------------------------------------
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
7.  After reading this problem, but before writing the solution to this
    problem, read the next problem, which depends on your solution of this
    problem. Create a class, VoteCounter, for counting votes.  It should be
    able to record "yes" and "no" votes and to return the number of "yes"
    votes and the number of no votes.  Below is a diaglog from the
    "interaction pane" that illustrates the behavior of the class.

    > h=new VoteCounter()
    Yes: 0, No: 0
    > h.no().no().yes()
    Yes: 1, No: 2
    > h.yeses()
    1
    > h.noes()
    2
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
public class VoteCounter {
  protected int yesCt, noCt;
  public VoteCounter(){
	  yesCt=0;
	  noCt=0;
  }
  public VoteCounter yes(){
	  yesCt+=1;
	  return this;
  }
  public VoteCounter no(){
	  noCt++;
	  return this;
  }
  public int yeses(){
	  return yesCt;
  }
  public int noes(){
	  return noCt;
  }
  public String toString(){
	  return "Yes: "+yesCt+", No: "+noCt;
  }
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8.  Write a class FullCounter, which is a subclass of VoteCounter, which has
    the capacity to record and return abstentions, and which has the capacity
    to add two instances of FullCounter.  Below is a dialog from the
    "interaction pane" that illustrates the behavior of the class.

    > a=new FullCounter()
    Yes: 0, No: 0, Abstentions: 0
    > a.abstain().abstain().no().yes().yes().yes()
    Yes: 3, No: 1, Abstentions: 2
    > b=new FullCounter()
    Yes: 0, No: 0, Abstentions: 0
    > b.abstain().yes().no().no()
    Yes: 1, No: 2, Abstentions: 1
    > c=a.plus(b)
    Yes: 4, No: 3, Abstentions: 3
    > c.abstentions()
    3
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
class FullCounter extends VoteCounter{
	private int abstCt;
	public FullCounter(){
		abstCt=0;
	}
	public FullCounter abstain(){
		abstCt++;
		return this;
	}
	public int abstentions(){
		return abstCt;
	}
	FullCounter plus(FullCounter f){
		FullCounter temp=new FullCounter();
		temp.yesCt=yesCt+f.yesCt;
		temp.noCt=noCt+f.noCt;
		temp.abstCt=abstCt+f.abstCt;
		return temp;
	}
	public String toString(){
		return super.toString()+", Abstentions: "+abstCt;
	}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>