Spring 2024 [Bono]

CS 455 Midterm 2 Solution


Problem 1 The groups below correspond to: O(1), O(log n), O(n) O(n log n), O(n2) 
(C H) (J) (A D F G I) (B) (E)


Problem 2

Returns true if and only if the specified string, str, . . .

consists wholly of 0 or more a's followed by the same number of b's.


Problem 3

Part A. Many correct solutions. 

 3  5

Part B. Depends on answer to part A. 
 4.0

Part C.

File data does not exist in the directory we're running the program in.


Part D. 

Error C
8.0


Part E. Many correct solutions. 

x


Problem 4 

updateAll(myList, new ZeroEven());

class ZeroEven implments UnaryOperator<Integer> {

   public Integer apply(Integer elmt) {
      if (elmt % 2 == 0) { return 0; }
      return elmt;
   }

}

Problem 5

Part A. 

public static ArrayList<Integer> getKeysWithValue(int val, Map<String, Integer> map) {
         
   ArrayList<String> result = new ArrayList<>();

   for(Map.Entry<String, Integer> entry: map.entrySet()) {
      if (entry.getValue() == val) {
         result.add(entry.getKey());
      }
   }

   return result;
         
}

Part B.

O(n)    [correct answer depends on the code written in Part A]


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

Solution 1. No-helper-function solution. This one is O(n2) time, since it makes repeated calls to substring to do the recursion and repeated calls to "+" to build up the result. Note: Calls to substring and "+" were explicitly allowed on the exam. 

   public static String removeXs(String str) {
         
      if (str.isEmpty()) { return str; }

      if (str.charAt(0) == 'x') {
         return removeXs(str.substring(1));
      }

      return str.charAt(0) + removeXs(str.substring(1));

   }
Solution 2. Tail-recursive solution with a helper function and no call to substring. Still O(n2) because you are creating a new string on every call. You can do it in O(n) time if you use a StringBuilder (a mutable string type) instead for soFar parameter and return type, and then convert it back to a String in the top-level function. 
   public static String removeXs(String str) {

      return removeXsH(str, 0, "");
   }

   // Let's call noX a version of str.substring(start) without x's:
   // returns soFar with noX appended to it
   public static String removeXsH(String str, int start, String soFar) {

      if (start == str.length()) { return soFar; }

      if (str.charAt(start) != 'x') {
         return removeXsH(str, start + 1, soFar + str.charAt(start));
      }

      return removeXsH(str, start + 1, soFar);
         
   }