Final Examination Solution
Com 1201 – Fall 2002 – Jeff Raab
Section 1 – Java programming
(10) 1. Consider a type of array named a Power-2-Array. An array of int values, a, is defined to be a Power-2-Array if the sum of its contents is equal to 2a.length.
Write a public method below named power2Array that takes an array of int values named a and has a return type of boolean. Your method must return true if the given array is a Power-2-Array by the above definition, or false in every other case. Your code must be complete, correct, documented, and as efficient as possible.
Analyze your method by listing its actual number of steps in the worst case, and by using Big-Oh notation to generalize the number of steps in the worst case.
/**
* Returns true if the sum of the values in the
given array
* is equal to 2^length of the array.
* @example power2Array({1,1}) returns true
* @example power2Array({1,2}) returns false
* @example power2Array({}) returns false
* @example power2Array(null) returns false
* @param a array of values to test
*/
public
boolean power2Array(int[] a) {
if (a == null) {
return false;
}
int sum = 0;
int power = 1;
for (int i = 0; i < a.length; i++) {
sum += a[i];
power *= 2;
}
return (sum == power);
}
The actual number of steps in the worst case is 2n + 4 .
Using Big-Oh notation, this generalizes to O(n) .
Section 2 – Implementing an
ADT
(30) Write an implementation of the Queue ADT, in Java, that uses an array of Objects to hold the contents of the queue. Your implementation must never fail to enqueue an Object due to insufficient space in the array of contents. Your implementation does not have to reduce the length of the array at any time, though it is acceptable for it to do so if you choose.
Your implementation must be complete, correct, documented, and as efficient as possible given the constraints of the problem. Include in your documentation for each method an analysis of the worst case running time of the method, using Big-Oh notation. The details of the Queue ADT are included on the final page of the examination.
Use the remainder of this page and the next page to provide your answer.
/**
* Queue
implementation using an array to store the elements.
* @author Jeff Raab
*/
public class ArrayQueue implements QueueADT {
/** Elements
on this. */
protected
Object[] elements = new Object[10];
/** Index of
front element in this. */
protected
int front = -1;
/** Index of
back element in this. */
protected
int back = -1;
/**
Constructs an empty queue. */
public
ArrayQueue() {}
/**
* Enqueues the given element on this.
* @param o object to enqueue
*/
public void
enqueue(Object o) {
back = after(back);
elements[back] = o;
if (front == -1) {
front
= 0;
}
}
/** Returns the front element on this. */
public Object front() {
if
(isEmpty()) {
throw new RuntimeException(“Queue is empty”);
}
return
elements[front];
}
/** Removes
and returns the front element on this. */
public
Object dequeue() {
if
(isEmpty()) {
throw new RuntimeException(“Queue is empty”);
}
Object
f = elements[front];
front
= after(front);
if
(size == 0) {
front = -1;
back = -1;
}
}
/** Returns
the size of this. */
public int
size() {
if (back >= front) {
return
(back – front);
}
return (back + elements.length – front);
}
/** Returns
whether or not this is empty. */
public
boolean isEmpty() {
return (size() == 0);
}
/**
* Returns the array index after the given
index.
* @param i index in the array
*/
private int
after(int i) {
return ((i + 1) % elements.length);
}
}
Section 3 – Short answer questions
(10) 1. Is it possible to implement the Stack ADT using one or more implementations of the Queue ADT? In other words, is it possible to implement the Stack ADT by using only one or more queues to hold the contents of the stack? You may use only the Queue ADT methods of the queues to implement the methods specified in the Stack ADT. You may assume that a Queue ADT implementation exists that is complete and correct.
Write your answer below. If yes, describe in reasonable detail how such a Stack ADT implementation would be implemented, including at least a short explanation for each method in the ADT. If no, describe in reasonable detail why one or more Queue ADT implementations are insufficient to implement the Stack ADT.
Yes, it is possible to implement the Stack
ADT using 2 implementations of the Queue ADT. One of the queues will be used to store the
elements and the other to hold them temporarily during the pop and top methods.
The push method would enqueue the given element onto the storage queue. The top method would transfer all but the last
element from the storage queue onto the temporary queue, save the front element
of the storage queue to be returned, transfer the last element to the temporary
queue, then transfer all elements back to the storage queue. The pop method would do the same as top, except instead of transferring the last
element onto the temporary queue after saving it for return, that last element
would be discarded.
(10) 2. Describe in reasonable detail a way to implement the Dictionary ADT such that the insertItem, findElement, and removeElement methods would all run in O(1) time, assuming that all of the keys associated with elements in the structure are integers in the range [25, 75]. You do not have to ensure that the remaining Dictionary ADT methods would have any particular running times, and you do not have to describe how those remaining methods would be implemented.
Describe how much memory would be used by such a structure, both specifically and in Big-Oh notation. For example, if you were to describe an unsorted sequence implementation of the Dictionary ADT, you would state that your structure would use 1 sequence of size n, which is O(n).
Given the range of keys, a hash table array
of length 51 could be used to implement the Dictionary ADT. The hash function for the table would be h(k)
= k – 25. Separate chaining would be the collision
handling strategy for the hash table, with unsorted lists used to hold the elements
associated with the key represented by that index. insertItem would hash the key and insert into the
unsorted list at the resulting index: O(1).
findElement would hash the key and return the first
element of the list, unless it was empty: O(1).
removeElement would hash the key and remove the first
element of the list, unless it was empty: O(1).
The memory used by this structure is an
array of 51 lists, which is 51 + O(n) units of memory, or O(n).
Section 4 – Diagrammatic
questions
(5) 1. List the order in which the contents of the following tree would be visited, for each of the given traversals:
|
Traversal |
Visit order |
|||||||||
|
Preorder |
G |
V |
S |
J |
M |
X |
R |
Z |
A |
T |
|
Postorder |
J |
S |
M |
V |
Z |
A |
R |
T |
X |
G |
|
Inorder |
S |
J |
V |
M |
G |
Z |
R |
A |
X |
T |
(5) 2. List the order in which the given keys would be contained in a Priority Queue ADT implemented using a sorted sequence, where keys are ordered in nondecreasing order of their priority value. You should ignore the elements associated with the given keys as they could be any objects, and they do not affect the resulting order.
For this problem the priority value of a key is defined as its minimum absolute value difference from the various powers of 2. For example, the priority value of the key 12 is 4, as it is 4 away from both 8, 23, and 16, 24. The priority value of the key 66 is 2, as it is 2 away from 64, 26. A table of the powers of 2 is below, for your reference:
|
k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
2k |
1 |
2 |
4 |
8 |
16 |
32 |
64 |
128 |
256 |
512 |
1024 |
Fill in the sequence diagram below with your answer, given the following list of keys in random order:
|
Keys |
94 |
28 |
43 |
256 |
71 |
48 |
462 |
11 |
0 |
84 |
54 |
|
Sorted sequence priority queue |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
256 |
0 |
11 |
28 |
71 |
54 |
43 |
48 |
84 |
94 |
462 |
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
size = 11 |
||||||||||||
(5) 3. Draw the heap that results from removing a minimum key from the heap shown below. Circle each node on the given heap diagram that was removed or had its key swapped in this process. You should ignore the elements associated with the given keys as they could be any objects and do not affect the resulting order.
(5) 4. List the contents of the array for an open addressing hashtable using the linear probing style of collision handling, after performing the given Dictionary ADT operations in order. Use the following hash function:
h(k) = | 2k + 5 | mod 11
You should ignore the elements associated with the given keys as they could be any objects and do not affect the resulting order. Place an X in the array to indicate an empty location that used to contain a key.
Fill in the following array diagram with your final answer, for these given operations:
|
Operations |
|
insertItem(2) |
|
insertItem(14) |
|
insertItem(2) |
|
removeAllElements(2) |
|
removeElement(0) |
|
insertItem(13) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
13 |
X |
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
length = 11 |
||||||||||||
Section 5 – Data structures
For each situation below, list the ADT you would choose for the specified task, and the implementation of that ADT that would provide the most efficient running time for each of the operations listed in the problem. Please use asymptotic analysis for the running time, and use Big‑Oh and Big‑Theta as appropriate.
(10) 1. You are employed by a software company designing an application for use by produce wholesalers. Your job is to implement the data structure used to store the inventory of the warehouse containing the produce. The data structure must be able to add a product with an associated code indicating its likelihood to spoil, remove a product that is most likely to spoil (to ship it from the warehouse), and return the overall number of products in the inventory. No other functionality is needed.
Your choice of ADT would be: Priority Queue ADT
Your choice of implementation would be: Heap
|
Operation |
Method in ADT used to implement |
Running time |
|
Add a product and its code |
insertItem |
O(log
n) |
|
Remove a product likely to spoil |
removeMin |
O(log
n) |
|
Return the number of products |
size |
O(1) |
(10) 2. You are employed by a software company designing an application for use by taxicab dispatchers. Your job is to implement the data structure used to associate customers with taxicabs. The data structure must be able to associate a customer’s address with a taxicab’s number, find the address associated with a taxicab’s number, and remove the association between an address and a taxicab number (when the customer has been delivered to its destination. No other functionality is needed.
Your choice of ADT would be: Dictionary ADT
Your choice of implementation would be: Hash table
|
Operation |
Method in ADT used to implement |
Running time |
|
Associate address with taxicab |
insertItem |
O(n) |
|
Find address associated with taxi |
findElement |
O(n) |
|
Remove address and taxicab association |
removeElement |
O(n) |