CS 455 Midterm 2 Solution

Problem 1

Part A. O(n²)

Part C. O(n)
[you have to have part B at least close to corrrect to get credit for part C]

Part B. all the changes can be made in the helper function, addInstanceOf: (new code in bold).

private void addInstanceOf(String word) {

   Iterator> iter = concordMap.entrySet().iterator();

   boolean found = false;

   while (iter.hasNext() && !found) {

      Map.Entry entry = iter.next();

      if (entry.getKey().equals(word)) {

         entry.setValue(entry.getValue() + 1);
         found = true;
      }
   }

   Integer count = concordMap.get(word);

   if (!found) { (count == null) {

      concordMap.put(word, 1);

   }
   else {
      concord.put(word, count + 1);
   }
   
      
}

Problem 3
Part A. 2. the objects in the ArrayList

Part B. 3. neither

Problem 4 We'll show the answer on multiple lines here (on original problem you write them all on one line) such that letters on the same line have the same big-O:

fastest

B
F
C E G H
A
D

Problem 5    500

Problem 6 (Changes shown in bold)

public static void binSearchR(int[] vals, int target, int low, int high) {

   if low > high) {
      return -1;
   }
 
   int mid = (low + high) / 2;
   
   if (vals[mid] == target) {  
      return mid;
   }

   if (vals[mid] < target) {
      return binSearchR(vals, target, mid + 1, high);
   }

   return binSearchR(vals, target, low, mid - 1);
   
}

Problem 7
I reduced the point value of this problem to 16 points total. Many students decided that the whole file only had one sentence in it (the precondition does not state that). That simplifies the problem a bit, so I reduced the total points for this problem such that a smaller portion of points are allocated to the first loop (~5 points), and we did not take off very much for not stopping that loop you when reach a word that ends with a period (-2).

Some other issues with some solutions:

• The Stack is the only place you need to ever save the whole sentence. Some students had one (or more!) of the following in addition to the Stack: a String version of the original sentence, an AL or array of all the words in the sentence, a String of the reversed version of the sentence. We did not take off points for this, but we might do so on a final exam problem. The issue isn't so much a waste of space, but a waste of time copying the data to different places, and in some cases unnecessarily complicating the code.

• Another issue that came up occasionally is students writing unnecessarily complex (or incorrect) code because of unfamiliarity with Java methods and classes. Sometimes it might even involve methods described right on the code handout (make sure you take advantage of that resource). Remember there are a few commonly used methods you need to know for exams (see Sample Exams page for details).

There are several versions of a correct solution. E.g., variants in loop logic; push the last word as-is and strip the period off when you pop it; strip the period before you push it; or this one, where we don't even push the last word. Here is one correct solution:

//  Prints out a version of a sentence read from the given scanner such that
//  the order of words is reversed. A sentence has one or more words and is 
//  terminated with a period.
//  All output will be on one line (i.e., no newlines printed).
//  PRE: the next sequence of characters on the scanner is a sentence. 
public static void printReversedSentence(Scanner in) {
     
   Stack<String> s = new Stack<>();
   
   String word = in.next();      
      
   while (word.charAt(word.length()-1) != '.') {
      s.push(word);
      word = in.next();  
   }
      
                      // take period off last word and print it first
   System.out.print(word.substring(0, word.length()-1));
   
   while (!s.empty()) {        // no "." words are on the stack  
      System.out.print(" " + s.pop());         
   }
      
   System.out.print(".");
    
}