EXAM 1 SAMPLE ANSWERS - "*" version

1. (a) log 64 - log 4 = 4
          2         2
   (b) return location to calling method, parameters, local variables
   (c) O(n), O(log n), O(n), O(1) 
   (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 = 2;
       }
       catch (InputMismatchException e) {
           channel = 2;
       }

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

3. (a) C, 2, 68, D
   (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) 80
   (d) best case O(1): find element in first position, return immediately
   (e) worst case O(n): search whole array but don't find element
       
5. (a) this.hours - otherTime.hours
       this.minutes - otherTime.minutes
       0
   (b) a
   (c) Time min = t.get(0);
       for (int i = 1; i < t.size(); i++)
           if (t.get(i).compareTo(min) < 0)
               min = t.get(i);
       return min;
   (d) O(n^2), exception, O(n), logical error

6. (a) pop O(n), push O(1), peek O(1), isEmpty O(1)
   (b) (stack shown sideways)
       8
       8 4
       12
       12 3
       12 3 7
       12 3 7 5
       12 3 2
       12 6
       2
   (c) Postfix: 9 1 3 4 * + 5 - 8 2
       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..q] = x[i..j] + x[j+1..q].
   Since x[i..j] < 0, x[i..q] < x[j+1..q].
   Thus, x[i..q] 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;