Practice Exercises (Set A)

1. Suppose that an intermixed sequence of stack push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence could not occur?

1. 4 3 2 1 0 9 8 7 6 5
2. 4 6 8 7 5 3 2 9 0 1
3. 2 5 6 7 4 8 9 3 1 0
4. 4 3 2 1 0 5 6 7 8 9
2. If we implement a stack using a resizing array, when and how is the array resized?

3. Use a stack to evaluate the postfix expression 1 2 + 3 4 * - 9 /. Write the state of the stack after each token (i.e., an operator or operand) is processed.

4. 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 operator stack in the order they are popped.

5. In using a stack to check delimiter matching, three different kinds of errors can occur. Give example expressions that would create each kind of error, and indicate which could result in stack underflow if things are not properly checked first.

6. What does the following code fragment print when n is 50? In general, what does it do when presented with a positive integer n?

Stack s = new Stack();
while (n > 0) {
s.push(n % 2);
n = n / 2;
}
while (!s.isEmpty())
System.out.print(s.pop());

7. Which abstract data type, stack or queue, would you choose to implement an "Undo" feature in a word processor? Which would you choose to store mouse click events when implementing a user interface?

8. What does the following code fragment print when n is 10? In general, what does it do when presented with a positive integer n?

Queue q = new Queue();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i < n; i++) {
int a = q.dequeue();
System.out.println(a);
int b = q.peek();
q.enqueue(a + b);
}

9. If a class implements Iterable interface, what can you do with the class objects?

10. Consider the program below and then answer the questions posed:

class Node {
public int iData; // data item (key)
public Node next; // next node in list

public Node(int id){ // constructor
iData = id;
}
}

class LinkList {
private Node first; // reference to first node on list

first = null;
}

public Node find(int key) { // find the node with a given key
Node current = first; // start at the first node
while (current != null && current.iData != key)
current = current.next; // go to next node
return current;
}

public void displayList() { // display the list
for (Node current = first; current != null; current = current.next)
System.out.println(current.iData); // print data
}

public void insertFirst(int key) { // insert a node at the front of the list
// See question (a)...
}

public Node delete(int key) { // delete the node with a given key
// See question (b)...
}

}

class LinkListApp {
public static void main(String[] args) {
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
Node d = theList.delete(44);
d = theList.delete(88);
theList.displayList(); // display list
} // end main()
}

1. Implement the insertFirst method that inserts a new node with the given data key at the front of the linked list. Assume the list is not empty.

2. Implement the delete method that deletes a node with the given data key. Assume the list is not empty. If the key does not exist in the list, the method should return null and should not change the list.

3. Predict the printed results of the main method in LinkListApp

11. Name two advantages of using linked lists over arrays to store data.

12. Name an advantage of using arrays over linked lists to store data.

13. Below is a method which uses a stack of integers with typical push and pop operations:

public static int foo(int x, int y) {
if (x <= 0 || y <= 0)
return 0;
stack.push(y);
return foo(x - 1, y-1) + stack.pop();
}


Assuming the stack is initially empty, draw a snapshot of the stack after every push and pop statement for each recursive call for foo(3,4). Label each stack snapshot with the recursive call, and the push or pop statement. For example, the following shows the first two snapshots of the stack after the push statement for the call foo(3,4) and after the push statement for the call foo(2,3).

 4
---
foo(3,4) - push

3
4
---
foo(2,3) - push


To what integer value does foo(3,4) evaluate when invoked?

14. Analyze the runtime of the following loops given an even input size N using direct loop analysis or recurrence relations. Derive the runtime cost function, and then a Big-O notation for the cost function. Assume that each loop statement takes 1 unit of time, and the update of loop variable can be ignored (does not count into running time).

(a)
for (int i = 0; i < N; i++) {
if (i % 2 == 0) {
for (int j = 0; j < N; j++)
System.out.println("1 iteration executed!");
}
else {
for (int j = 0; j < 10; j++)
System.out.println("1 iteration executed!");
}
}

(b)
for (int i = 0; i < N; i++) {
for (int j = i; j < 2 * N; j++) {
System.out.println("1 iteration executed!");
}
}

15. 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 4-Queens problem until the first solution is found.

16. 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 0 0 1 1
0 1 0 1 1
0 0 0 1 1
0 1 0 1 0
0 0 0 0 0

17. A doubly circular linked list is a list where each node points to its successor and its predecessor in a circular manner. The head variable points to the first node in the list. An empty list is represented by a null value in head. The prev value of the first list node points to the last node (i.e., the "tail") and the next value of the last node in the list points to the first node. The structure of a node and an (incomplete) list class are given by the following class definitions.

public class Node {
public int value;
Node next; // "next" points to the successor
Node prev; // "prev" points to the predecessor
}

public class List {
public Node head; // head must point to first node in list

public List() { // Constructor
head = null; // Empty list
}

//... other methods ...
}

1. Write a Java method for the List class that inserts a Node object x at the head of the doubly circular list:

public void insertAtHead(Node x) {

// write the code that should go here...

}

2. Write a Java method for the List class that inserts an Node object x at the tail of the doubly circular list:

public void insertAtTail(Node x) {

// write the code that should go here...

}
3. Write a Java method for the List class that deletes the Node object at the tail of the doubly circular list:

public void deleteAtTail() {

// write the code that should go here...

}
18. Show the traces for each sort requested below when applied to the array shown.

{ 'f', 'b', 'a', 'h', 'c', 'd', 'g', 'e' }
1. Selection Sort
2. Insertion Sort
19. What's the average runtime cost of insertion sort in big O notation?

20. What is the best case and worst case time complexity in Big O notation for the selection sort algorithm?

21. Write a recursive method that given some even number $n$, calculates the number of ways to pair off $n$ people. As an example, if $n=4$, there are $3$ such pairings: $(1,2),(3,4)$ and $(1,3),(2,4)$ and $(1,4),(2,3)$. (Hint: suppose you expand a group of $n$ people to $n+2$ people. Consider one of the new people -- let us call him "Bob". Bob must have a partner -- how many are possible? Once we've made this choice, what's left to do?)
int numberOfPairings(int n)

// write the code that should go here...

}

1. (b)
2. double the size when full, halve the size when quarter full
3.
                 4
2       3   3  12       9
1   1   3   3   3   3  -9  -9  -1
=== === === === === === === === ===

The expression evaluates to -1

4. ^ ^ * ( - / +
5. answers vary. As one possibility: "a + [b * (c - d])" has mis-matched delimiters; "[a + (b - c)" is missing a right delimiter; "a + (b - c)]" is missing a left delimiter. This last case (missing left delimiter) can create a stack underflow error when a stack is used for delimiter checking and we fail to check to see if the stack is empty before attempting to pop the stack.
6. $110010$. In general, the code prints the binary version of the value $n$
7. An "undo" feature is best implemented with a stack, while storing mouse click events is best implemented with a queue.
8.
0
1
1
2
3
5
8
13
21
34

In general, this will print out the first n values of the Fibonacci sequence
9. One can iterate through the items of an object of that class. More specifically, one can use a "for-each" loop (i.e., and "enhanced for loop") to do this -- or one can get an iterator using the iterator() method and then use it's next() and hasNext() methods to iterate through the items of the object in question.
1.
public void insertFirst(int key) { // insert a node at the front of the list
Node node = new Node(key);
node.next = first;
first = node;
}

2.
public Node delete(int key) { // delete the node with a given key

// if the list is empty, there is nothing to delete..
if (first == null)
return null;

Node node = first;

// if the key was found on the 1st node, reset "first"..
if (node.iData == key) {
first = node.next;
return node;
}

// traverse the list to find parent of node with the given key..
while (node.next != null && node.next.iData != key) {
node = node.next;
}

if (node.next == null) { // then key wasn't present
return null;
}
else { // re-route references to skip over node to be deleted..
Node deletedNode = node.next;
node.next = node.next.next;
return deletedNode;
}
}

3.
66
22

10. dynamic sizing; very fast insertions and removals
11. no additional overhead in terms of memory (for node references) is needed.
12.

2
3        3        3
4          4        4        4       4
========  ========  ======== ======= ======= =======
foo(3,4)  foo(2,3)  foo(1,2)   pop     pop     pop
push     push       push

foo(3,4) = foo(2,3) + pop
foo(2,3) = foo(1,2) + pop
foo(1,2) = foo(0,1) + pop
foo(0,1) = 0

So,

foo(1,2) = 0 + 2 = 2
foo(2,3) = 2 + 3 = 5
foo(3,4) = 5 + 4 = 9  <-- final answer = 9

1. $\displaystyle{C(n) = \frac{n^2}{2} + 5n \sim \frac{n^2}{2}; \quad C(n) \textrm{ is } O(n^2)}$

2. $\displaystyle{C(n) = \frac{3n^2}{2} + \frac{n}{2} \sim \frac{3n^2}{2}; \quad C(n) \textrm{ is } O(n^2) }$

13.
                                             2
1                       0   0
2       3   3   3               3   3   3
0   0   0   0   0   0   0       1   1   1   1
=== === === === === === === === === === === ===

14.   Positions Marked (following enqueue and dequeue operations described below):
 1 2 4 Wall Wall 3 Wall 6 Wall Wall 5 7 9,10 Wall Wall 8 Wall 12,13 Wall not visited 11 14 15,16,17 18,19,20 21,22,23
enqueue pos 1
dequeue pos 1, mark visited
enqueue pos 2 (with parent pos 1)
enqueue pos 3 (with parent pos 2)
dequeue pos 2, mark visited
enqueue pos 4 (with parent pos 2)
dequeue pos 3, mark visited
enqueue pos 5 (with parent pos 3)
dequeue pos 4, mark visited
enqueue pos 6 (with parent pos 4)
dequeue pos 5, mark visited
enqueue pos 7 (with parent pos 5)
enqueue pos 8 (with parent pos 5)
dequeue pos 6, mark visited
enqueue pos 9 (with parent pos 6)
dequeue pos 7, mark visited
enqueue pos 10 (with parent pos 7)
dequeue pos 8, mark visited
enqueue pos 11 (with parent pos 8)
dequeue pos 9, mark visited
enqueue pos 12 (with parent pos 9)
dequeue pos 10, mark visited (for the second time)
enqueue pos 13, (with parent pos 10)
dequeue pos 11, mark visited
enqueue pos 14, (with parent pos 11)
dequeue pos 12, mark visited
enqueue pos 15 (with parent pos 12)
dequeue pos 13, mark visited (for the second time)
enqueue pos 16 (with parent pos 13)
dequeue pos 14, mark visited
enqueue pos 17 (with parent pos 14)
dequeue pos 15, mark visited
enqueue pos 18 (with parent pos 15)
dequeue pos 16, mark visited (for the second time)
enqueue pos 19 (with parent 16)
dequeue pos 17, mark visited (for the third time)
enqueue pos 20 (with parent pos 17)
dequeue pos 18, mark visited
enqueue pos 21 (with parent 18)
dequeue pos 19, mark visited (for the second time)
enqueue pos 22 (with parent 19)
dequeue pos 20, mark visited (for the third time)
enqueue pos 23 (with parent 20)
dequeue pos 21, mark visited -- done (we just dequeued the end position)

So the path taken backwards (following parents) is:
21, 18, 15, 12, 9, 6, 4, 2, 1

Thus the path taken is: 1, 2, 4, 6, 9, 12, 15, 18, 21

1.
public void insertAtHead(Node x) {
if (head == null) { // no nodes in circular list
}
else {  // one or more nodes in list
}
}

2.
public void insertAtTail(Node x) {
}

3.
public void deleteAtTail() {
if (head == null) { // no nodes in circular list
; //do nothing (optionally throw exception)
}
}
else {
}
}

1.
Order before selection sort application:
f  b  a  h  c  d  g  e

0  1  2  3  4  5  6  7
------------------------
a  b  f  h  c  d  g  e
a  b  f  h  c  d  g  e
a  b  c  h  f  d  g  e
a  b  c  d  f  h  g  e
a  b  c  d  e  h  g  f
a  b  c  d  e  f  g  h
a  b  c  d  e  f  g  h
a  b  c  d  e  f  g  h

Order after selection sort application:
a  b  c  d  e  f  g  h

2.
Order before insertion sort application:
f  b  a  h  c  d  g  e

0  1  2  3  4  5  6  7
------------------------
f  b  a  h  c  d  g  e
b  f  a  h  c  d  g  e
a  b  f  h  c  d  g  e
a  b  f  h  c  d  g  e
a  b  c  f  h  d  g  e
a  b  c  d  f  h  g  e
a  b  c  d  f  g  h  e
a  b  c  d  e  f  g  h

Order after insertion sort application:
a  b  c  d  e  f  g  h

15. $O(n^2)$
16. $O(n^2)$
17.
int numberOfPairings(int n) {
return (n == 2 ? 1 : (n - 1) * numberOfPairings(n-2));
}