CS 455 Midterm 2 Solution

Problem 2.    Queue

Problem 3
Part A.   [5, 7, 54] [5, 7, 54] [5, 7, 54]

Part B.   [3, 5, 7, 54] [3, 5, 7] [5, 7, 54]

Problem 4
Because a Set is organized internally by the values it contains, changing a value while iterating would invalidate the set.

Alternate solution: Because a Set is not allowed to have duplicate elements, and changing a value while iterating could introduce a duplicate.

Problem 5
This would not work as a hash function because calling it more than once with the same key will result in different hash codes.

Problem 6

Part A.   O(scores.size() * maxScore)

Part B.   Solution in bold.

public static int[] getCounts(ArrayList scores, int maxScores) {

   int[] counts = new int[maxScore+1]; // all values init'd to 0
   
   for (int i = 0; i < scores.size(); i++) {
      
      for (int score = 0; score <= maxScore; score++) {
         if (scores.get(i) == score) {
            counts[score]++;

            counts[scores.get(i)]++;
 
         }
      }
       
   }
   return counts;
}

Problem 7.

public static void reportMisspellings(Scanner in, Set<String> dictionary) {
   TreeMap<String, Integer> mistakes = new TreeMap<>();
   while(in.hasNext()) {
      String word = in.next();
      if(!dictionary.contains(word)) {
         Integer numTimes = mistakes.get(word);
         if(numTimes == null) {
            mistakes.put(word, 1);
         }
         else {
            mistakes.put(word, numTimes+1);
         }
      }
   }
   printMisspellings(mistakes);
}

Part A.

Answer: 32

Part B.

File not found.

35
50
27
Answer: 50

35
Oops!
Answer: 35

Solution with 3-arg helper (tail recursive):

// PRE: nums.length > 0
public static int min(int[] nums) {
   return minR(nums, 1, nums[0]);
}

// minR: finds the minimum of minSoFar and the values in positions
//       [start, nums.length-1] in nums
// PRE: 0 <= start <= nums.length 
private static int minR(int[] nums, int start, int minSoFar) {
   if (start == nums.length) { // 0-element range, so minSoFar is the smallest
      return minSoFar;
   }
   if (nums[start] < minSoFar) { // check if current value is less than min
      minSoFar = nums[start];        // if so, it becomes the min value so far
   }
   return minR(nums, start + 1, minSoFar);  // return the min of minSoFar
                                            // and the rest of the array
}

Solution with 2-arg helper:

// PRE: nums.length > 0
public static int min(int[] nums) {
   return minR(nums, 0);
}

// minR: finds the minimum value in positions [start, nums.length-1] in nums
// PRE: nums.length > 0 and 0 <= start < nums.length 
int minR(int[] nums, int start) {
   if (start == nums.length-1) {  // 1-element range so return that value
      return nums[start];
   }
   int minRest = minR(nums, start + 1); // find the min of the rest of the array
   if (nums[start] < minRest) {  // return the min of this value and min of the rest
      return nums[start];
   }
   return minRest;
}