UNIVERSITY OF TORONTO
	Faculty of Arts and Science
	APRIL/MAY EXAMINATIONS 1998
	CSC 108S
	Duration - 3 hours

	Examination aids allowed: textbook only
		(Lewis & Loftus, Java Software Solutions).

Check that this examination paper has 11 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 = 5 + 5 + 5 + 5]

Write program fragments or methods as required by the specifications 
below. Unless stated otherwise, the parts of this question are not 
connected with each other.

Parts (a) and (b) refer to this class:

class Student {
   private String name;
   private int mark;
   public Student (String name, int mark) {
      this.name = name;
      this.mark = mark;
   }
   public getMark () { return mark; }
}

(a)	A fragment to declare an integer size, read size from input, 
and declare an array students with size elements of type Student. (Do 
not read data into the array: see part (b). Do assume that an input 
data stream stdin has been declared and initialized for you.)

(b)	A fragment to read data into all the elements of the array 
students from part (a).

(c)	A method printMulti to print a line consisting of k copies of 
the character c, where k and c are parameters. For example, the call 
printMulti(6,'*') would print the line "******".

(d)	A method printBars to print a series of lines. Line number p 
must contain a number of asterisks given by count[p], where count is 
an array of integers and is a parameter of the method. For example, if 
the array thisMany has the value {4, 1, 3}, then printBars(thisMany) 
would print this output:

   ****
   *
   ***

	You must use the method printMulti, from part (c), in printBars.

2.	[20 marks]

A program implementing a new board game (not Othello) requires a 
method to decide whether a position is valid. An interface for the 
game contains the abstract method

   boolean valid_position ( boolean [][] board, int row, int column ) ;

Your task in this question is to write an implementation for the 
method valid_position. 

The game board is represented by the two-dimensional array board, the 
first parameter of valid_position. We consider board[i][j] to 
represent the square in row i and column j of the "real" board. If 
board[i][j] is true, then this square is occupied; if board[i][j] is 
false, then this square is unoccupied.

A square board[i][j] is a valid position if

* it is unoccupied,

* all squares on row i - the row passing through board[i][j] - are 
unoccupied,

* all squares on column j - the column passing through board[i][j] - 
are unoccupied,

* all squares on the two diagonals passing through board[i][j] are 
unoccupied.

Otherwise, board[i][j] is not a valid position.

The method valid_position returns true if board[row][column] is a 
valid position; otherwise valid_position returns false.

For example, if X represents an occupied square, blank represents an 
unoccupied square and O represents the square board[row][column], then 
valid_position should return true for the board on the left and false 
for the board on the right (because there is an occupied square on the 
diagonal through O).

	- o - -		- o - -
	- - - x		- - - x
	x - x -		x - - x

You may assume without checking that the array board is rectangular. 
That is, each row of board has the same number of columns. But don't 
assume that the number of rows and columns is the same.

You may also assume that error checking has been done elsewhere, so 
that 0 <= row < board.length and 0 <= column <= board[0].length.

3.	[20 marks = 4 + 8 + 8]

The organizers of a marathon race want to give blue ribbons to the 
fastest runners. They have an input file containing the name and 
completion time for each competitor, something like this:

	B. Kidd
	137

The completion time gives the number of minutes taken, as an integer. 
The input data for the runners is provided in random order (not sorted 
by name or time). We will use this class to represent the runners:

   class Runner {
      public String name;
      public int time;
      public Runner (String n, int t) { name = n; time = t; }
   }

The "name" and "time" fields (data members of the class) are public, 
so you do not need "get" or "set" methods to access them.

(a)	Write a fragment of a "main" method to declare an array 
"runners" and store the information from the data file in the array. 
Assume:

* an input stream "stdin" has already been declared and initialized.

* there are not more than 1000 runners. Declare a variable "rnum" to 
contain the actual number of runners.

* the input data are terminated by "QUIT" in the place of a runner's 
name.

(b)	First, the race organizers decide to give blue ribbons to the 
runners with times not more than 10% longer than the fastest runner's 
time. Write a fragment of code to print these runner's names, assuming 
the array from part (a) has already been declared and filled with the 
data about the runners.

(c)  Next, the race organizers change their minds, and decide to give 
blue ribbons to the fastest 10% of the runners - that is, the ones 
whose completion times are shorter than at least 90% of the other 
runners' times.

Write a method (not a fragment of "main()") to print the names of 
these runners. Your method must take two parameters: an array of type 
Runner[], and an int containing the number of runners stored in the 
array, corresponding to the variable rnum in part (a).

In this part, we have one additional rule: the output must list the 
selected runners in order of appearance in the array parameter. In 
other words, you may not sort the list of runners. Instead, your 
solution can be based directly on the definition of "fastest" given in 
the first paragraph [of part(c)].

4.	[20 marks = 6 + 4 + 4 + 3 + 3]

The questions below are about a program that is [included after
part (e)]. The program compiles and runs successfully. After 
the program is a data file that is referred to by some of the 
questions.

(a)  What is the output from this program, given this input file?

(b)  For each query handled in the "Read queries" section of the 
"main" method, state how many times the "if" statement labelled "LINE 
A" is executed. Assume that the input data are the same as in the file 
below.

(c)  How many accesses to the "address" field of a Residence object 
are required by the call of the "listHouses" method? Again, assume 
that the input data are the same as in the file below.

(d)	If the total number of Residences in the "database" is N, how 
many times on average is LINE A executed during a single query in the 
"Read queries" section of "main"? Assume that all queries succeed - 
that is, that there are no queries about addresses that are not 
actually in the database. Assume also that you are dealing with a 
typical data file, not with the specific example file used in parts 
(a) to (c).

(e)	What additional information would you need besides the total 
number of Residences in the "database", in order to say how many 
"address" fields on average need to be accessed by the "listHouses" 
call?

Here is the program discussed in the questions above:

import java.io.*;

abstract class Residence {
   // Assume that the input will never contain more than SIZE items.
   private static final int SIZE = 100;
   private static Residence[] list = new Residence[SIZE];
   private static int listLength = 0;

   private String address;

   protected static void addToList (Residence item) {
      list[listLength++] = item;
   }

   public Residence (String address) {
      this.address = address;
      addToList (this);
   }

   abstract public String getCosts ();

   public static String lookup (String address) {
      for (int i = 0; i < listLength; i++)
         if (list[i].address.equals(address))			// LINE "A"
            return list[i].address + " " + list[i].getCosts();
      return address + " not found";
   }

   public static void listHouses () {
      System.out.println ("Houses:");
      for (int i = 0; i < listLength; i++)
         if (list[i] instanceof House)
            System.out.println (list[i].address);
   }

   public static void listApartments () {
      System.out.println ("Apartments:");
      for (int i = 0; i < listLength; i++)
         if (list[i] instanceof Apartment)
            System.out.println (list[i].address);
   }
}

class House extends Residence {
   private double price;
   private double taxes;

   public House (String address, String price, String taxes) {
      super (address);
      this.price = Double.valueOf(price).doubleValue();
      this.taxes = Double.valueOf(taxes).doubleValue();
   }

   public String getCosts () {
      return "price: " + price + ", taxes: " + taxes;
   }
}

class Apartment extends Residence {
   private double rent;

   public Apartment (String address, String rent) {
      super (address);
      this.rent = Double.valueOf(rent).doubleValue();
   }

   public String getCosts () {
      return "rent: " + rent;
   }
}

public class Test {
   public static void main (String[] args) throws IOException {
      BufferedReader in = new BufferedReader (new InputStreamReader(System.in));

      // Read the "database" of housing information.
      while (true) {
         String address = in.readLine();
         if (address.equals ("DONE")) break;
         String housingType = in.readLine();
         if (housingType.equals ("house")) {
            String price = in.readLine();
            String taxes = in.readLine();
            new House (address, price, taxes); // The return value is discarded.
         }
         else { // It's an apartment.
            String rent = in.readLine();
            new Apartment (address, rent);
         }
      }

      // Read queries about the database.
      while (true) {
         String address = in.readLine();
         if (address.equals ("QUIT")) break;
         System.out.println (Residence.lookup (address));
      }

      // Summarize database.
      Residence.listHouses();
      Residence.listApartments();
   }
}

Here is the data file to be read as input by the program. To save 
space, the two or three lines of data for each Residence are separated 
by vertical bars '|' rather than by newlines.

10 Mary St.|house|250000|3000
147 Peter St.|apartment|850
99 Ellesmere Road|apartment|700
2 Yonge St.|house|300000|4000
3987 Finch Ave.|apartment|980
4 Parkdale Ave.|house|180000|2100
DONE
10 Mary St.
4 Parkdale Ave.
99 Ellesmere Road
12 Amelia Court
QUIT