1. Suppose that the Stack class consisted only of the three methods push, pop, and isEmpty:
2. 3. 4. 5.
6.
7. } 8.
9.
public Stack() { … }
public void push(T item) { … }
public T pop() throws NoSuchElementException
public boolean isEmpty() { … }
{ … }
public class Stack
…
Implement the following “client” method (i.e. not in the Stack class, but in the program that uses a stack): public static
10. // COMPLETE THIS METHOD 11. }
12.
to return the number of items in a given stack S.Derive the worst case big O running time of the algorithm you used in your implementation. What are the dominant algorithmic operations you are counting towards the running time?
SOLUTION
Create another, temporary stack. Pop all items from input to temp stack, count items as you go. When all done, push items back from temp stack to input, and return count.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
public static
// COMPLETE THIS METHOD
Stack
int count=0;
while (!S.isEmpty()) {
temp.push(S.pop());
count++; }
while (!temp.isEmpty()) {
S.push(temp.pop());
}
24. return count; 25. }
26.
27.
Note: There’s no try-catch around
the S.pop() and temp.pop() calls because we know there won’t be an exception, since we only popping when the stack is not empty.Dominant operations are push, pop. (isEmpty is auxiliary, used only as a stopping condition. The constructor is only used once, so can be ignored since it is independent of the input stack size.) Each item in the stack is popped and pushed two times. For a stack of size n, this will add up to 4n pushes and pops, which gives a big O time of O(n).
28.
29.A postfix expression is an arithmetic expression in which the operator comes after the values (operands) on which it is applied. Here are some examples of expressions in their regular (infix) form, and their postfix equivalents: Infix Postfix
30. —————————-
31. 2 2
32. 2+3 23+
33. 2*(3+4) 234+*
34. 2*(3-4)/5 234-*5/ 35.
Note that the postfix form does not ever need parentheses.Implement a method to evaluate a postfix expression. The expression is a string which contains either single-digit numbers (0–9), or the operators +, -, *, and /, and nothing else. There is exactly one space between every two characters. The string has no leading spaces and no trailing spaces. You may assume that the input expression is not empty, and is correctly formatted as above. You may find the following Stack class to be useful – assume the constuctor and methods are already implemented.
public class Stack
36. public Stack() { … }
37. public push(T item) { … }
38. public T pop() throws NoSuchElementException
{ … }
39. public T peek() throws
NoSuchElementException { … }
40. public boolean isEmpty() { … }
41. public void clear(T item) { … }
42. public int size (T item) { … }
43. }
44.
}You may use the Character.digit(char,10) method to convert a character to the integer value it represents. For example, Character(‘2’,10) returns the integer 2. (The parameter 10 stands for the “radix” or base of the decimal number system.)
You may write helper methods (with full implementation) as necessary. You may not call any method that you have not implemented yourself.
public static float postfixEvaluate(String
expr) {
45. /** COMPLETE THIS METHOD **/ 46. }
47.
SOLUTION:
public static float postfixEvaluate(String expr) {
48.
49.
50.
51.
52.
Stack
for (int i=0; i < expr.length(); i++) {
char ch = expr.charAt(i);
if (ch == ' ') { continue; }
if (ch == '+' || ch == '-' || ch == '*' ||
ch == '/') {
53. float second = stk.pop();
54. float first = stk.pop();
55. switch (ch) {
56. case '+': stk.push(first + second);
57. case '-': stk.push(first - second);
58. case '*': stk.push(first * second);
59. case '/': stk.push(first / second);
60. }
61.
62.
63.
64. }
65. return stk.pop();
66.}
67.
68.Consider a smart array that automatically expands on demand. (Like the java.util.ArrayList.) It starts with some given initial capacity of 100, and whenever it expands, it adds 50 to the current capacity. So, for example, at the 101st add, it expands to a capacity of 150.How many total units of work would be needed to add 1000 items to this smart array? Assume it takes one unit of work to write an item into an array location, and one unit of work to allocate a new array.
SOLUTION
This is the sequence of adds and work:
◦ First 100 adds: 100 units for writes
◦ Expansion: 1 unit for allocation + 100 units to write from old to new
◦ Next 50 adds: 50 units for writes
◦ Expansion: 1 unit for allocation + 150 units to write from old to new
◦ Next 50 adds: 50 units for writes
◦ Expansion: 1 unit for allocation + 200 units to write from old to new
◦ Next 50 adds: 50 units for writes. .
.
69.To add 1000 elements, 18 expansions of 50 required (100+18*50=1000)Units of work done: 100 + (1+100+50)+ (1+150+50)+ (1+200+50)+ ... (1+950+50)
continue; }
stk.push(Character.digit(ch,10);
70.Suppose you set up a smart array with an initial capacity of 5, with a DOUBLING of capacity every time there is a resize. What would be the average number of units of work per add, in the course of performing 100 adds? Assume the same work units as the previous exercise.SOLUTION
We will expand the array 5 times: to 10, 20, 40, 80 and 160, one unit per expansion for a total of 5 units.
Each time we expand, we have to copy the current length over. So cost for that will be 5+10+20+40+80 = 155.
We will need to write 100 elements, which will cost 100 units. So total = 5 + 155 + 100 = 260. The average is 260/100 = 2.6 for each add.
71.You are given the following Queue class:
72.
73.
74.
75.
public class Queue
public Queue() { … }
public void enqueue(T item) { … }
public T dequeue() throws
76. 77. 78. 79.
public boolean isEmpty() { … }
public int size() { … }
}
NoSuchElementException { … }
Complete the following client method (not a Queue class method) to implement the peek feature, using only the methods defined in the Queue class:
80. // returns the item at the front of the given
queue, without
81. // removing it from the queue
82. public static
83. throws NoSuchElementException {
84. /** COMPLETE THIS METHOD **/
85. }
86.
Derive the worst case big O running time of the algorithm that
drives your implementation. What are the dominant algorithmic operations you are counting towards the running time? SOLUTION
◦
◦ ◦ ◦ ◦ ◦ ◦
Version 1, using temporary queue and isEmpty() method // returns the item at the front of the
given queue, without
// removing it from the queue
public static
throws NoSuchElementException {
/** COMPLETE THIS METHOD **/
if (q.isEmpty()) {
throw new
NoSuchElementException(“Queue Empty”);
◦}
◦ T result = q.dequeue(); ◦
◦ Queue
◦ temp.enqueue(result); ◦
◦ while(!q.isEmpty()) {
◦ ◦} ◦
temp.enqueue(q.dequeue()); ◦ while(!temp.isEmpty()) {
◦
◦}
◦ return result; ◦}
◦
◦ ◦
Dominant operations are enqueue and dequeue. Every item is enqueued twice and dequeued twice. For a queue of size n, this adds up to 4n operations, which is O(n) time.
Version 2, using size() method, no scratch queue needed // returns the item at the front of the
given queue, without
// removing it from the queue
q.enqueue(temp.dequeue());
87.
◦ ◦ ◦ ◦ ◦
public static
throws NoSuchElementException {
/** COMPLETE THIS METHOD **/
if (q.isEmpty()) {
throw new
NoSuchElementException(“Queue Empty”); ◦}
◦ ◦ ◦ ◦
◦
T result = q.dequeue();
q.enqueue(result);
// dequeue an element and enqueue it
again for (size-1) elements
// if there was only 1 element, this
loop will not execute
◦
◦
◦}
◦ return result; ◦}
◦
for (int i=0; i < q.size()-1; i++) {
q.enqueue(q.dequeue());
Dominant operations are enqueue and dequeue. For a queue of size n, there are n enqueques and dequeues each,
for 2n operations, which gives O(n) time.
88.* Suppose there is a long line of people at a check-out counter in a store. A new counter is opened, and people in the even positions (second, fourth, sixth, etc.) in the original line are directed to the new line. If a check-out counter line is modeled using
a Queue class, we can implement this "even split" operation in this class.Assume that a Queue class is implemented using a CLL, with a rear field that refers to the last node in the queue CLL, and that the Queue class already contains the following constructors and methods:
89. public class Queue
90. public Queue() { rear = null; }
91. public void enqueue(T obj) { … }
92. public T dequeue() throws
NoSuchElementException { … }
93. 94. 95. 96.
public boolean isEmpty() { … }
public int size() { … }
}
Implement an additional method in this class that would perform
the even split:
97. // extract the even position items from
this queue into
98. // the result queue, and delete them from
this queue
99. 100. 101. 102.
public Queue
/** COMPLETE THIS METHOD **/
}
Derive the worst case big O running time of the algorithm that drives your algorithm. What are the dominant algorithmic operations you are counting towards the running time? SOLUTION
// extract the even position items from
this queue into
103.
this queue
104.
105.
106.
107.
108. Queue
109. int originalSize = size();// size of
this original queue
110.
111. // iterate once over each pair of
queue elements
// the result queue, and delete them from
public Queue
/** COMPLETE THIS METHOD **/
// Front of queue is at position 1, so
we will extract 2nd, 4th, 6th, …
112.
pos += 2) {
113.
114.
115.
116.
result queue
117.
118.
119.
120.
we need to
121.
122.
123.
124.
125.
126.
127. }
128.
for (int pos=2; pos <= originalSize;
// the first in a pair is recycled
enqueue(dequeue());
// the second in a pair goes to
evenQueue.enqueue(dequeue());
}
// if original size was an odd number,
// recycle one more time
if ((originalSize % 2) == 1) {
enqueue(dequeue());
}
return evenQueue;
129.
Dominant operations are enqueue and dequeue. For a queue of size n, there are n enqueues and n dequeues, for a total
of 2n opertions. So O(n) time.