Midterm Solution

1. Box trace of a binary search for 31 in anArray=<11, 21, 31, 41, 51, 61, 71>

   value = 31 first = 0 last = 6 mid = (0 + 6) / 2 = 3 value < anArray[3]

   value = 31 first = 0 last = 2 mid = (0 + 2) / 2 = 1 value > anArray[1]

   value = 31 first = 2 last = 2 mid = (2 + 2) / 2 = 2 value = anArray[2] return 2

2. /**
    * computeMax: compute and return the largest integer in a list of integers.
    * @param aList, a list object of a class that implements IntegerListInterface
    * @return the maximum integer in aList, or Integer.MIN_VALUE if alist is empty. 
    */
   public int computeMax (IntegerListInterface aList)
   {
       int size = aList.size();
   
       if (size == 0)
          return Integer.MIN_VALUE;
    
       // Invariant: aList has at least one element.
       int max = aList.get(1); // initialize the maximum so far to the first item in aList.
   
       for (int i = 2; i <= size; i++)
       {
   '       // Get the next item in aList
   	int nextItem = aList.get(i);
   
           // If next item is greater than max (the maximum we've seen so far) then update max 
   	if (nextItem > max)
              max = nextItem;
       } // end for
   
       return max;
   } // end computeMax
   

3. /**
    * deposit: Bank method which deposits a given amount to the account corresponding to the given account ID.
    * @param accountId String  the ID of the account to which we want to deposit
    * @param amount    Money   the amount to deposit
    * @return none
    * Throws AccountNotFoundException if there is no account with the given ID.
    */
   public void deposit (String accountId, Money amount) throws AccountNotFoundException
   {	
   	// Search for the account with the given id.
           int index = this.find(id);  // call helper method
   
           if (index == -1) { // id not found
   		throw new AccountNotFoundException(id + " not found");
           }
   	else { // id was found; deposit to the appropriate account
   		Account acc = (Account) accounts.get(index);
   		acc.deposit(amount);
   	}
   } // end deposit
   
   /**
    * find: helper method of deposit
    * @param id  String
    * @return the index of the account with the given id, or -1 if not found.
    */
   private int find(String id)
   {
           int numOfAccounts = accounts.size();
   
   	for (int i = 1; i <= numOfAccounts; i++) {
   		// Get the next account (at index i) from the list of accounts.
   		Account nextAcc = (Account) accounts.get(i);
   
   		// If its id matches the id given as parameter, then return the index of the account whose id matched 
   		if (id.equals(nextAcc.getId()))
   			return i;
   	} // end for
   
   	// Invariant: id was not found, so return -1.
   	return -1;
   } // end find
   

4. • d) There is a catch clause for ArithmeticException in m3.
   • a) There is no catch for NullPointerException in m3, so we check the method that called it (m1). There is no catch for NullPointerException in m1, so we check the method that called it (main). It is caught in main by catch(Exception e).
   • b) There is no catch for IndexOutOfBoundsException in m3, so we check the method that called it (m1). There is a catch for IndexOutOfBoundsException in m1, so it is caught in m1.
5. • b) The constructor of the super class is invoked to initialize the inherited attributes a and b, whereas z is an attribute of BClass so we initialize it here. (Similarly, the constructor of ColoredSphere intializes its color after calling the constructor of Sphere to initialize the inherited attribute radius.)
   • b) addEm needs to add x + y + z, so we call super.addEm() which adds x + y and then we add z to that. changeEm needs to change x and y but leave z alone; this is exactly what super.changeEm() does, so we leave changeEm alone, i.e. we don't need to redefine changeEm in BClass.
6. • a) head -> 60 -> 70 -> 77 -> 80 -> 90 -> null
   • b)

     /**
      * insertSortedNoDuplicates: a ListReferenceBased method which inserts a given object into a sorted list, and keeps it sorted.
      */
     public void insertSortedNoDuplicates(Object item)
     {
     	// If item does not exist in the list, insert it.
     	if (!this.search(item)) {
     		this.insert(item); // call the insert method that we discussed (which inserts an item into the list regardless of whether it is a duplicate or not)
     	} // end if
     } // end insertSortedNoDuplicates
     
     /**
      * search: helper method of insertSortedNoDuplicates that returns true if item exists in the list, false otherwise.
      */
     private boolean search(Object item) 
     {
     	boolean found = false;
     
     	Node current = this.head;
     
     	while (current != null && !found) {
     		if (item.equals(current.getItem())) {
     			found = true;
     		} // end if
     
     		current = current.getNext();
     	} // end while
     
     	return found;
     } // end search