Review Exercises (Set A2)

  1. Refer to the following 4 sequences as you answer questions (a) and (b) given below:

        I. 6 8 7 5 4 9 3 2 1
       II. 2 1 4 3 6 5 9 8 7
      III. 4 3 2 7 6 5 9 1 8
       IV. 1 2 3 4 5 6 7 8 9
    
    1. Suppose that an intermixed sequence of stack push and pop operations are performed.
      The pushes push the integers 1 through 9 in order; the pops print out the return value.
      Which of the above sequences could not occur as the printed output?

    2. Suppose that an intermixed sequence of enqueue and dequeue operations on a queue are
      performed. The enqueue operations enqueue integers 1 through 9 in order; the dequeue
      operations print out the value dequeued. Which of the above sequences could
      not occur as the printed output?

  2. Name one advantage and one disadvantage of implementing a stack or queue using resizing arrays.

  3. Name one advantage and one disadvantage of implementing a stack or queue using linked lists.

  4. Use a stack to evaluate the postfix expression 1 3 2 * 4 5 + / 3 * -. Write the state
    of the stack after each operator is processed. To what value does the expression evaluate?

  5. In using the shunting yard algorithm to convert (A * B + C) * (( D ^ E * F) + G) from
    partially parenthesized infix form to postfix form, list the elements that are popped
    from the operand stack in the order they are popped.

  6. Below is a recursive method which uses a queue of integers:

    public static int mystery(int n) {
       if (n == 0)
          return 1;
       queue.enqueue(n);
       return mystery(n-1) * queue.dequeue();
    }
    
    1. Assuming the queue is initially empty, draw a snapshot of the queue after every enqueue
      and dequeue statement for each recursive call for mystery(4). Label each queue snapshot
      with the recursive call, and whether it was an enqueue or dequeue.

      For example, the following shows the first snapshot of the queue after the enqueue
      statement for the call mystery(4):

      mystery(4), insert : 4
    2. What does mystery(4) return as a value?

    3. More generally, for a given integer n >= 0, what does the method mystery calculate?

  7. Analyze the runtime of the following code snippets given an input size n. Find the
    cost function for each that counts the number of primitive operations performed. Also,
    indicate what this function is equivalent to using tilde notation. Lastly, cite what this
    cost function would be using Big-O notation. Assume that statements in the body of
    loops are a primitive operations, but the checking or update of any loop variables can be
    ignored (i.e., don't include statements making a comparison with, or updating the value of
    i or j in the cost function).

    1.  

      for (int i = 0; i < N; i++)
         for (int j = i; j < 3*N; j++)
            System.out.println("1 iteration executed!");
      
    2.  

      int sum = 0;
      for (int i = 1; i < N; i *= 2)
         for(int j = 0; j < i; j++)
            sum++; 
      
  8. The following code snippet consolidates the essential operations in pushing n integers
    to a stack using a resizing array. What is the runtime cost of this code in Big-O
    notation? You may assume that assigning a value to an array element and copying a value
    from one array to another are both primitive operations.

    int top = 0;                                             
    Integer[] stackArray = new Integer[1];                   
    for (int i = 0; i < n; i++) {                            
       if (i == stackArray.length) { 
           int oldLength = stackArray.length;
           int newLength = oldLength * 2;
           Integer[] newArray = new Integer[newLength];
           for (int j = 0; j < oldLength; j++) {
               newArray[j] = stackArray[j];
           }
           stackArray = newArray;
       }
       stackArray[top] = i;
       top++;
    }
    
  9. One can solve the N-Queens problem by implementing a backtracking algorithm using a
    stack. Show the values of such a stack after each push or pop operation for 5-Queens
    problem until the first two solutions are found. Indicate which stack states correspond
    to the solutions.

  10. Name two methods guaranteed to exist in any class that implements the Iterator
    interface.

  11. Explain why the code below to calculate the nth Fibonacci number is a bad idea?

    public static int fibonacci(int n) {
        switch (n) {
        case 0 : ; 
        case 1 : return 1;
        default : return fibonacci(n-1) + fibonacci(n-2);
        }
    }
    
  12. One can solve a maze by implementing a pathfinding algorithm using a queue or a stack.
    Using a queue search on the following maze (1's represent walls; 0's represent traversable
    areas; top left corner is the starting position; the bottom right corner is the finish),
    show the sequence of positions found by the pathfinding algorithm. Assume that when
    checking for valid "next" positions, one looks up, then right, then down, and then
    finally left -- in that order.

    0 1 0 1 1
    0 0 0 0 0
    0 1 0 1 1
    0 1 0 1 0
    0 0 0 0 0
    
  13. A double--ended linked list is a list that keeps a reference to both the head and tail
    element in the list. Use the structure of a list element and the (incomplete) list class
    given below by the following class definitions to answer the questions on the next page.

    public class ListElem {
       public int value;
       ListElem next; // "next" points to the successor
    }
    
    -----------------------------------------------------------------------
    
    public class List {
       public ListElem head; // "head" points to the first element in list
       public ListElem tail; // "tail" points to the last element in list
       
       public List() // Constructor {
          head = null; // Empty list
          tail = null;
       }
       
       //... other methods ...
       
    }
    
    1. Complete the method for the List class given below that inserts an ListElem object x before the head
      of the list. (Hint: don't forget to handle the case when the list is empty!)

      public void insertAtHead(ListElem x) {
      
      }
      
    2. Complete the method for the List class given below that deletes a ListElem object with a
      given key. If the key does not exist in the list, the method should not change the list.
      (Hint: don't forget to handle the case when the list is empty!)

      public void delete(int key) {
      
      }