Spring 2023 [Bono]

CS 455 Midterm 2 Solution

Problem 1.    Queue


Problem 2.    Question: big-O of ops of Stack using an AL representation where the front of the AL is the top of the Stack

Answer: push and pop are each O(n); top and isEmpty are each O(1)


Problem 3 There are two main solutions students gave that work in O(n log n), although many students left out a critical step on the second solution.

Solution 1.

  1. use mergesort on each of the arrays. time for this step: O(n log n)
  2. merge the two sorted arrays together, but for the case in the loop where the elements from each array are the same, print out the value. Time for this step: O(n)

Solution 2.

  1. use mergesort on the second array. time for this step: O(n log n)
  2. for each element in the first array: (loop body executes n times)
    1. use binary search to search for this element in the second (i.e., sorted) array. If it finds it, print it out. Time for each binary search: O(log n)
    Total time for step 2: O(n log n)


Problem 4

flabbergasted


Problem 5

Part A.

public static void sortByLength(ArrayList<String> words) {
   Colletions.sort(words, new LengthComp());
}

// auxiliary class:
class LengthComp implements new Comparator<String> {
   public int compare(String s1, String s2) {
      int diff = s1.length() - s2.length();
      if (diff != 0) { return diff; }
      return s1.compareTo(s2);
   }
}

Part B. O(n log n)


Problem 6


Problem 7
For parts A and B it's relevant that TimeOfDay overrides hashCode but doesn't override equals.

Part A.   it looks in the correct hash bucket but doesn't find this time in the chain, so it returns false (options: b, f)

Part B.   it creates a new entry with this time and event and adds it to the Map, and then returns null. (options: b, f)

Part C.  
This one was tricky.

No, they are not kept in order. While the method hashCode orders them by what time they occur, the final hash index used takes that value % HASH_SIZE (i.e., the size of the hash table) so that can change the order. E.g., HASH_SIZE = 16, and one TimeOfDay is 15 (min from midnight) and a later one is 17: the 17 will go in bucket 1, and the 15 will go in bucket 15. So, when we visit them by bucket number (i.e., array index) we will get to 17 before 15.
[Note: You didn't have to illustrate it with an example to get full credit.]

Part D.
It's not a flaw in the class, because all the information stored by the constructor and returned from the accessors are primitive types, and primitives have value semantics, so there is no possiblity of having two references to the same object.


Problem 8.
Solution in bold.

public class MyProg {
   public static void main(String[] args) {

      String fileName;  // define here so this variable is in scope for the try and catch clauses
      try {

         Scanner in = new Scanner(System.in);
         System.out.print ("Please enter a file name: ");
         String fileName = in.next();
         Data data = readfile(fileName); // note: this line can throw the exception
         data.process();
         data.printResults(System.out);

      catch (FileNotFoundException e) {
         System.out.println("ERROR: File does not exist: " + fileName);
         System.out.println("Exiting program.");
      }

   }


   public static Data readFile(String fileName) throws FileNotFoundException {
      Data data = new Data(); // create an empty data object
      File inFile = new File(fileName);
      Scanner fileScanner = new Scanner(inFile); // note: this line can throw the exception
      while (fileScanner.hasNextLine()) {
         data.add(fileScanner.nextLine());
      }
      fileScanner.close();
      return data;
   }
}


Problem 9
Several different correct solutions, the first one here is the most straightforward. This problem involves thinking recursively, and many students had trouble with it. Many solutions violated the problem restrictions, for example, including using loops and/or Java classes and methods.

Since some students attempted to get the MSD by computing the largest power of 10 of the number first, I am showing a correct recursive solution to do it that way here as well. (The code is somewhat longer than the first solution given.)

Solution 1

   public static void printDigits(int num) {
      if (num < 10) {
         System.out.print(num);
      }
      else {
         printDigits(num / 10);  // prints a comma-sep list of the number div 10
                                 // e.g., if num is 1234, will do printDigits(123), i.e., prints: "1,2,3"
         System.out.print("," + num % 10);  // and this prints ",4" to complete the output
      }
   }

Solution 2

   public static void printDigits(int num) {
      int pow = highestPower10(num, 1);
      printDigitsR(num, pow);
   }
   
   // if top-level call passes in 1 for pow,
   // returns the largest power of 10 <= num
   //  e.g., for 1234 returns 1000, for 25 returns 10
   private static int highestPower10(int num, int pow) {
      if ((num / pow) < 10) {
         return pow;
      }
      return highestPower10(num, pow * 10);
   }

   // prints all the digits of num, comma-separated
   // PRE: pow is the largest power of 10 <= num
   public static void printDigitsR(int num, int pow) {
      if (pow < 10) {
         System.out.print(num);
      }
      else {
         System.out.print(num / pow + ",");
         printDigitsR(num % pow, pow / 10);
      }
   }