CS 455 Midterm 1 Solution

Part A. x

Part B. a

Problem 2

Part A. n

Part B. O(n^2)

Problem 3
Part A. O(n log n)

Part B. get the entrySet() and iterate over it; that's O(n)

Problem 4

school
no such entry
school
no such entry

Problem 5

A. 6, 7
B. 9, 6
C. y
D 6, 12
E. 23, 24

Problem 6
There were several versions of correct logic to get the same effect. (Changes shown in bold)

public static void paintItRed(Color[][] image, int row, int col) {

   if (!inRange(image, row, col)) {
      return;       // we're not in bounds of the image
   }
 
   if (image[row][col].equals(Color.BLACK)) { 
      return;       // we've hit the edge of the region
   }

   
   if (image[row][col].equals(Color.RED)) {  
      return;      // we've already been here
   }
   

   image[row][col] = Color.RED;

   // recursively call paintItRed on the neighbors of (row, col)
   for (int rowOffset = -1; rowOffset <= 1; rowOffset++) {
      for (int colOffset = -1; colOffset <= 1; colOffset++) {

         if (!(rowOffset == 0 && colOffset = 0)) { // don't call it with same params
            paintItRed(image, row + rowOffset, col + colOffset);
         }

      }
   }
}

Problem 7 Solution shown in bold.

static void sortByDistance(ArrayList<Point> points, Point target) {

   Collections.sort(points, new DistanceComparator(target));

}


class DistanceComparator implements Comparator<Point> {

   public int compare(Point a, Point b) {

      return (int) (a.distanceSq(target) - b.distanceSq(target));
   }

   public DistanceComparator(Point target) {
      this.target = target;
   }

   private Point target;
}

// Solution 1 (no helper function necessary) 
public static int num3s(int num) {

   if (num == 0) { return 0; }

   int count = 0;
   if (num % 10 == 3) { count++; }

   return count + num3s(num / 10);
}


// Solution 2 (tail-recursive solution) 
public public static int num3s(int num) {
   return num3sR(num, 0);
}

// num3sR returns the sum of count and the number of 3's in num
public public static int num3sR(int num, int count) {

   if (num == 0) { return count; }

   if (num % 10 == 3) { count++; }

   return num3s(num / 10, count);
}