EXAM 1 SAMPLE ANSWERS - "+" version

1. (a) log 128 - log 4 = 5
          2         2
   (b) return location to calling method, parameters, local variables
   (c) O(log n), O(n), O(1), O(n) 
   (d) Scanner scan = new Scanner(System.in);
       System.out.println("Input a channel number: ");
       int channel;
       try {
           channel = scan.nextInt();
           if (channel < 2 || channel > 200)
               channel = 200;
       }
       catch (InputMismatchException e) {
           channel = 200;
       }

2. (a) O(n log n)
   (b) O(n^2)       ^ means exponentiation here
   (c) O(m^2)
   (d) O(m)
   (e) O(n^4)
   (f) O(1)

3. (a) 2, C, D, 68
   (b) Since strings are immutable, concatenation of strings causes a
       new string to be created each time. StringBuilder just adds
       on new characters without creating new strings every time,
       similar to the action of an ArrayList.
   (c) Find c > 0, n > 0 where cn^2 > (1/2)n^2 - (1/2)n
       c > (1/2) - (1/2n)
       Choose n = 2, so c = 1/4.
       Since (1/4)n^2 > (1/2)n^2 - (1/2)n for n > 2, (1/2)n^2 - (1/2)n = O(n^2).

4. (a) int[] temp = new int[intArray.length*2];
       for (int i = 0; i < numElements; i++)
           temp[i] = intArray[i];
       intArray[i] = temp;
   (b) for (int i = 0; i < numElements; i++) 
           if (intArray[i] == element) return;
       if (numElements == intArray.length) reallocate();
       intArray[numElements] = element;
       numElements++;
   (c) 60
   (d) worst case O(n): search whole array but don't find element
   (e) best case O(1): find element in first position, return immediately
       
5. (a) this.hr - otherTime.hr
       this.min - otherTime.min
       0
   (b) c
   (c) Time max = t.get(0);
       for (int i = 1; i < t.size(); i++)
           if (t.get(i).compareTo(max) > 0)
               max = t.get(i);
       return max;
   (d) O(n), logical error, O(n^2), exception

6. (a) pop O(n), push O(1), peek O(1), isEmpty O(1)
   (b) (stack shown sideways)
       5
       5 4
       9
       9 3
       9 3 8
       9 3 8 7
       9 3 1
       9 3
       3
   (c) Postfix: 9 5 4 3 * + / - 8 7
       Stack (shown sideways, bottom to top): + / ( *
   (d) LIFOStack<E> temp = new ListStack<E>();
       int counter = 0;
       while (!s.isEmpty()) {
           temp.push(s.pop());
           counter++;
       }
       while (!temp.isEmpty())
           s.push(temp.pop());
       return counter;

7. (a)
   k loop runs from i to j. Minimum value of i is 0, maximum value of j is 
   n-1, so k loop runs O(n) at worst. i and j loops run O(n^2) time (since the
   number of times j runs depends on i and yields n + n-1 + ... + 2 + 1 = 
   O(n^2). So total time for algorithm is O(n^3).
   (b)
   x[i..p] = x[i..j] + x[j+1..p].
   Since x[i..j] < 0, x[i..p] < x[j+1..p].
   Thus, x[i..p] can't be a maximum since it is less than some other sum.

8. (a)
   Node<E> newNode = new Node<E>(element);
   if (head == null) {
      head = newNode;
      tail = newNode;
   }
   else {
      newNode.next = head;
      head = newNode;
   }

   (b) 
   Node<E> ref = head;
   int count = 0;
   while (ref != null) {
      count++;
      ref = ref.next;
   }
   return count;
 
   (c)
   if (head == null) return null;
   E result = tail.data;
   tail.data = head.data;
   head = head.next;
   if (head == null) tail = null;
   return result;