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. 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) {
      
      }
      
          public void delete(int key) {
              if (head != null) {  // empty lists have nothing to delete
                  if (head == tail && head.value == key)) { // list of size 1
                      head = null;
                      tail = null;
                  }
                  else if (head.value == key) { // key at 1st
                      head = head.next;
                  }
                  else {
                      ListElem n = head;
                      
                      // now advance n until n.next.value == key...
                      while ((n.next != null) && (n.next.value != key)) {
                          n = n.next;
                      }
                      
                      // reroute to perform the deletion
                      if (n.next != null)
                          n.next = n.next.next;
                  }
              }
          }