Compsci 100, Fall 2009, October 9 Recitation


Name: _____________________  Netid: _________________


Name: _____________________  Netid: _________________
 

Name: _____________________  Netid: _________________


    The first question is continued from last week's recitation. In this version, you'll be asked to analyze a recursive version and to comment on an iterative version.

    Move to the Back

    Doubly linked lists are implemented using the declaration below. public static class DNode { string info; DNode next; // next node DNode prev; // previous node DNode(String s, DNode before, DNode after) { info = s; prev = before; next = after; } } Write the method moveToBack which moves each node whose info field is equal to target to the end of the list. The nodes are doubly-linked. The relative order of the unmoved nodes doesn't change (from the original order in the list). A pointer to the modified list is returned.

    Note that it's possible that the original first node is moved and that no nodes are moved. You should not create any new nodes, just move pointers/references.

    For full credit your code must run in O(n) time for an n-node list. You might want to create a pointer to a list containing the moved nodes, update that list, then link the entire moved-node list to the end.

    /** * Move all nodes with target values to end of list, * leaving relative order of nodes unchanged. * @param list is the list to be altered * @return the potentially altered list */ public static DNode moveAfter(DoubleNode list, String target)
  1. Recursive Implementation Here's a recursive implementation that passes several tests. You'll be asked questions about this implementation after the code. public DNode moveToBack(DNode list, String target){ if (list == null) return list; if (list.info.equals(target)){ DNode after = moveToBack(list.next,target); if (after == null) return list; DNode temp = after; while (temp.next != null){ temp = temp.next; } temp.next = list; list.next = null; list.prev = temp; return after; } else { list.next = moveToBack(list.next,target); return list; } }
    1. Explain in words the logic of the else code-block, when is it executed and why does it work?
      
      
      
      
      
    2. Explain the purpose of the while loop in the if-code-block. Why is it there and what does it do?
      
      
      
      
      
    3. If T(n) is the time for moveToBack to execute for an n-Node list, then justify the following recurrence relation. Explain why both expressions on the right-hand-side of the equation occur and why they're correct. What do you think the running time for this solution is?
         T(n) = T(n-1) + O(n)
      
      
      
      
      
      
      
      
      
      
      
  2. Here's an iterative solution that passes some tests. You'll be asked questions about the code. public DNode moveToBack(DNode list, String target){ DNode stack = null; DNode first = null; if (list == null) return list; // need to keep track of the last node, so stop on it while (list.next != null){ if (list.info.equals(target)){ DNode follow = list.next; // follow 1 if (list.prev != null){ list.prev.next = list.next; } list.next.prev = list.prev; if (stack == null){ stack = list; list.prev = null; list.next = null; } else { list.next = stack; list.prev = null; stack.prev = list; stack = list; } list = follow; // follow 2 } else { if (first == null){ first = list; } list = list.next; } } // list references the list node in the non-target node list // and it's possible that list.info.equals(target) list.next = stack; if (stack != null){ stack.prev = list; } return first; }
    1. In the code the variable stack points to the first node of all the target-nodes that will be moved to the back, each target node is added to the front of the stack list. Explain the code in the else block of dealing with a target-node and why the name of the variable is stack.
      
      
      
      
      
      
      
      
    2. What is the purpose of the lines labeled follow 1/follow 2?
      
      
      
      
      
      
      
      
    3. When will the code if (list.prev != null) evaluate to true?
      
      
      
      
      
      
    4. The code above works except when every node in the list is a target node to be moved to the back. In that case the code above returns null. Explain why and a very simple fix.
      
      
      
      
      
      
      


    Stacks and Queues

    Postfix Stuff

  3. Evaluate the following postfix expressions, none result in an error.

    1. 3 8 7 + * 5 /
    2. 6 4 * 20 - 12 +
    3. 8 6 + 4 + 2 *
    4. 5 4 3 2 1 + + + +

  4. For the last expression above, explain which re-arrangements of the numbers 1, 2, 3, 4, 5, and four plus-signs do not result in the value 15 and why. Use English to describe the characteristics of the expressions whose value is not 15.
    
    
    
    
    
    


    The questions below refer to the Postfix.java program. Here's a capture of one run of the program. The user entered input is in italics.

    3 5 8 + *
    value of 3 5 8 + * = 39
    5 3 -
    value of 5 3 - = 2
    5 3 + +
    error: java.lang.RuntimeException: empty stack error java.util.EmptyStackException
    3 a +
    error: java.lang.RuntimeException: badly formed postfix expression java.lang.NumberFormatException: For input string: "a"
    9 +
    error: java.lang.RuntimeException: empty stack error java.util.EmptyStackException
    5 7 %
    error: java.lang.NumberFormatException: For input string: "%"
    
    

  5. The StringTokenizer class splits a string into a sequence of tokens separated by some character in the String DELIMS, but also returns the character separating the tokens. Explain the purpose of the if (t.equals(" ")) continue; statement in the method evaluate (note that there is a space as the last character of DELIMS).
    
    
    
    
    
    
    
  6. As shown in the run above, the postfix expression 5 3 + + generates an error. Explain the error and how the exceptions are caught and rethrown in the code.
    
    
    
    
    
    
  7. As shown in the run above, the postfix expression 3 a + generates an error. Explain the error and how the exceptions are caught and rethrown in the code -- in particular, when does the error occur in the processing and evaluation of the expression?
    
    
    
    
    
    
    
    
  8. The postfix expression "5 3 %" generates an error as shown above -- note that this is not a RunTimeException. Why is a NumberFormatException generated --- when does the error occur. Explain how to modify DELIMS so that the IllegalArgumentException about unrecognized operators is generated (and why/how modifying DELIMS will generate the error).
    
    
    
    
    
    


    Stack/Queue Questions

    These questions don't refer to the postfix evaluation code.

  9. Describe the contents of stack s after the method convert below executes. (describe the contents in a general manner based on what's in s before the code executes.) public void convert(Stack<Object> s){ ArrayList<Object> list = new ArrayList<Object>(); while (s.size() > 0) { list.add(s.pop()); } for(Object o : list) { s.push(o); } }
  10. What happens if a queue is used instead of a stack in the code above, e.g., public void convert(Queue<Object> q){ ArrayList<Object> list = new ArrayList<Object>(); while (q.size() > 0) { list.add(q.remove()); } for(Object o : list) { q.add(o); } }

  11. Consider loading a stack and queue using the code below, this is the load method (we'll consider the stack and queue to be instance variables). Stack<String> stack = new Stack<String>(); Queue<String> queue = new LinkedList<String>(); public void load(){ for(int k=0; k < 10; k++) { stack.push(""+k); queue.add(""+k); } }

    What is printed by the following after loading the stack using the load method.

    while (stack.size() > 0) { System.out.println(stack.pop()); }

  12. What is printed by the following after loading the queue using the load method. while (queue.size() > 0) { System.out.println(queue.remove()); }

    Consider the function popFromTo below.

    Stack<Object> popFromTo(Stack<Object> from) { Stack<Object> to = new Stack<Object>(); while (from.size() > 0) { to.push(from.pop()); } return to; }
  13. What happens when the statement below executes? s = popFromTo(s);

  14. If stack s is loaded with 10 values using the load method, what are the contents of s after executing: Stack<Object> s2; s2 = popFromTo(s); s = popFromTo(s2);

  15. Suppose the statements below are executed (when queue contains 10 values from the load method), what are the contents of q2 after the 11 is added to queue? Queue<Object> q2 = queue; queue.add(""+11);