# 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.

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) {

}