CS 455 Midterm 2 Solution

Problems 1 through 4

Correct solution shown on your exam.

Problem 5.1 (many correct answers)

The contents of the file:

A
B
C
D

The file "data" does not exist

Error #3
Max line length is 0

6.1. target = Mike
Marie, Saul, Mike
6.2. target = Lydia
Marie, Gus, Hank, Jesse
6.3. target = Walter
Marie, Saul, Skyler, Walter

(a second solution accepted: algorithm used consistently goes right of middle when there is an even number of items)

Problem 7.1

Returns true iff str is a single-word palindrome (i.e, reads the same forwards and backwards).

Problem 7.2 New code shown in bold below.

public static boolean mystery(String str) {  
   Stack stack = new Stack();
   int loc = str.length() / 2;
   for (int i = 0; i < loc; i++) {
      stack.push(str.charAt(i));
   }
   
   if (str.length() % 2 == 1) {  // if there are an odd number of chars
      loc++;                     // move loc past the middle element
   }
   
   for (int i = loc; i < str.length(); i++) {
      if (str.charAt(i) != stack.peek()) {
        return false;
      }
      stack.pop();
   }
   return true;
}

public static void nickNamer(ArrayList<String> names) {

    names.replaceAll(new Terminator());

}

class Terminator implements UnaryOperator<String> {

   public String apply(String name) {
      return "The " + name + "-inator";
   }

}

Solution 1:

// PRE: all the values in nums are > 0
public static int numDouble(int [] nums) {
   return numDoubleR(nums, 0);
}

private static int numDoubleR(int[] nums, int start) {
   if (start == nums.length) {
      return 0;
   }
   if (isDoubleDigit(nums[start])) {     
      return 1 + numDoubleR(nums, start + 1);    
   }
   else { 
      return numDoubleR(nums, start + 1);
   }
}

private static boolean isDoubleDigit(int num) { 
   return (num < 100) && (num % 11 == 0);
}

Solution 2: Tail-recursive; another way of doing isDoubleDigit

public static int numDouble(int [] nums) {
    return numDoubleR(nums, 0, 0);
}

private static int numDoubleR(int[] nums, int start, int count) {
   if (start == nums.length) {
      return count;
   }
   if (isDoubleDigit(nums[start])) {
      count++;
   }
   return numDoubleR(nums, start + 1, count);
}

private static boolean isDoubleDigit(int num) { 
   return (num % 10 == num / 10);   // (e.g., 388: (8 != 38) correct result)
}