Midterm Solution

1. Box trace of a binary search for 30 in anArray=<10, 20, 30, 40, 50, 60, 70>

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

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

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

2. /**
    * computeMin: 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.MAX_VALUE if alist is empty. 
    */
   public int computeMin (IntegerListInterface aList)
   {
       int size = aList.size();
   
       if (size == 0)
          return Integer.MAX_VALUE;
    
       // Invariant: aList has at least one element.
       int min = 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 less than min (the minimum we've seen so far) then update min 
   	if (nextItem < min)
              min = nextItem;
       } // end for
   
       return min;
   } // end computeMin
   

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.
           Account acc = this.find(accountId);  // call helper method
   
           if (acc == null) { // id not found
   		throw new AccountNotFoundException(id + " not found");
           }
   	else { // id was found; deposit to the appropriate account
   		acc.deposit(amount);
   	}
   } // end deposit
   
   /**
    * find: helper nethod of deposit that searches for the account with the specified id.
    * @param id  String representing the account ID 
    * @return the account with the given id, or null if not found.
    */
   private Account 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 account whose id matched 
   		if (id.equals(nextAcc.getId()))
   			return nextAcc;
   	} // end for
   
   	// Invariant: id was not found, so return null.
   	return null;
   } // end find
   

4. • Part A:
     1. d) There is a catch clause for ArithmeticException in m3.
     2. b) There is no catch for ArrayIndexOutOfBoundsException in m3, so we check the method that called it (m1). There is a catch for ArrayIndexOutOfBoundsException in m1, so it is caught in m1.
     3. 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).
   • Part B: Loop invariant: 1 <= i <= n and fact = i!
5. • Part A:

     // constructor: 
     // enforces class invariant: the attribute faceValue must be between 1 and 6 inclusive, 
     // and uses a default value of 1 if the given value is out of range.
     public Die (int value)
     {
     	if (value >= 1 && value <= 6) {
     		this.faceValue = value;
     	}
     	else {
     		this.faceValue = 1;
     	}
     }
     

   • Part B
     1. 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.)
     2. 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.
   • • a) head -> 70 -> 80 -> 90 -> 99 -> 100 -> null (each node has item field storing the integer value, and next field referencing the next node in the linked list)
     • b)

       /**
        * insertSortedNoDuplicates: a ListReferenceBased method which inserts a given object into a sorted list, and keeps it sorted.
        * @param item the Object to insert
        * @return none
        */
       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 checks if the given item exists in this list.
        * @param item the Object to search for
        * @return true if the item is in this 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