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;
}

**
Type error: return type is integer, but return expression is of
            type double.
**

----------
// 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;
}

**
Logical error: 1/(i*i) always truncates because this uses integer
               division.  1/(i*i) is always 0 for i>1.

Note: To fix this you must cast using one of the following:
               sum += 1.0/(i*i);
               sum += (double)1/(i*i);
               sum += 1/(double)(i*i);
**

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

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

**
Return type error: println wants a String to print, but m("hi")
            doesn't return anything.  The return type for
            method m should be String.
**

----------
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);
**
Initialization error: count isn't initialized to 0 before the loop starts.
**

(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?

**
-
-
15
-
RESULT: 15
**

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

**
20
-
-
15
RESULT: 15
**

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

**
-
-
-
RESULT: 999
**

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

**
if (num < temp && num > SAVE) {
   temp = num;
   System.out.println (temp);
}
else {
   System.out.println ("-");
}
**

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?

**
numerator and denominator of the fraction being reduced.
**

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

**
The two fractions compared are (1) the parameter, and
(2) the fraction whose equals method is being called.
**

(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
**
Circle "Runs successfully"
Output: beta
        gamma
        delta
**

	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
**
Circle "Produces an error message"
Reason: Because the elements of "list" have not been initialized.
**

	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
**
Circle "Runs successfully"
Output: 1/4
        2/5
        1/4
**

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:

**
   int sum = 0;

   // The left-hand side (the first column)
   for (int i=0; i<A.length; i++)
      sum += A[i][0];

   // The bottom row, except the first element
   for (int i=1; i<A.length; i++)
      sum += A[A.length-1][i];

   // The diagonal, except the first and last elements
   for (int i=1; i<A.length-1; i++)
      sum += A[i][i];

   return sum;
**

(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
**
increasing
**

	(10)		increasing	not increasing 
**
increasing
**

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

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

	(-1, 0, 3)	increasing	not increasing 
**
increasing
**

	(-10, -5, -8)	increasing	not 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.)

**
static boolean isIncreasing (int[] A) {
   for (int i=1; i<A.length; i++)
      if (A[i] <= A[i-1])
         return false;
   return true;
}
**

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
**
instance variable
**

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

**
It's used within the class to represent the family, but there are other
ways to represent a family, and we might want to change our choice later;
that would be impossible if other software has access to the 
representation.
**

(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.

**
Peter 1958 Katie Inman | Inman 1931 Lois William | 2 | methods...
**

(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.

**
while (true) {
   System.out.println (name);
   int where = find (name);
   if (where == -1)
      return;
   name = list[where].mother;
}
**

(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?

**
k+1
**

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?

**
k
**

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 {

**
   DataInputStream stdin = new DataInputStream (System.in);

   String line = stdin.readLine();
   int first = Integer.parseInt (line);
   if (first == -1) {
      System.out.println ("error");
      return;
   }

   line = stdin.readLine();
   int second = Integer.parseInt (line);
   if (second == -1) {
      System.out.println ("error");
      return;
   }

   if (first < second) {
      int temp = first;
      first = second;
      second = temp;
   }

   while (true) {
      line = stdin.readLine();
      int next = Integer.parseInt (line);
      if (next == -1)
         break;
      if (next >= first) {
         second = first;
         first = next;
      }
      else if (next > second) {
         second = next;
      }
   }
   System.out.println (second);
}
**