UNIVERSITY OF TORONTO
Faculty of Arts and Science
DECEMBER EXAMINATIONS 1997

CSC 108F

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 and 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 = 12 + 8]
--	-------------------

(a)	Each of these program fragments contains at least one logical 
or syntax error. Describe the worst error briefly. (There is intended 
to be just one error in each case, but if you think you have found 
more than one, judge for yourself which is worst.)

public static int f (int x) {
	if (x >= 0)
		return x*12.6;
	else
		return x/0.126;
}




// Sum 1/i**2, for i = 1, 2, ..., N
public static double invSquares (int N) {
	double sum = 0;
	for (int i=1; i<=N; i++)
		sum += 1/(i*i);
	return sum;
}




public static void m (String s) {
	return ("my input is " + s);
}

and in main():
System.out.println (m("hi"));




in main():
int count;
while (true) {
	s = stdin.readLine(); // Assume stdin is defined as usual.
	if (s.equals("quit"))
		break;
	count += 1;
	System.out.println(s);
	}
	System.out.println("number of lines read = " + count);


(b)	Consider the following Java program:

import java.io.*;
public class Wow {
   public static void main (String[] args) throws IOException {

      DataInputStream stdin = new DataInputStream (System.in);

      final int SAVE = 10;
      int temp = 999;
    
      int num = Integer.parseInt (stdin.readLine());
      while (num > 0) {
         if (num < temp) {                  //
            if (num > SAVE) {               //
               temp = num;                  //
               System.out.println (temp);   //
            }                               //
            else                            //
               System.out.println ("-");    //
         }                                  //
         else                               //
            System.out.println ("-");       //

         num = Integer.parseInt (stdin.readLine());
      }
      System.out.println("RESULT: " + temp);
   }
}

i) What does this program output if given the numbers 5 10 15 20 -1, 
in that order, as input?

ii) What does this program output if given the numbers 20 25 5 15 -1, 
in that order, as input?

iii) What does this program output if given the numbers 1000 5 2000 -
1, in that order, as input?

iv) Rewrite the two if-statements (marked by "//") with just one if-
statement that performs the exact same function.


2.	[15 marks = 1 + 2 + 12]
--	-----------------------

Assume that a Fraction class has been defined as follows:

class Fraction {
	private int numerator;
	private int denominator;
	public Fraction (int a, int b) {
		numerator = a;
		denominator = b;
		reduce();
	}

	// Returns this fraction's numerator
	public int getNumerator () {
		return numerator;
	}

	// Returns this fraction's denominator;
	public int getDenominator () {
		return denominator;
	}

	// Prints this fraction.
	public void print () {
		System.out.println(numerator + "/" + denominator);
	}

	// Reduces this Fraction to its simplest form.
	// For example, 6/8 would be reduced to 3/4.
	public void reduce () {
		// Details omitted (but you do not have to complete this method).
	}

	// Returns true if this Fraction equals otherFrac, and false otherwise.
	public boolean equals (Fraction otherFrac) {
		// Must first reduce both myself and fraction otherFrac.
		reduce();
		otherFrac.reduce();
		// Now see if we're equal.
		if (numerator == otherFrac.getNumerator() &&
			denominator == otherFrac.getDenominator())
				return true;
			else
				return false;
	}

	// Divides this fraction in half.
	public void halve () {
		denominator = denominator * 2;
		reduce();
	}
}

(a)	What variables does the method reduce have to examine and 
possibly change?


(b)	How can the equals method compare two Fractions for equality 
when it only has one Fraction parameter?

(c)	For each code fragment below, circle the right answer to 
indicate whether it will run successfully or produce an error message. 
If it runs successfully, state what the output will be. If it produces 
an error message, explain the problem (but do not simply give the 
contents of the error message).

	Fraction f1 = new Fraction(3, 5);
	Fraction f2 = new Fraction(3, 5);
	Fraction f3 = f1;
	if (f1 == f2)
		System.out.println("alpha");
	if (f1 == f3)
		System.out.println("beta");
	if (f1.equals(f2))
		System.out.println("gamma");
	if (f1.equals(f3))
		System.out.println("delta");

                        Runs successfully

                        Produces an error message

	Fraction[] list;
	list = new Fraction[15];
	System.out.print("The numerators are: ");
	for (int i=0; i<15; i++)
		System.out.print(list[i].getNumerator());

                        Runs successfully

                        Produces an error message

	Fraction apple = new Fraction (1, 2);
	Fraction peach = new Fraction (4, 5);
	Fraction pear = apple;
	peach.halve();
	pear.halve();
	apple.print();
	peach.print();
	pear.print();

                        Runs successfully

                        Produces an error message


3.	[20 marks = 10 + 10]
--	--------------------

(a)	Consider a two-dimensional array that contains integers in a 
triangular pattern. The array is square, but only a triangular part is 
used, as in this example:

	2
	1	7
	3	6	8
	4	2	5	3

Write a method that sums the numbers along the perimeter of the 
triangle - the first column, the bottom row and the diagonal. In our 
example, the sum is:

        2 + 1 + 3 + 4 + 2 + 5 + 3 + 8 + 7 = 35.

The first line of the method is given below. Notice that the method 
takes just one argument, the array itself. The array is square, and 
its length is the number of rows and columns.

public static int perimeterSum (int[][] A) {
	// You write the rest:


(b)  An increasing array of integers is an array in which every 
element is greater than the one before it.

i) Which of the following are increasing arrays of integers? Circle 
the correct answers.


	(1, 4, 5, 7)	increasing	not increasing

	(10)		increasing	not increasing 

	(4, 3, 2, 1)	increasing	not increasing 

	(1, 4, 4, 6)	increasing	not increasing 

	(-1, 0, 3)	increasing	not increasing 

	(-10, -5, -8)	increasing	not increasing 


ii) Write a Java method that determines if an array of integers is an 
increasing array of integers. Its only parameter should be an array of 
integers. It should return a boolean value of true if the array is 
increasing, and false otherwise. You can assume that the array has 
been initialized appropriately. (You do not have to write the entire 
program - only one method.)


4.	[15 marks = 1 + 2 + 3 + 6 + 3]
--	------------------------------

Here are a Person class and the beginnings of a FamilyInfo class:

class Person {
	public String name;	// Assume this field is unique for every Person.
	public int birthYear;
	public String mother; 
	public String father;
}

// FamilyInfo class: keeps track of people in a family.
// The data structure used is an array of Persons. 

class FamilyInfo {

	private Person[] list;
	private int familySize; // # of people currently in this list

	// Other methods not shown here would include methods to build a 
	// FamilyInfo, methods for adding new Persons to it, and methods 
	// for searching and printing it.

	// Returns the integer index in our list of the Person with the
	// given 'name', or -1 if that Person isn't in our list.
	private int find (String name) {
		// Details omitted. 
	}

	// Prints the given 'name' and the names of all that Person's maternal
	// ancestors stored in this FamilyInfo. That is, prints the mother,
	// grandmother, great grandmother, and so on, until we have no more
	// information. (After all, we only have information on a finite number
	// of people).
	public void printMaternalAncestors (String name) {
		// Details omitted.
	}
}

 (a)	What kind of variable is "list"? Circle the correct choice.

		instance variable	class variable

(b)  The variable list should not be (and is not) declared public. Why not?

(c)	Say that we have instantiated (created) a FamilyInfo variable 
"myFamily" and stored the following information into it (using methods 
not shown here):

* Peter was born in 1958, and his parents were Katie and Inman.
* Inman was born in 1931 and his parents were Lois and William.

We have no further information about Katie, Lois, or William.

Draw a diagram showing the contents of the myFamily object at this 
stage.



(d)	Fill in the body of the printMaternalAncestors. Assume that 
the method find has already been written and use it to help you. Your 
method can stop printing maternal ancestors when it encounters an 
ancestor not found in the list.



(e)	If we had a FamilyInfo containing k people and we called 
printMaternalAncestors, what is the greatest number of times that the 
find method might have to be called?


Consider a single call to the find method. If the FamilyInfo has k 
people in it, what is the greatest number of elements of list that 
might have to be examined?



5.	[10 marks]
--	----------

Complete this main( ) method to read a list of integers, ending with -1.
Print the second-largest integer in the list.

The list cannot contain -1, but it may contain other negative 
integers. If the largest value appears twice in the list, then that 
value is both the largest and the second-largest. If there are fewer 
than 2 items in the list, your program should print an error message.

public static void main (String[] args) throws IOException {