Fall 2023 [Bono]

CS 455 Midterm 2 Solution


Problem 1
  1. O(log n)
  2. O(n)
  3. O(n)
  4. O(log n)
  5. O(n)
  6. O(n)
  7. O(n log n)
  8. O(1)
  9. O(1)
  10. O(n)
  11. O(1)
  12. O(n)


Problem 2 Many correct variants on code to illustrate.

Digits is not immutable.
Code to illustrate this: 

   Digits dig = new Digits(123);
   System.out.println(dig.getDigit(0));  // 1
   dig.getDigits().set(0, 9);
   System.out.println(dig.getDigit(0));  // 9

Problem 3
Two main variants: one that inits cursor to -1, another that inits it to 0. Solution shown in bold. 
public class ALIterator {

   ArrayList<Integer> list;
   int cursor;

   public ALIterator(ArrayList<Integer> list) {

      this.list = list;
      cursor = 0;

   }

   public boolean hasNext() {

      return cursor < list.size();

   }

   public Integer next() {

      if (!hasNext()) { throw new NoSuchElementException(); }
      cur++;
      return list.get(curr-1);

   }
}

Problem 4
c. The client can avoid this exception.


Problem 5
Part A [2].
The Student class is missing a definition for hashCode()

Part B [2].
b. Because equals is overridden from the Object class.


Problem 6

A1. 4
A2. Mona (Many correct answers.)

B1. 2
B2. John (Many correct answers.)

C1. 4
C2. Paulie (Four possible correct answers.)

D1. 1
D2. Junior


Problem 7   Several variations on how to solve this. We'll show two here.

Solution 1. No-helper-function solution. This one is O(n^2), since it makes repeated calls to substring to do the recursion (but calls to substring were explicitly allowed on the exam). 

   public static int abCount(String str) {

      if (str.length() < 2) { return 0; }
      if (str.substring(0, 2).equals("ab")) {
         return 1 + abCount(str.substring(2));
      }
      return abCount(str.substring(1));

   }
Solution 2. Tail-recursive solution with a helper function. (You can also make a 2-arg helper, that accumulates the count on the way back, like the previous solution does.) 
   public static int abCount(String str) {

      return abCountR(str, 0, 0);
   }

   private static int abCountR(String str, int start, int countSoFar) {
      if (start + 1 >= str.length()) { return countSoFar; }
      if (str.substring(start, start + 2).equals("ab")) {
         return abCountR(str, start + 2, countSoFar + 1);
      }
      return abCountR(str, start + 1, countSoFar);

   }