UNIVERSITY OF TORONTO
Faculty of Arts and Science
APRIL/MAY EXAMINATIONS 2000
CSC 108H1 S
Duration — 3 hours
Examination aids allowed: Textbook (Arnow & Weiss, Introduction to Programming using Java) and API reference (Appendix O from Lewis & Loftus, Java Software Solutions, or the entire book by Lewis & Loftus).
Check that this examination paper has 10 pages (including this cover page but not the empty back cover page).
Answer all questions in the space provided in this paper. When the response requires you to write a program, your marks will depend on the style of your program as well as its correctness. (However, comments are generally not necessary.) All programs must be written in Java.
1. [20 marks = 8 + 12]
Study the program below. There are two questions — (a) and (b) — at the end of the program.
public class Thing {
private static int count = 0;
private String sound = "quiet";
public Thing (String noise) {
sound = noise;
count++;
}
void changeSound (String noise) { sound = noise; }
void makeNoise () { System.out.println(sound); }
public int howMany () { return count; }
public static void main (String[] args) {
Vehicle auto;
Car edsel = new Car();
Car pinto = new Car();
Truck fargo = new Truck();
System.out.println("fargo " + fargo.howFast());
auto = edsel;
fargo.faster();
auto.changeSound("honk honk");
fargo.faster();
auto = fargo;
auto.faster();
pinto.faster();
fargo.faster();
System.out.println("auto " + auto.howFast());
System.out.println("edsel " + edsel.howFast());
System.out.println("pinto " + pinto.howFast());
System.out.println("fargo " + fargo.howFast());
fargo.makeNoise();
edsel.makeNoise();
pinto.makeNoise();
Clock timex = new Clock();
Clock casio = new Clock();
casio.makeNoise();
casio.changeSound("hum");
timex.makeNoise();
casio.makeNoise();
Dog fido = new Dog();
Cat fluffy = new Cat();
Dog rover = new Dog();
fluffy.makeNoise();
System.out.println("fluffy " + fluffy.howFast());
fido.changeSound("howl");
fido.faster();
fluffy.faster();
fido.faster();
System.out.println("fido " + fido.howFast());
System.out.println("fluffy " + fluffy.howFast());
System.out.println("rover " + rover.howFast());
fido.makeNoise();
fluffy.makeNoise();
rover.makeNoise();
System.out.println("auto " + auto.howMany());
System.out.println("timex " + timex.howMany());
System.out.println("fido " + fido.howMany());
System.out.println("pinto " + pinto.howMany());
System.out.println("main " + count);
}
}
class Machine extends Thing {
public Machine (String noise) { super(noise); }
}
class Clock extends Machine {
public Clock() { super("tick"); }
}
class Vehicle extends Machine {
private static int count = 0;
private int speed = 0;
public Vehicle (int speedValue, String noise) {
super(noise);
speed = speedValue;
count++;
}
public void faster () { speed += 10; }
public int howFast() { return speed; }
public int howMany() { return count; }
}
class Car extends Vehicle {
public Car () { super(40, "beep"); }
}
class Truck extends Vehicle {
public Truck() { super(20, "honk"); }
}
class Animal extends Thing {
private String speed;
public Animal (String speedValue, String noise) {
super(noise);
speed = speedValue;
}
public void faster () {
if (speed.indexOf("fast") < 0)
speed = "fast";
else
speed = "very " + speed;
}
public String howFast() { return speed; }
}
class Cat extends Animal {
public Cat () { super("very slow", "meow"); }
}
class Dog extends Animal {
public Dog () { super("fast", "bark"); }
}
(a) Draw a diagram showing the inheritance relationships for the classes in the program above ("the class hierarchy tree").
(b) When the program runs, what output does it produce?
You may write the output either in the space below or beside the line in the main( ) method that produces it. Your answer must make it clear exactly which lines of output are printed, and in what order.
2. [10 marks]
A rule commonly used to make English spelling easier is, "i before e except after c". This rule says that "ie" is right and "ei" is wrong, unless there is a "c" just before the two letters; thus, "cei" is always right and "cie" is always wrong. For example, "thief" and "ceiling" are correctly spelled, but "cieling" and "theif" are wrong. The rule doesn’t work in all cases, but we’ll ignore that.
Write a program to enforce this rule. Your program will read a sequence of lines from the standard input, ending when the line "quit" is read. Each line is then changed (if necessary) so that it agrees with the spelling rule, and printed. For example, consider this input line:
The theif is on their cieling, being weighed wierdly.
The corresponding output is:
The thief is on thier ceiling, bieng wieghed wierdly.
Notice that our "rule" is wrong about four of the six words containing an "ie" or "ei"!
The program is begun for you here:
import java.io.*;
public class Spell {
public static void main (String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// You write the rest.
3. [20 marks = 4 + 4 + 6 ´ 2]
Here is a program that runs without error. There are questions below it to be answered. Read all the parts before answering.
import java.io.*;
public class Test {
public static void main (String[] args) throws IOException {
BufferedReader in = new BufferedReader (new InputStreamReader
(System.in));
int n = Integer.parseInt(in.readLine());
doSomething(n);
}
public static void doSomething (int n) {
int count = 1;
int sum = 0;
for (int i=1; i<=n; i++) {
for (int j=0; j<n/2; j+=3) {
count++;
sum += count; // A
}
count += 5;
for (int k=0; k<n-1; k+=2) {
count++;
for (int j=k; j<k+1; j++) {
count++;
sum %= count; // B
}
}
}
System.out.println ("Count is: " + count);
System.out.println ("Sum is: " + sum);
}
}
(a) If the input contains one line consisting of the string "2", what output does the program produce?
You may use the space at the bottom of the next page for rough work, if you need it.
(b) If the input contains one line consisting of the string "3", what output does the program produce?
You may use the space at the bottom of the next page for rough work, if you need it.
(c) If the input is "3", as in (b), how many times is the line labelled "//A" executed? Circle the value that best represents the correct answer.
2 3 4 5 6 7 8 9 10 27
(d) If the input is "3", as in (b), how many times is the line labelled "//B" executed?
2 3 4 5 6 7 8 9 10 27
(e) If the input is "10", how many times is the line labelled "//A" executed?
5 9 10 11 15 20 25 50 100 1000
(f) If the input is "10", how many times is the line labelled "//B" executed?
5 9 10 11 15 20 25 50 100 1000
(g) If the input contains a string representing the number N, how many times is the line labelled "//A" executed? Circle the function that most closely resembles the behaviour of the program, ignoring constant factors. (That is, we are looking for "big-O" equality, not an exact match.)
1 log N sqrt(N) N N2 N3 N log N N2 log N
(h) If the input contains a string representing the number N, how many times is the line labelled "//B" executed?
1 log N sqrt(N) N N2 N3 N log N N2 log N
4. [15 marks = 5 + 10]
Here is a Student class with some crucial parts omitted. Parts (a) and (b) ask you to supply these parts.
import java.util.*;
public class Student {
// Each year's marks are stored in a Vector. There are four years of
// study, so the Student has an array of four Vectors.
private static final int NUM_YEARS = 4;
private Vector[] marks = new Vector[NUM_YEARS];
private String name;
private int studentNumber;
public Student (String name, int studentNumber) {
// OMITTED -- see part (a).
}
// addMark: add the given mark to this Student's record for the
// given year.
public void addMark (int mark, int year) {
Integer markObject = new Integer(mark);
marks[year].addElement(markObject);
}
// equals: does another Student have the same contents as this one?
public boolean equals (Object otherStu) {
// OMITTED -- see part (b).
}
}
(a) The body of the constructor for the Student class is omitted. Complete the constructor here. (Hint: You must initialize all the instance variables.)
(b) The body of the equals( ) method is omitted. Complete it here. (Reminder: An equals( ) method checks whether all the data belonging to two objects are the same, and in the same order.)
5. [10 marks]
A position in space can be given by three "coordinates". For example, a point 3.0 m (metres) forward from my nose, 1.2 m to the left, and 5.3 m upwards is uniquely specified (provided that we know where my nose is and which way I’m looking). Or a position 110 m north of the centre of the Bloor-Yonge intersection, 42 m east, and 87 m down into the ground is also clearly identifiable. We might refer to these positions briefly as (3.0, 1.2, 5.3) and (110, –42, –87); in the latter case, two of the coordinates are negative, assuming that east and down are both negative. We can’t compare the two sets of coordinates directly, because in one case we use my nose and in the other the Bloor-Yonge intersection as the starting position or "origin".
Here we will assume that we have a standard origin, and that we always use metres as units. With this convention, we can use the Euclidean formula for the distance between any two points. If one point, PA, is (x1, x2, x3) and the other, PB, is (y1, y2, y3), then the distance between them is the square root of the sum of the squares of their differences in each direction:
distance = sqrt ( (x1 – y1)2 + (x2 – y2)2 + (x3 – y3)2 )
It is natural to represent the positions PA and PB as 3-element arrays of doubles in Java. That technique is used in the method begun below to calculate the distance between two points.
Complete the method. Its prototype is given as a starter for you.
// distance: return the distance between two points,
// each represented as arrays of three coordinates.
public static double distance (double[] pA, double[] pB) {
// You write the rest.