Midterm Examination Solution
Com 1201 Spring 2003 Jeff Raab
Section
1 Short answers
(2) 1. An object can be of only one class, but it may be of many different types .
(2) 2. The Proxy design pattern is used to define a class whose data member(s) are used to perform some or all of the work of the methods in the class
(2) 3. The three types of abstractions that are used to define new types of Java objects are
class , interface , and abstract class .
(2) 4. The Java primitive type named byte represents an integer in the range [-128, 128). The Java class named Byte is defined to have one data member of type byte. The number of Byte objects that can be used in a program is limited only by memory .
(2) 5. If a programmer wants a data member in a class to be not only available to be used by other classes in its package, but to be available to be used by any class in any package, the programmer must use the keyword public to set the level of access for the data member.
(2) 6. A Java class may be defined to implement as many interfaces as you like, but that class must extend exactly one other class.
(2) 7. In Java, it is standard practice to throw an exception if one of the preconditions for a method is violated.
(2) 8. Circle all of the following parts of a class definition that add to the public interface for the class being defined:
|
a. |
public data members |
b. protected data members
|
c. |
public constructors |
d. private methods
(2) 9. Circle the correct value for the following expression:
(set{0, 1, 2, 3, 4 } + set{1, 2, 3}) ฎ excluding(4) ฎ size()
a. 3
|
b. |
4 |
c. 7
d. 8
(2) 10. Circle all the things that are created in the execution of the following Java statement:
Object element = new Object();
a. new class
|
b. |
new object |
|
c. |
new reference variable |
d. new container to hold objects
Section
2 UML specification
(20) Draw a UML class hierarchy diagram that shows the details of all of the types of object involved in the below class definitions, and that shows the relationships between those types. Note that the bodies of the methods have been replaced with ellipses ( ) to eliminate details that are not necessary in your diagram.
public
interface Buf {
public void tib(double moy);
}
public
abstract class Cug implements Buf {
protected boolean med = false;
protected double rop;
public Cug() { ... }
public void beb() { ... }
public abstract void tib(double moy);
}
public
class Hig extends Cug {
private Cug saz;
public Hig(Cug yab) { ... }
public void tib(double moy) { ... }
private double nal() { ... }
}
public
interface Erk extends Buf {
public Hig urb(double dib);
public void fim();
}
Please draw your diagram on the following page.
Section
2 answer
The following diagram contains all of the parts I expected to see in
your diagram:
Please note that the
dotted line with the white arrow means implements,
while the solid like with the white arrow means extends. Classes extend classes. Interfaces extend interfaces. Classes implement interfaces.
The diamond-anchored
line with the black arrow shows that the class with the diamond contains a data
member of the type the arrow points to.
Methods that take in as input, or return as output, an object of a type
dont have a diamond arrow pointing to that type. For instance, there is no line from Erk to Hig though the urb methods
returns a Hig.
Section 3 Analysis
Analyze each function. Write the number of * characters it actually prints, in terms of the values of any inputs to the function. Provide an asymptotic analysis of the number of * characters printed, in terms of the values of any inputs to the function. 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 the code of each function before performing your analysis of it. Assume that the values of any input variables will not be less than 0.
(5) public void printStars1(int m,
int n) {
for
(int i = 0; i < n; i++) {
System.out.println(***);
for (int j = 0; j < m; j++) {
System.out.println(*);
}
}
System.out.println(**);
}
The exact number of * characters printed is 3n + mn + 2 .
Using asymptotic notation, the number of * characters printed is O(mn) .
(5) public void printStars2(int
n) {
for
(int i = 0; i < 2 * n; i += 2) {
System.out.println(****);
}
}
The exact number of * characters printed is 4n .
Using asymptotic notation, the number of * characters printed is O(n) .
Section
3 Analysis
Analyze each function. Write the number of * characters it actually prints, in terms of the values of any inputs to the function. Provide an asymptotic analysis of the number of * characters printed, in terms of the values of any inputs to the function. 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 the code of each function before performing your analysis of it. Assume that the values of any input variables will not be less than 0.
(5) public void printStars3(int
n) {
System.out.println(***);
for
(int i = n; i > 1; i = i / 2) {
System.out.println(**);
}
}
The exact number of * characters printed is 2 log n + 3 .
Using asymptotic notation, the number of * characters printed is O(n) .
(5) public void printStars4(int
n) {
System.out.println(**);
for
(int i = 0; i < n; i++) {
System.out.println(**);
System.out.println(*);
}
System.out.println(*);
}
The exact number of * characters printed is 3 + 3n .
Using asymptotic notation, the number of * characters printed is O(n) .
Section
3 Analysis
Analyze each pair of functions below, using asymptotic notation, and circle the function out of the two that represents a more efficient running time or use of memory, if any. If the functions represent equal efficiency, do not circle either of them.
|
(2) |
3 * n2 |
is O(n2) |
and |
2 * n3 |
is O(n3) |
|
(2) |
n * log n |
is O(n log n) |
and |
4n |
is O(n) |
|
(2) |
2n3 + n3 * 256 |
is O(n3) |
and |
n * n * n * n |
is O(n4) |
|
(2) |
n128 |
is O(n128) |
and |
2n |
is O(2n) |
|
(2) |
4 * log3 n |
is O(log3 n) |
and |
3 * log4 n |
is O(log4 n) |
Section
4 Java programming
|
WordJumble |
|
# char[] letters |
|
+ WordJumble(String s) + char getLetter(int i) + void jumble() void swap(int i, int j) + String toString() |
(30) Write a class that implements the given UML specification.
The primitive type char represents a single character: letter, number, punctuation mark, &c. It is very much like an int, and you should treat it like an int.
A summary of the HTML documentation for the String class is given at the end of this exam. Note especially the methods named toCharArray and length in the String class documentation.
The constructor must take in a String as input and store the characters of the String, in order, in a new array of char assigned to the data member named letters. It is a precondition for the constructor that the given String is not null, and if that invariant is violated you must throw a RuntimeException with a detail message describing the error.
The getLetter method must return the char in letters that is at the given index i. It is a precondition for the method that the given value is a valid index in the array, and if that precondition is violated you must throw a RuntimeException with a detail message describing the error.
The jumble method must perform the following algorithm:
for each
index i in the array named letters:
choose
an index j in the range [0, letters.length)
swap
the values in letters
at indices i and j
You do not have to ensure that i and j are different values.
The following expression will select a number at random in the range [0, k):
(int)(Math.random()
* k)
The private method named swap must swap the values in letters at the given indices i and j. There are no preconditions for the swap method.
The toString method must return a String that contains the values in letters in order.
Write your class definition on the next pages. You must follow the guidelines for writing code as have been posted on the course website, including documentation.
You do not have to write tests for
this class!
Section 4 answer
/**
* Represents text that can be jumbled.
* @author Jeff Raab
*/
public class WordJumble {
/** Letters in this. */
protected char[] letters;
/**
* Constructs a new word
jumble.
* @param s String
containing the text for the word jumble
*/
public WordJumble(String s) {
if (s == null) {
throw new RuntimeException(String is null);
}
letters = s.toCharArray();
}
/**
* Returns the letter in this at the given
index.
* @param i index of
letter
* @example (new
WordJumble(Fox)).getLetter(-1) is an error
* @example (new
WordJumble(Fox)).getLetter(1) returns o
* @example (new
WordJumble(Fox)).getLetter(3) is an error
*/
public char getLetter(int i) {
if ((i < 0) || (i >= letters.length)) {
throw new RuntimeException(Index out of bounds);
}
return letters[i];
}
/**
* Jumbles the letters in
this.
* @example (new
WordJumble(Grape)).jumble() might result
* in letters in the order aeGpr
*/
public void jumble() {
for (int i = 0; i < letters.length; i++) {
swap(i, (int)(Math.random() * letters.length));
}
}
Section 4 answer
/**
* Swaps the letters in this at the given
indices.
* @param i first index of
letters to swap
* @param j other index of
letters to swap
* @example (new
WordJumble(Box)).swap(0, 2) results in
* letters in the
order xoB
* @example (new
WordJumble(Box)).swap(1, 1) results in
* letters in the
order Box
*/
private void swap(int i, int j) {
char temp = letters[i];
letters[i] = letters[j];
letters[j] = temp;
}
/** Returns a String version of this. */
public String toString() {
return new String(letters);
}
}
java.lang
Class
String
java.lang.Object
| +--java.lang.String
All Implemented Interfaces:
CharSequence, Comparable, Serializable
|
Constructor Summary |
|
|
|
|
|
|
|
|
|
|
|
Method Summary |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|