Exercises - Review T1

  1. Find the cost function C(n), and its tilde approximation, for the primitive operations of interest specified the code snippet below.

    int count = 0;
    for (int i = 2; i < 2*n; i++)
      for (int j = i; j < n; j++)
        something(); // <-- primitive operation of interest
    

    As $i$ takes on the values $2,3,4,\ldots,(2n-1)$, we go through the following numbers of $j$ values: $$(n-2),(n-3),\ldots,2,1,0,0,\ldots,0$$ Thus the primitive operation of interest happens $$(n-2) + (n-3) + \cdots + 2 + 1 \, \textrm{times}$$ This, being the sum of an arithmetic series, is given by $$C(n) = \cfrac{(n-1)(n-2)}{2} \sim \frac{n^2}{2}$$

  2. Find the cost function C(n), and its tilde approximation, for the primitive operations of interest specified the code snippet below. You may assume $n = 3^m$ for some positive integer m.

    int count = 0;
    for (int i = n/2; i < n; i++)
      for (int k = 1; k < n; k *= 3)
        something(); // <-- primitive operation of interest
    

    Note $n = 3^k$ must be odd. As the n/2 involves "integer division", the first value of $i$ is actually $(n-1)/2$. Thus, the outer loop happens $n-(n-1)/2 = (n+1)/2$ times. The inner loop happens $\log_3 n$ times, so $$C(n) = \left( \frac{n+1}{2} \right) \log_3 n \sim \frac{n \log_3 n}{2}$$

  3. Based on the table below, if $C(n) \sim kn^m$, what is a reasonable guess for the value of $m$?

    $\displaystyle{\begin{array}[t]{|c|c|c|}\hline n & C(n) & C(2n)/C(n)\\\hline 4 & 10 & 5.2\\\hline 8 & 52 & 6.82\\\hline 16 & 355 & 7.51\\\hline 32 & 2663 & 7.84\\\hline 64 & 20881 & 7.913\\\hline 128 & 165228 & 7.9865\\\hline 256 & 1319597 & ⋮ \\\hline \end{array}}$

    As the values of $C(2n)/C(n)$ seem to be getting arbitrarily close to $8 = 2^3$ as $n$ increases, a good guess based on the information given would be $m=3$.

  4. Use a stack to decide if the delimiters below properly match or not. Show the state of the stack after each push or pop is performed, and indicate what should be concluded when the algorithm terminates.

    { [ ( { a b } ) ] [ c ] ( [ d f ) ] }

    {         (note: as drawn here, the stack "grows" to the right)
    { [
    { [ (
    { [ ( {
    { [ (
    { [
    { 
    { [
    {
    { (
    { ( [
    { (    at which point the popped "[" doesn't match
           the corresponding delimiter found in the expression (a ")")
    
  5. Use a stack to evaluate the postix expression below. Show the state of the stack after each value or operator is read, and then indicate the value for the expression produced.

    2 3 4 + 5 6 7 - * + +

    2        (note: as drawn here, the stack "grows" to the right)  
    2  3
    2  3  4
    2  7
    2  7  5
    2  7  5  6
    2  7  5  6  7
    2  7  5 -1
    2  7 -5
    2  2
    4     ---> so the expression evaluates to 4
    
  6. Use two stacks to evaluate the fully parenthesized infix expression below. Show the state of both stacks after each value, operator, or parenthesis is read, and then indicate the value for the expression produced.

    ( 9 + ( ( 4 + 3 ) * ( 7 - 8 ) ) )

    operand stack          operator stack
    : 9                    :
    : 9                    : +
    : 9  4                 : +
    : 9  4                 : + +
    : 9  4  3              : + +
    : 9  7                 : +
    : 9  7                 : + x
    : 9  7  7              : + x
    : 9  7  7              : + x -
    : 9  7  7  8           : + x -
    : 9  7 -1              : + x
    : 9 -7                 : +
    : 2                    :          ---> so the expression evaluates to 2
    
  7. Use the Shunting Yard Algorithm to convert the partially-parenthesized infix expression below. Show the state of the postfix expression being generated, the stack, and the remainder of the expression, as each token is "processed" from left to right.

    A + B / C * ( D - A ) ^ F ^ H

    A      +B/C*(D-A)^F^H
    ---------------------
       |
       
    A      B/C*(D-A)^F^H
    --------------------
       |+
       
    AB      /C*(D-A)^F^H
    --------------------
        |+
    
    AB      C*(D-A)^F^H
    -------------------
        |/
        |+
    
    ABC      *(D-A)^F^H
    -------------------
         |/
         |+
    
    ABC/      (D-A)^F^H
    -------------------
          |*
          |+
    
    ABC/      D-A)^F^H
    ------------------
          |(
          |*
          |+
    
    ABC/D      -A)^F^H
    ------------------
           |(
           |*
           |+
    
    ABC/D      A)^F^H
    -----------------
           |-
           |(
           |*
           |+
    
    ABC/DA      )^F^H
    -----------------
            |-
            |(
            |*
            |+
    
    ABC/DA-      ^F^H
    -----------------
            |*
            |+
    
    ABC/DA-      F^H
    ----------------
            |^
            |*
            |+
    
    ABC/DA-F      ^H
    ----------------
             |^
             |*
             |+
    
    ABC/DA-F      H
    ----------------
             |^
             |^
             |*
             |+
    
    ABC/DA-FH      
    ----------------
               |^
               |^
               |*
               |+
               
    now pop the whole stack to finish:
    
    The postfix form is: ABC/DA-FH^^*+      
    
  8. Use a stack and backtracking to find two solutions to the problem of placing 5 queens on a 5 x 5 chess board so that no queen can attack any other. Show the state of the stack with each queen placement attempted.

    We place column numbers $0$ to $4$ on the stack as we place queens in rows $0$ to $4$, as shown below:

    : 0
    : 0 2
    : 0 2 4
    : 0 2 4 1
    : 0 2 4 1 3    ---> 1st solution
    : 0 2 4 1
    : 0 2 4
    : 0 2
    : 0
    : 0 3
    : 0 3 1
    : 0 3 1 4
    : 0 3 1 4 2    ---> 2nd solution
    
  9. Consider the following code:

    import java.util.Iterator;
    
    public class ThingyMebob {
        
        Thing[] things;
        
        public ThingyMebob() {
            things = new Thing[10];
        }
        
        public Iterator iterator() {
            return _______________ {
                int pos = things.length-1;
                public boolean hasNext() {
                    return pos >= 0;
                }
                
                public Thing next() {
                    pos--;
                    return things[pos+1];
                }
            };
        }
        
        public void fill(Thing[] things) {
            for (int i =0; i < 5; i++)
                this.things[i] = things[i];
        }
        
        public static void main(String[] args) {
            ThingyMebob bob = new ThingyMebob();
            String[] strs = {"a","b","c","d","e"};
            bob.fill(strs);
            for (String string : bob) 
                System.out.print(string);
        }
    }
    
    1. What code must be added in the blank to support for-each loops like the one in main?

    2. In addition to the code that must be added in the given blank addressed in the previous question, there are two other errors in the code above. Describe them both.

    1. new Iterator()

    2. The class should implement the Iterable interface, so add "implements Iterable" after "public class ThingyMebob".

      Also, generic array creation is not allowed in Java, so change "things = new Thing[10];" to "things = (Thing[]) (new Object[10]);"

  10. What method(s) does a class guarantee exist(s) if it implements the Iterable<Item> interface? ..what is the return type of this method?

    iterator(), which has a return type of: Iterator<Item>

  11. Two methods must be written for a class to implement Iterator<Item>. What are they? ..and what are their respective return types?

    hasNext() and next(), which have return types boolean and Item, respectively

  12. Suppose you see a line of code begin with <return new Bunch()> ...:

    1. What would tell you (and the compiler) that you should expect the definition of an anonymous inner class to come next?

    2. What is the very next non-whitespace character after the two parentheses that you should expect if an anonymous inner class is coming next?

    1. Knowing that Bunch is the name of an interface would suffice.

      Interestingly, Bunch being the name of an abstract class would also give you this expectation. Note that neither interfaces nor abstract classes can be "constructed" in and of themselves -- they need some concrete class that implements or extends them.

    2. A curly-brace, "{"

  13. The following letters, in the order they appear, are enqueued into a newly constructed queue implemented using an array. Dashes will cause a dequeue. The underlying array doubles in size when the enqueued character would fill the array and halves its size when a dequeue would leave it one-quarter full. Trace the state of the internal array that results. (Indicate null entries in the array with a period.)

    A B C D - E F - - G H I - - - -

    A  .                     // double size when one short of full
    A  B  .  .
    A  B  C  .
    A  B  C  D  .  .  .  .
    .  B  C  D  .  .  .  .   // leave rest of array in place on dequeue
    .  B  C  D  E  .  .  .
    .  B  C  D  E  F  .  .
    .  .  C  D  E  F  .  .
    .  .  .  D  E  F  .  .
    .  .  .  D  E  F  G  .
    .  .  .  D  E  F  G  H   
    I  .  .  D  E  F  G  H   // wrap tail around
    I  .  .  .  E  F  G  H
    I  .  .  .  .  F  G  H
    I  .  .  .  .  .  G  H   // halve size when 1/4 full
    H  I  .  .
    
  14. Suppose the integers 0 through 9 are pushed, in order, onto a stack. The stack is then popped until it is empty, with the result of each pop immediately enqueued in an initially empty queue. Finally, the queue is dequeued until it is empty, printing each value dequeued in the order it is dequeued. What prints as a result?

    The numbers leave the stack in reverse order, while the queue leaves this order unchanged. So the following would be printed:

    9 8 7 6 5 4 3 2 1 0

  15. Assuming q below is an initially empty queue of integers, show the state of the queue after this code fragment executes. (Make sure to indicate the head and tail of the queue.). You may assume the method sumOfDigits(int n) returns the sum of the digits of n.

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    q.enqueue(4);
    q.enqueue(5);
    
    for (int i = 0; i < 4; i++)
      int a = q.dequeue();
      int b = q.dequeue(); 
      q.enqueue(a+b);
      q.enqueue(sumOfDigits(a+b))
    }
    

    The queue after the code above executes looks like this:

    (Head) 7 8 8 10 1 (Tail)

    To understand why, consider the state of the queue after each pass through the loop, as shown the below (the head is always on the left side, and the tail on the right):

    1 2 3 4 5
    3 4 5 3 3
    5 3 3 7 7
    3 7 7 8 8
    7 8 8 10 1
    
  16. Suppose a queue is implemented with an array. Why does one keep track of the position of the head of the queue? Why not always insist the head of the queue is at the beginning of the array (i.e., at index 0)?

    So we don't have to make so many copies to move every element in the queue forward

  17. What's the cost function $C(n)$, associated with the array accesses (i.e., getting or assigning a value) resulting only from the array resizing in pushing n items onto a stack implemented with an array (initially of size 1) whose size is increased by a factor of 5 every time it gets full? For ease of analysis, you may assume that $n=5^k$ for some positive integer $k$.

    Let $S$ be the number of copies made during resizing. Then

    $$\begin{array}{rclllllll} 5S &=& & & 5 + & 5^2 + & ... + & 5^{k-1} + &5^k\\ S &=& 1& + & 5 + & 5^2 + & ... + & 5^{k-1} \end{array}$$ Subtracting these, we have $$4S = 5^k - 1$$ So, $$\begin{array}{rcl} C(n) &=& 2*(5^k - 1)/4 \hspace{.1in}\textrm{doubled as each copy requires 2 array accesses}\\ &=& (5^k - 1)/2\\ &=& (n - 1)/2 \end{array}$$
  18. Bob finds he needs to store ordered pairs of various types of things for a given program (e.g., pairs of int values, of double values, of String objects, etc. Alice writes a OrderedPair class that she knows will work. Bob trusts her, but decides to test her OrderedPair class anyways -- so he writes the OrderedPairTest class below. He expects the indicated output, but keeps getting errors when he tries to run his class.

    public class OrderedPairTest {
    	
       public static void main(String[] args) {
    		
          OrderedPair<String> pair1 = new OrderedPair<String>("alice","bob");
          OrderedPair<int> pair2 = new OrderedPair<int>(5,7);
          OrderedPair<double> pair3 = new OrderedPair<double>(1.3,2.4);
    		
          System.out.println(pair1);
          System.out.println(pair2);
          System.out.println(pair3);
       }  
    }
    

    Expected Output:

    (alice,bob)
    (5,7)
    (1.3,2.4)
    
    1. What is the source of his errors -- what did he do incorrectly?

    2. Alice is irritated that Bob didn't trust her and consequently deletes her OrderedPair code from his machine before he had a chance to fully understand it. So Bob now has to write that class too. He sketches out as much as he remembers (see below), but knows there are several errors or missing elements. Finish his sketch of the OrderedPair class below so that when OrderedPair is used with Bob's test code above (after corrections), the expected output will be produced.

      public class OrderedPair {
      	
         x,y;
      	
         public OrderedPair(x, y) {
            //???
         }
      	
         public String toString() {
            return ("(" + x + "," + y + ")");
         }
      }
      
  19. There are two errors present in the code below. Find them!

    The class described is meant to work as a linked list that maintains a reference only to its head node. (Note, the fact that the class does not not maintain a reference to its tail is intentional, and should not be considered an error.)

    The addLast() method is intended to add the item specified to the tail of the linked list.

    public class LL {
        
        private class Node {
           Item item;
           Node next;
        }
        
        Node first;
        
        public void addLast(Item item) {
           Node newEnd = new Node();
           newEnd.item = item;
           newEnd.next = null;
           
           if (first == null)
             first = newEnd;
           else {
             Node tmp = first;
             while (tmp != null)
               tmp = tmp.next;
             tmp.next = newEnd;
           }
        }
    }
    

    First Error: Missing generic type parameter at top (i.e., LL)
    Other Error: In the while loop, the condition should be (tmp.next != null)