CS 112 Summer 2017-- Homework Four Solutions to Part A

 

Part A: Analytical Problems (20 points)

  1. Manipulating a stack

    Given the following stack, depicted here from top to bottom:

    +   +
    | 6 |
    | 8 |
    | 1 |
    | 3 |
    | 7 |
    +---+
    

    What would the stack look like after the following sequence of pushes and pops?

    pop();
    push(2);
    push(9);
    push(0);
    pop();
    push(7);
    
    Solution:  From left to right:
    
    | 7 3 1 8 2 9 7 
                      
  2. Manipulating a queue

    Given the following queue, depicted here from the back of the queue (left) to the front (right):

    +-------------------+
    | 3 | 8 | 1 | 5 | 2 |
    +-------------------+
    

    What would the queue look like after the following sequence of enqueues and dequeues?

    dequeue();     // assume you simply throw away the value after dequeueing it
    dequeue();
    enqueue(9);
    enqueue(3);
    dequeue();
    
    Solution:
    
    3  9  3  8   
    
    
  3. Manipulating a priority queue

    Given the following MaxQueue, depicted here from the back of the queue (left) to the front (right):

    +-------------------+
    | 1 | 4 | 6 | 7 | 9 |
    +-------------------+
    

    Assuming that items in this priority queue are kept in max order, such that larger items leave the queue before smaller items, what would the queue look like after the following sequence of enqueues and dequeues?

    getMax();         // assume you simply throw away the value after dequeueing it
    insert(5);
    getMax();
    insert(12);
    insert(2);
    getMax(); 
    
    Solution: 
    
    1  2  4  5  6    
  4. Suppose a number of pop() and push() operations are performed on a stack S. The push() operations put the integers 0 through 9 onto S in order, and the pop() operations print the return value. That is, the sequence looks like this:
      push(0);
      Pop and print 0 or more times;
      push(1);
      Pop and print 0 or more times;
      push(2);
      Pop and print 0 or more times;;
      ....
      push(9);
      Pop and print 0 or more times;
    Which of the following sequences could not occur as a result of such a sequence of stack operations (there may be more than one)?

    1. 9 8 7 6 5 4 3 2 1 0
    2. 8 7 6 5 4 3 2 1 0 9
    3. 4 3 2 1 0 5 6 7 8 9
    4. 4 6 8 7 5 3 2 9 0 1
     Solution: Only number 4 could not occur.  
        
        
  5. This problem considers the same problem as (5) but for MaxQueues. Suppose a number of insert() and getMax() operations are performed on a MaxQueue M. The put() operations put the integers 0 through 9 onto M in order, and the getMax() operations print the return value. That is, the sequence looks like this:
      insert(0);
      getMax and print 0 or more times;
      insert(1);
      getMax and print 0 or more times;
      insert(2);
      getMax and print 0 or more times;;
      ....
      insert(9);
      getMax and print 0 or more times;

    For each of the following sequences, state whether or not they could occur as a result of such a sequence of MaxQueue operations.

    1. 9 8 7 6 5 4 3 2 1 0
    2. 0 1 2 3 4 5 6 9 8 7
    3. 5 4 3 7 6 9 8 2 1 0
    4. 1 2 3 4 5 0 9 7 8 6
      Solution:  Only the last one could not occur!      
            
  6. Suppose we consider the same problem as in (5) and (6) for standard queues. Of course one sequence of numbers that could be produced is the numbers in order:
         0 1 2 3 4 5 6 7 8 9
        
    Is this the only sequence that you can produce, or is there is another sequence that is possible? Explain your answer by giving another sequence or explaining why the one given is the only possible sequence.
  7. Solution: Yes, this is the only possible sequence, because we have defined the input sequence as ordered from 0 to 9, and a FIFO queue ALWAYS outputs in the same order as the input.

  8. Suppose you have a queue Q and a stack S and you perform the following operations:
              while(! Q.isEmpty() )            // push every element of Q onto the stack
                  S.push( Q.dequeue() );
              while(! S.isEmpty() )            // Enqueue every element popped off the stack
                  Q.enqueue( S.pop() ); 
    How would you describe what you have done to the queue?
    Solution: You have reversed the queue.  
      
  9. Now suppose you have a stack S and a MaxQueue M, and you perform the following operations:
              while(! M.isEmpty() )            // push every element of M onto the stack
                  S.push( M.getMax() );
              while(! S.isEmpty() )            // Insert every element popped off the stack
                  M.insert( S.pop() ); 
    How would you describe what you have done to the priority queue? You may assume there are no duplicate numbers involved.
    Solution: The MaxQueue is unchanged -- it is still in order!
    
      
  10. Now suppose you have a priority queue M, a normal queue Q, and a stack S; M and S are initially empty, but Q has elements in it. You perform the following operations:
              while( !Q.isEmpty() )             
                  M.insert( Q.dequeue() );
              while( !M.isEmpty )             
                  S.push( M.getMax() );
              while( !S.isEmpty() )            
                  Q.enqueue( S.pop() ); 
    How would you describe what you have done to the queue Q? You may assume there are no duplicate numbers involved.
    Solution: Assuming M is a Max Queue, you have ordered the elements in the queue into reverse order (largest at rear, smallest at front); 
    if M were a Min Queue, then you have ordered it into ascending order. The point is that M orders the elements, and S reverses them.  
  11. This is an exercise in the use of reference types. Recall that Strings are reference types, and the name of a String object can be changed, just as arrays can. What would the following code fragment print out?
      String s = "Hithere";
      String t = "Folks";
      String u = "CS112";
      String v = s;
      s = t;
      t = v;
      u = s;
      System.out.println(s.charAt(0)); 
      System.out.println(t.charAt(1));
      System.out.println(u);
      System.out.println(v);
      

    Solution:

    F
    i
    Folks
    Hithere
    
    Explanation, line by line:
      
      String s = "Hithere";            // s points to "Hithere"
      String t = "Folks";              // t points to "Folks"
      String u = "CS112";              // u points to "CS112"
      String v = s;                    // both v and s point to "Hithere"
      s = t;                           // both s and t point to "Folks"
      t = v;                           // t, v, and s point to "Hithere" and only s points to "Folks"
      u = s;                           // s and u point to "Folks"; t, v, and s point to "Hithere" and none point to "CS112"