Midterm Examination Solution
Com 1201 Fall 2002 Jeff Raab
Section
1 Java Programming
Carnivals and
game shows often feature a Wheel of Fortune, a circular device that can be
spun to randomly select a prize, or randomly select a number or symbol for
wagering.
A simple wheel of this kind has a number of locations on it that each represent a prize, and a fixed pointer that indicates the randomly selected location. When the wheel is spun, the prize locations move around the fixed pointer, until the motion stops and a location is indicated by the pointer. A picture of this kind of wheel is shown at the right.
Assume the following Java class definition for such a wheel:
/** Models
a carnival or lottery wheel of fortune. */
public
class WheelOfFortune {
/** Array containing prize amounts for
wheel locations. */
protected int[] prizes = null;
/**
*
Constructs a wheel with the given number
* of
prize locations.
*
@param size number of prize locations
*/
public WheelOfFortune(int size) {
prizes = new int[size];
for (int i = 0; i < prizes.length;
i++)
prizes[i] = randomPrize();
}
/** Returns a prize amount, at random. */
protected int randomPrize() {
return (int)(Math.random() * 10000);
}
}
Write a public method named spin to be included in the definition of the WheelOfFortune class. This method must take a single parameter named clicks, of type int, and rotate the prize amounts stored in the array forward the number of locations indicated by the parameter.
For example, for a prize amount array containing { 1, 2, 3, 4 } in order, a call to spin(2) must result in a prize amount array containing { 3, 4, 1, 2 } in order. For a prize amount array containing { 0, 100, 10, 5000 } in order, a call to spin(3) must result in a prize amount array containing { 100, 10, 5000, 0 } in order.
Section
1 answer
This method must treat the array named prizes as a circular array, and rotate the values the given number of indices. As with any shift of values in an array, care must be taken not to overwrite a value unless that value has been temporarily stored in a variable for the term of the rotation. Here is a solution method for this problem:
/**
* Rotates this wheel the given number of
clicks.
* @param clicks number of clicks to rotate
this wheel
*/
public
void spin(int clicks) {
int[] newPrizes = new int[prizes.length];
for (int i = 0; i < prizes.length; i++)
newPrizes[i + clicks % prizes.length]
= prizes[i];
prizes = newPrizes;
}
It is possible to write a method to perform this task that does not create a new array, but it is much easier to do so. A less efficient but very readable alternative would be to perform a series of single rotations:
/**
* Rotates this wheel the given number of
clicks.
* @param clicks number of clicks to rotate
this wheel
*/
public
void spin(int clicks) {
int temp = 0;
for (int i = 0; i < clicks; i++) {
temp = prizes[prizes.length - 1];
for (int j = prizes.length - 1; j
> 0; j++) {
prizes[j] = prizes[j - 1];
}
prizes[0] = temp;
}
}
Section
2 Implementing a Java interface
The Deque ADT describes a data structure used to store and retrieve Objects. Assume the following Java interface specifying the required operations for the ADT:
/**
Interface describing the operations in the Deque ADT. */
public
interface DequeADT {
/**
*
Inserts the given element at the first position
* in
this deque.
*
@param element object to be added
*/
public void insertFirst(Object element);
/**
*
Inserts the given element at the last position
* in
this deque.
*
@param element object to be added
*/
public void insertLast(Object element);
/**
* Removes the object at the
first position
* in this deque, and returns it.
*/
public Object removeFirst() throws RuntimeException;
/**
* Removes the object at the last
position
* in this deque, and returns it.
*/
public Object removeLast() throws RuntimeException;
/** Returns the number of objects in this
deque. */
public int size();
/** Returns whether or not this deque is empty.
*/
public boolean isEmpty();
}
On the following page, write a complete Java class named VectorDeque that implements this ADT using a Java Vector object to do the work of the methods required by the ADT. The last pages of this exam summarize the documentation for the Vector class, for your reference.
Your class must include all necessary code. A perfect score will be given for a well documented class definition that could be typed into a Java file and compiled without error, and that correctly implements the above ADT. Partial credit will be given for incomplete or incorrect code.
Your code must be legible to be graded!
Section
2 answer
This problem requires a similar class to the VectorStack class from the Stack Pictures homework. Here is my version of this class:
import
java.util.Vector;
/** Deque
implementation using a Java Vector. */
public
class VectorDeque implements DequeADT {
/** Vector used to store elements. */
protected Vector elements = new Vector();
/** Constructs a new deque. */
public VectorDeque() {}
/**
*
Inserts the given element at the first position
* in
this deque.
*
@param element object to be added
*/
public void insertFirst(Object element) {
elements.insertElementAt(0,
element);
}
/**
*
Inserts the given element at the last position
* in
this deque.
*
@param element object to be added
*/
public void insertLast(Object element) {
elements.add(element);
}
/**
* Removes the object at the
first position
* in this deque, and returns it.
*/
public Object removeFirst() throws RuntimeException
{
if (isEmpty())
throw new RuntimeException(Its
empty.);
return elements.remove(0);
}
/**
*
Removes the object at the last position
* in
this deque, and returns it.
*/
public Object removeLast()
throws RuntimeException {
if (isEmpty())
throw new
RuntimeException(Its empty.);
return
elements.remove(size() - 1);
}
/** Returns the number of objects in this
deque. */
public int size() {
return elements.size();
}
/** Returns whether or not this deque is
empty. */
public boolean isEmpty() {
return elements.isEmpty();
}
}
Section
3 Analysis
Analyze each code segment and write the number of * characters it prints. Provide an asymptotic analysis of the number of * characters printed, using Big-Oh or Big-Theta as appropriate. In case you are unsure, the following code prints a single * character:
System.out.println(*);
The following code prints three * characters:
System.out.println(***);
Be sure to completely read each code segment before performing your analysis. If the number of * that are printed, actually or asymptotically, depends on a variable you should use that variable in your answers.
1. System.out.println(****);
for (int i = 0; i < n; i++)
System.out.println(**);
System.out.println(***);
The number of * characters printed is 2n + 7.
Asymptotically, the number of * characters printed is O(n).
2. System.out.println(**);
for (int i = 0; i < n; i++) {
for
(int j = 0; j < n; j++) {
System.out.println(*);
}
}
System.out.println(**);
The number of * characters printed is n2 + 4.
Asymptotically, the number of * characters printed is O(n2).
Section
3 Analysis
Analyze each code segment and write the number of * characters it prints. Provide an asymptotic analysis of the number of * characters printed, using Big-Oh or Big-Theta as appropriate.
3. System.out.println(*);
int pow = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 *
2;
for (int i = 0; i < pow; i++)
System.out.println(*);
System.out.println(***);
The number of * characters printed is 1024 + 4.
Asymptotically, the number of * characters printed is O(1).
4. System.out.println(**);
for (int i = 0; i < n; i++) {
for
(int j = i; j < m; j++) {
System.out.println(***);
}
}
System.out.println(****);
The number of * characters printed is n <= m n(n + 1) / 2 + n(m - n) + 6 n > m m(m + 1) / 2 + 6
Asymptotically, the number of * characters printed is O(mn).
Section 4 Linear
structures
For each situation below, circle the ADT you would choose for the specified task, and circle 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.
1. You are employed by a software company designing an application for use in food markets. Your job is to implement the data structure used to store the price of each item scanned as a customer checks out. The structure must be able to add a price to the structure, get the last price that was added, and remove the last price that was added (in the case where the item scanned incorrectly).
|
Stack ADT |
Your choice of linear ADT would be: Queue ADT
|
Linked List |
Your choice of implementation would be: Dynamic Array
|
Operation |
Method in ADT used to implement |
Running time |
|
Add price to structure |
push |
O(1) |
|
Get last price added to structure |
top |
O(1) |
|
Remove last price that was added |
pop |
O(1) |
2. You are employed by a software company designing an application for use in customer service telephone call centers. Your job is to implement the data structure used to store the callers on hold. The structure must be able to add a caller to the structure, count the callers on hold (to estimate wait time), and remove the caller that has been waiting the longest when a representative is ready.
|
Queue ADT |
Your choice of linear ADT would be: Stack ADT
|
Linked List |
Your choice of implementation would be: Dynamic Array
|
Operation |
Method in ADT used to implement |
Running time |
|
Add caller to structure |
enqueue |
O(1) |
|
Count callers on hold |
size |
O(1) |
|
Remove next caller to serve |
dequeue |
O(1) |
java.util
Class Vector
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|