Midterm Examination
Com 1201 Fall 2002 Jeff Raab
Name
___________________________________ ID# ______________________
Introduction
This is a closed book, closed notes examination. Please read all of the instructions for each problem before you provide your solution. If you have any questions regarding a particular problem, please raise your hand and the test proctor will help you understand the requirements for the problem. You have one class period to complete the problems on this examination.
Grading
|
Section |
Points |
Score |
|
1 |
25 |
|
|
2 |
30 |
|
|
3 |
20 |
|
|
4 |
25 |
|
|
Total |
100 |
|
|
Letter grade |
|
|
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.
Write your method on the next page.
Section
1 answer
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
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 __________________________ .
Asymptotically, the number of * characters printed is __________________________ .
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 __________________________ .
Asymptotically, the number of * characters printed is __________________________ .
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.
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 __________________________ .
Asymptotically, the number of * characters printed is __________________________ .
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 __________________________ .
Asymptotically, the number of * characters printed is __________________________ .
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).
Your choice of linear ADT would be: Stack ADT Queue ADT
Your choice of implementation would be: Dynamic Array Linked List
|
Operation |
Method in ADT used to implement |
Running time |
|
Add price to structure |
|
|
|
Get last price added to structure |
|
|
|
Remove last price that was added |
|
|
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.
Your choice of linear ADT would be: Stack ADT Queue ADT
Your choice of implementation would be: Dynamic Array Linked List
|
Operation |
Method in ADT used to implement |
Running time |
|
Add caller to structure |
|
|
|
Count callers on hold |
|
|
|
Remove next caller to serve |
|
|
java.util
Class Vector
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|