Exercises - Review T1

1. Find the cost function C(n), and its tilde approximation, for the primitive operations of interest specified the code snippet below.

int count = 0;
for (int i = 2; i < 2*n; i++)
for (int j = i; j < n; j++)
something(); // <-- primitive operation of interest


As $i$ takes on the values $2,3,4,\ldots,(2n-1)$, we go through the following numbers of $j$ values: $$(n-2),(n-3),\ldots,2,1,0,0,\ldots,0$$ Thus the primitive operation of interest happens $$(n-2) + (n-1) + \cdots + 1 \, \textrm{times}$$ This, being the sum of an arithmetic series, is given by $$C(n) = \cfrac{(n-1)(n-2)}{2}$$

2. Find the cost function C(n), and its tilde approximation, for the primitive operations of interest specified the code snippet below. You may assume $n = 3^m$ for some positive integer m.

int count = 0;
for (int i = n/2; i < n; i++)
for (int k = 1; k < n; k *= 3)
something(); // <-- primitive operation of interest

Note $n = 3^k$ must be odd. As the n/2 involves "integer division", the first value of $i$ is actually $(n-1)/2$. Thus, the outer loop happens $n-(n-1)/2 = (n+1)/2$ times. The inner loop happens $\log_3 n$ times, so $$C(n) = \left( \frac{n+1}{2} \right) \log_3 n \sim \frac{n \log_3 n}{2}$$

3. Use a stack to decide if the delimiters below properly match or not. Show the state of the stack after each push or pop is performed, and indicate what should be concluded when the algorithm terminates.

{ [ ( { a b } ) ] [ c ] ( [ d f ) ] }

{         (note: as drawn here, the stack "grows" to the right)
{ [
{ [ (
{ [ ( {
{ [ (
{ [
{
{ [
{
{ (
{ ( [
{ (    at which point the popped "[" doesn't match
the corresponding delimiter found in the expression (a ")")

4. Use a stack to evaluate the postix expression below. Show the state of the stack after each value or operator is read, and then indicate the value for the expression produced.

2 3 4 + 5 6 7 - * + +

2        (note: as drawn here, the stacck "grows" to the right)
2  3
2  3  4
2  7
2  7  5
2  7  5  6
2  7  5  6  7
2  7  5 -1
2  7 -5
2  2
4     ---> so the expression evaluates to 4

5. Use two stacks to evaluate the fully parenthesized infix expression below. Show the state of both stacks after each value, operator, or parenthesis is read, and then indicate the value for the expression produced.

( 9 + ( ( 4 + 3 ) * ( 7 - 8 ) ) )

operand stack          operator stack
: 9                    :
: 9                    : +
: 9  4                 : +
: 9  4                 : + +
: 9  4  3              : + +
: 9  7                 : +
: 9  7                 : + x
: 9  7  7              : + x
: 9  7  7              : + x -
: 9  7  7  8           : + x -
: 9  7 -1              : + x
: 9 -7                 : +
: 2                    :          ---> so the expression evaluates to 2

6. Use a stack and backtracking to find two solutions to the problem of placing 5 queens on a 5 x 5 chess board so that no queen can attack any other. Show the state of the stack with each queen placement attempted.

We place column numbers $0$ to $4$ on the stack as we place queens in rows $0$ to $4$, as shown below:

: 0
: 0 2
: 0 2 4
: 0 2 4 1
: 0 2 4 1 3    ---> 1st solution
: 0 2 4 1
: 0 2 4
: 0 2
: 0
: 0 3
: 0 3 1
: 0 3 1 4
: 0 3 1 4 2    ---> 2nd solution

7. Consider the following code:

import java.util.Iterator;

public class ThingyMebob {

Thing[] things;

public ThingyMebob() {
things = new Thing[10];
}

public Iterator iterator() {
return _______________ {
int pos = things.length-1;
public boolean hasNext() {
return pos >= 0;
}

public Thing next() {
pos--;
return things[pos+1];
}
};
}

public void fill(Thing[] things) {
for (int i =0; i < 5; i++)
this.things[i] = things[i];
}

public static void main(String[] args) {
ThingyMebob bob = new ThingyMebob();
String[] strs = {"a","b","c","d","e"};
bob.fill(strs);
for (String string : bob)
System.out.print(string);
}
}

1. What code must be added in the blank to support for-each loops like the one in main?

2. In addition to the code that must be added in the given blank addressed in the previous question, there are two other errors in the code above. Describe them both.

1. new Iterator()

2. The class should implement the Iterable interface, so add "extends Iterable" after "public class ThingyMebob".

Also, generic array creation is not allowed in Java, so change "things = new Thing[10];" to "things = (Thing[]) (new Object[10]);"

8. What method(s) does a class guarantee exist(s) if it implements the Iterable interface?

iterator()

9. The following letters, in the order they appear, are enqueued into a newly constructed queue implemented using an array. Dashes will cause a dequeue. The underlying array doubles in size when the enqueued character would fill the array and halves its size when a dequeue would leave it one-quarter full. Trace the state of the internal array that results. (Indicate null entries in the array with a period.)

A B C D - E F - - G H I - - - -

A  .                     // double size when one short of full
A  B  .  .
A  B  C  .
A  B  C  D  .  .  .  .
.  B  C  D  .  .  .  .   // leave rest of array in place on dequeue
.  B  C  D  E  .  .  .
.  B  C  D  E  F  .  .
.  .  C  D  E  F  .  .
.  .  .  D  E  F  .  .
.  .  .  D  E  F  G  .
.  .  .  D  E  F  G  H
I  .  .  D  E  F  G  H   // wrap tail around
I  .  .  .  E  F  G  H
I  .  .  .  .  F  G  H
I  .  .  .  .  .  G  H   // halve size when 1/4 full
H  I  .  .

10. Suppose the integers 0 through 9 are pushed, in order, onto a stack. The stack is then popped until it is empty, with the result of each pop immediately enqueued in an initially empty queue. Finally, the queue is dequeued until it is empty, printing each value dequeued in the order it is dequeued. What prints as a result?

The numbers leave the stack in reverse order, while the queue leaves this order unchanged. So the following would be printed:

9 8 7 6 5 4 3 2 1 0

11. Assuming q below is an initially empty queue of integers, show the state of the queue after this code fragment executes. (Make sure to indicate the head and tail of the queue.). You may assume the method sumOfDigits(int n) returns the sum of the digits of n.

q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
q.enqueue(5);

for (int i = 0; i < 4; i++)
int a = q.dequeue();
int b = q.dequeue();
q.enqueue(a+b);
q.enqueue(sumOfDigits(a+b))
}


The queue after the code above executes looks like this:

(Head) 7 8 8 10 1 (Tail)

To understand why, consider the state of the queue after each pass through the loop, as shown the below (the head is always on the left side, and the tail on the right):

1 2 3 4 5
3 4 5 3 3
5 3 3 7 7
3 7 7 8 8
7 8 8 10 1

12. Suppose a queue is implemented with an array. Why does one keep track of the position of the head of the queue? Why not always insist the head of the queue is at the beginning of the array (i.e., at index 0)?

So we don't have to make so many copies to move every element in the queue forward

13. What's the cost function $C(n)$, associated with the array accesses (i.e., getting or assigning a value) resulting only from the array resizing in pushing n items onto a stack implemented with an array (initially of size 1) whose size is increased by a factor of 5 every time it gets full? For ease of analysis, you may assume that $n=5^k$ for some positive integer $k$.

Let $S$ be the number of copies made during resizing. Then

$$\begin{array}{rclllllll} 5S &=& & & 5 + & 5^2 + & ... + & 5^{k-1} + &5^k\\ S &=& 1& + & 5 + & 5^2 + & ... + & 5^{k-1} \end{array}$$ Subtracting these, we have $$4S = 5^k - 1$$ So, $$\begin{array}{rcl} C(n) &=& 2*(5^k - 1)/4 \hspace{.1in}\textrm{doubled as each copy requires 2 array accesses}\\ &=& (5^k - 1)/2\\ &=& (n - 1)/2 \end{array}$$
14. There are two errors present in the code below. Find them!

The class described is meant to work as a linked list that maintains a reference only to its head node. (Note, the fact that the class does not not maintain a reference to its tail is intentional, and should not be considered an error.)

The addLast() method is intended to add the item specified to the tail of the linked list.

public class LL {

private class Node {
Item item;
Node next;
}

Node first;

Node newEnd = new Node();
newEnd.item = item;
newEnd.next = null;

if (first == null)
first = newEnd;
else {
Node tmp = first;
while (tmp != null)
tmp = tmp.next;
tmp.next = newEnd;
}
}
}


First Error: Missing generic type parameter at top (i.e., LL)
Other Error: In the while loop, the condition should be (tmp.next != null)