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)
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;
}
}
Explain in words the logic of the else code-block,
when is it executed and why does it work?
Explain the purpose of the while loop in the
if-code-block. Why is it there and what does it do?
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)
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;
}
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.
What is the purpose of the lines labeled follow 1/follow
2?
When will the code if (list.prev != null) evaluate to
true?
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
Evaluate the following postfix expressions, none result in an error.
3 8 7 + * 5 /
6 4 * 20 - 12 +
8 6 + 4 + 2 *
5 4 3 2 1 + + + +
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: "%"
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).
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.
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?
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.
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
What happens if a queue is used instead of a stack in the code
above, e.g.,
public void convert(Queue q){
ArrayList list = new ArrayList();
while (q.size() > 0) {
list.add(q.remove());
}
for(Object o : list) {
q.add(o);
}
}
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 stack = new Stack();
Queue queue = new LinkedList();
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());
}
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 popFromTo(Stack from) {
Stack to = new Stack();
while (from.size() > 0) {
to.push(from.pop());
}
return to;
}
What happens when the statement below executes?
s = popFromTo(s);
If stack s is loaded with 10 values using the load method, what
are the contents of s after executing:
Stack s2;
s2 = popFromTo(s);
s = popFromTo(s2);
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 q2 = queue;
queue.add(""+11);