1. (12 points)  Given the method x() below, write the method sort() that puts
  the entries in the array t in ascending order ("Apple", "Toy", "alfalfa",
  "open",...).  You may use any algorithm you wish for the sort.

    void x(){
       String t[]={"sand","open","Apple","tiger","orange","Toy","alfalfa"};
       sort(t);
    }
=============================================================================
 void sort(String t[]){
  //a quick and dirty bubble sort (very inefficient)
  String temp;
  for(int j=0;j<t.length;j++)
    for(int k=0;k<t.length-1;k++)
    if(t[k].compareTo(t[k+1])>0){
       temp=t[k];
       t[k]=t[k+1];
       t[k+1]=temp;
  }
 }
}
=============================================================================
2. (12 points) Assume you are given the class Util below. Write the class
   MySqrtException (a checked exception). Then write the code for the method
   x(), which is passed an array of doubles and replaces each double with its
   square root by calling MySqrt. The code in the main() method in class Util
   shows how x() is called.  If an exception is thrown, an error message
   should be displayed and then the program should continue.
   class Util{
    public static double mySqrt(double x) throws MySqrtException{
     if(x<0) throw new MySqrtException("Negative argument: "+x);
     if(x==0)
       return 0;
     double guess;
     guess=x/2;
     for(int j=0;j<7;j++)
       guess=(x+guess*guess)/2/guess;
     return guess;
    }
    public static void main(String arg[]){
      double v[]={2.4, 3.7, 8, 9.2, 1.6};
      x(v);
    }
   }
=============================================================================
    static void x(double v[]){
      for(int j=0;j<v.length;j++)
       try{
          v[j]=mySqrt(v[j]);
          }
         catch(MySqrtException m){
          System.out.println(m.getMessage());
         }
      }

   class MySqrtException extends Exception{
     public MySqrtException(String x){
       super("MySqrtException: "+x);
     }
   }
=============================================================================
3.  (12 points) Write a recursive method that sums the entries x[i], x[i+1],
     ..., x[j] of the array of doubles, x, using the following recursvie
     algorithm:   To sum the entries, add the first entry, the last entry,
     and the sum of the remaining entries.  If we name the method sum(), here
     is how it is called:
         double r[]={2.6, 3.1, 1.7, 2.8, 9.6};
         System.out.println("The sum is "+ sum(r,0,4));
=============================================================================
  static double sum(double []x,int low, int high){
    if(low>high)
      return 0;
    if(low==high)
      return x[low];
    return x[low]+x[high]+sum(x,low+1, high-1);
  }
=============================================================================

4.  (12 points)  Assume the file ints.dat contains only ints. Write a program
     that reads ints in the file ints.dat and prints out their sum.
=============================================================================
     import java.io.*;
     import java.util.Scanner;
     public static void main(String afg[]){
       int x,sum;
       sum=0;
       try{
         Scanner sc=new Scanner(new FileInputStream("ints.dat"));
         while(sc.hasNextInt()){
           x=sc.nextInt();
           sum+=x;
         }
         System.out.println("The sum is "+sum);
       }
       catch(IOException e){
         System.out.println("Failure to open the file 'ints.dat'");
       }
     }
=============================================================================

5.  (12 points)  Assume class Node, defined below, is used to construct a
    binary tree with no repeated entries and having the property that
    the entry at any node is greater than all entries in the subtree whose
    root is the left child and less than all entries in the subtree whose root
    is the right child. Write the methods isContainedIn() and
    hasTheSameEntries().  The method isContainedIn() returns true if and
    only if all the entries in the first tree are in the second tree.  The
    method hasTheSameEntries() returns true if and only if both trees have
    the same entries.  Hints:  isContainedIn() could call a simpler method
    that asks whether an int is in the tree.  Below I show how the methods
    are called.
      class Node{
         public int entry;
         public Node child[2];
      }

      public static void main(String arg[]){
         Node t1,t2;
         // .....
         //.....
         //code for building trees with roots t1 and t2
         System.out.println("It is "+isContainedIn(t1,t2)+
            " that all the entries in the first tree are in the second tree");
         System.out.println("It is "+hasTheSameEntries(t1,t2)+
            " that both trees have the same entries");
      }
==============================================================================
  static boolean inTree(int j,Node rt){
    if(rt==null)
      return false;
    if(j==rt.k)
      return true;
    if(j<rt.k)
      return inTree(j,rt.child[0]);
    return inTree(j,rt.child[1]);
  }

  static boolean isContainedIn(Node rt,Node container){
    return rt==null ||
      inTree(rt.k,container) && isContainedIn(rt.child[0],container)
              && isContainedIn(rt.child[1],container);
  }

  static boolean hasTheSameEntries(Node rtA, Node rtB){
    return isContainedIn(rtA,rtB) && isContainedIn(rtB,rtA);
  }
==============================================================================
6. (10 points) 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, a multi-threaded linked list, stack,
   queue, priority queue, binary search tree. Note: you DO NOT have to write
   code ? just pick the best data structure and explain why it is indeed the
   best of these choices! (10 points)

   a. Given a small file of characters(less than 500 characters) test if it
      is a palindrome.
        one dimensional array, comparing from each end
        (very clumsy) a linked list, comparing from each end
   b. A newspaper machine that dispenses newspapers.
        stack

   c. The board for the "Eight Queens" problem.
        two dimensional array
      
   d. An ailing company wants to evaluate employee records so that it can lay
      off some workers on the basis of service time (the most recently hired
      employees are laid off first).
         stack

   e. A program (www.switchboard.com) that allows a telephone number to be
      entered anywhere in the United States and then returns the person?s name
      and address to whom the phone number belongs.
         binary search tree (that is bushy)

   f. People traveling up an escalator.
         queue
       
   g. A sort button on an application that will enable data stored in records
      to be displayed in a number of different orders.
          multi-threaded linked list (or multi-threaded tree)

   h. The logic used for the back button on a web browser.
          stack

   i. British Royal Family Genealogy Records
          binary search tree

   j. The checkout area at a supermarket that has registers for 10 items or
      less, for 15 items or less, or for items more than 15.
           priority queue
7. (5 points) Using the Pizza and Sicilian class defined on the last page,
   what will be printed when the following statements are executed.

    Pizza p = new Pizza('M',0,1,0);
    System.out.println(p);
    Sicilian s = new Sicilian(new Pizza('L',1,1,1),20);
    System.out.println(s);}
==========================================================================
     Regular Pizza(M, Cheese: 0, Pepperoni: 1, Ham: 0, Cost: 14.0)
     Sicilian Pizza(L, Cheese: 1, Pepperoni: 1, Ham: 1, Cost: 40.0)
==========================================================================
8. (15 points) I started writing a class called PizzaOrders whose purpose is
   to keep track of the pizza orders that are taken in at a pizza shop. Note
   that it uses the class Pizza, which is declared on the last page.

 class PizzaOrders{
   private  Node head;
    private  Node tail;

     public class Node{
       private int orderNumber;
       private Pizza pizza;
       private Node next;



 Write all methods and constructors necessary to execute the following code:

    Sicilian pie1 = new Sicilian(new Pizza('L',4,4,4),25);
    Pizza pie2 = new Pizza('L',1,1,0);
    Pizza pie3 = new Pizza('S',1,0,1);
    Sicilian pie4 = new Sicilian(pie1,10);
    PizzaOrders list = new PizzaOrders();
    list.enqueue(1,pie1);
    list.enqueue(2,pie2);
    list.enqueue(3,pie3);
    list.enqueue(4,pie4);
    list.dequeue();
    list.cancelOrder(3); //takes in an order number and removes the
                         //order from the list.
    System.out.println(list);
==========================================================================

class PizzaOrders{
     private Node head;
     private Node tail;
     private class Node{
       private int orderNumber;
       private Pizza pizza;
       private Node next;
     public Node(int num,Pizza p,Node n){
         orderNumber = num;
         pizza = p.clone();
         next = n;
      }
     public String toString(){
       return "Order Number: " + orderNumber + " " + pizza;
     }
     }
    
     public PizzaOrders(){
       head = null;
       tail = null;
     }
     public void enqueue(int num,Pizza p){
       if(head == null){
         head = new Node(num,p,null);
         tail = head;
       }
       else{
         tail.next = new Node(num,p,null);
         tail = tail.next;
       }
     }
     public void dequeue(){
       if(head == null){
         System.out.println("No More Orders");
       }
       else
           head = head.next;
     }
     public void cancelOrder(int num){
       Node temp = head;
       if(head == null)
          System.out.println("No Orders in the Queue");
       if(tail == head && head.orderNumber == num){
           head = null;
           tail = null;
       }
       else if(head.orderNumber == num){
         head = head.next;
       }
       else{
       while(temp.next != null && temp.next.orderNumber != num){
            temp = temp.next;
       }
       if(temp.next == null)
         System.out.println("Order Not Found");
       else if(temp.next == tail)
          tail = temp;
       else
         temp.next = temp.next.next;
     }
     }
     public String toString(){
       Node temp = head;
       String t = "";
       while(temp != null){
         t = t + temp + "---->";
         temp = temp.next;
       }
       return t + "null";
   }
  }
==========================================================================

9. (10 points) I started writing a class called Stack whose purpose is to keep
   track of characters that are placed onto a Stack data structure.

class Stack{
  char [] sign;
  int elementsInArray;

  public Stack(){
    sign = new char[10];
    elementsInArray = 0;
  }
==========================================================================

class Stack{
  char [] sign;
  int elementsInArray;
  public Stack(){
    sign = new char[10];
    elementsInArray = 0;
  }
  public void push(char c){
    Check.err(elementsInArray < sign.length,"Array Full");
    sign[elementsInArray] = c;
    elementsInArray++;
  }
  
  public String toString(){
    String temp = "";
    for (int i = 0; i < elementsInArray; i++)
      temp = temp + sign[i] + " ";
    return temp;
  }
}

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

class Pizza{
    private char size;
    private int [] toppings;

    public Pizza(char s, int cheese, int pepperoni, int ham){
    size = s;
    toppings = new int[3];
    toppings[0] = cheese;
    toppings[1] = pepperoni;
    toppings[2] = ham;
    }

    public Pizza(Pizza p){
      size = p.size;
      toppings = new int[3];
      for(int i = 0; i < toppings.length; i++){
        toppings[i] = p.toppings[i];}
    }

    public Pizza clone(){
        return new Pizza(this);}

    public String toString(){
      return getType() + "(" + size + ", Cheese: " + toppings[0] + ",
        Pepperoni: " + toppings[1] + ", Ham: " + toppings[2] + ", Cost: " +
        pizzaCost()+ ")";}

    public double pizzaCost(){
      double cost = 0;
      if(size == 'S')
        cost = 10;
      else if(size == 'M')
        cost = 12;
      else if(size == 'L')
        cost = 14;
      for(int i = 0; i < toppings.length; i++)
          cost = cost + (toppings[i] * 2);
      return cost;}

     private String getType(){
      return "Regular Pizza";}
    }

   class Sicilian extends Pizza{
    int addedCost;
    public Sicilian(Pizza p, int aCost){
      super(p);
      addedCost = aCost;}

     public Sicilian(Sicilian s){
      super(s);
      addedCost = s.addedCost;}

    public Sicilian clone(){
        return new Sicilian(this);}

     public double pizzaCost(){
      return addedCost + super.pizzaCost();}

     public String getType(){
       return "Sicilian Pizza";}
   }