University of Toronto
csc148F--Introduction to Computer Science, Fall 1997
Second Test -- Horton's evening section

 
Duration: 		 50 minutes 
Aids allowed: 		 None

 
Family Name: 		      
First Name:  		      
Student # :		 	  
Tutor (circle one): 		 
       Cyrus Hsia    Catherine Stinson    Shingo Takagi    Jamie Hale

 
		 1.       / 10 
		 2.       /  9 
		 3.       /  9 
		 4.       /  8 
		 Total    / 36

Question 1

[10 marks in total]

For integers , let S(n) be some statement. For the purpose of this question, it does not matter what this statement is.

For each proof outline given below, state whether or not it is a valid approach to proving that S(n) is true for all integers . In other words, if you filled in the details, would you be able to conclude that S(n) is true for all integers .

Circle YES or NO. If you circle NO, you must give your reason in order to earn any marks.

(a)  Is this a valid approach to doing the proof?

Proof:
BASE CASE: Prove S(0) is true.
Let k > 0 be an arbitrary integer.
INDUCTION HYPOTHESIS: Assume S(k) is true.
INDUCTION STEP: Prove S(k+1) is true.

       No.  The base case doesn't connect to the induction part.

 
(b)  Is this a valid approach to doing the proof?

Proof:
BASE CASE: Prove S(0) is true.
Let be an arbitrary integer.
INDUCTION HYPOTHESIS: Assume S(k-1) is true.
INDUCTION STEP: Prove S(k) is true.

       Yes.

 
(c)  Is this a valid approach to doing the proof?

Proof:
BASE CASE: Prove S(0) is true and S(1) is true.
Let be an arbitrary integer.
INDUCTION HYPOTHESIS: Assume S(k) is true.
INDUCTION STEP: Prove S(k+2) is true.

       Yes.

 
(d)  Is this a valid approach to doing the proof?

Proof:
BASE CASE: Prove S(0) is true.
INDUCTION HYP: Assume S(k) is true for all integers .
INDUCTION STEP: Prove S(k+1) is true.

       No.  The base case assumes the whole theorem!

 
(e)  Is this a valid approach to doing the proof?

Proof:
BASE CASE: Prove S(0) is true.
Let be an arbitrary integer.
INDUCTION HYP: Assume S(j) is true for all integers j where .
INDUCTION STEP: Prove S(k+1) is true.

       Yes.

Question 2

[9 marks in total]

Consider the following Java method:

      public static int smallest (int[] a, int size) {
          int small = 1000;
          int i = 0;

          while (i != size) {
             if (a[i] < small)
                   small = a[i];
             i++;
          }
          return small;
      }

There are several good solutions to this question. Below two are shown. Their answers cannot be mixed and matched though!

(a)  [5 marks]
Give appropriate preconditions and postconditions for this method.
Preconditions:

Solution (1):
1 <= size <= a.length
at least one value in a[0..size-1] is less than 1000

Solution (2):
0 <= size <= a.length

Postconditions:

Solution (1)
the value returned is the smallest value in a[0..size-1] inclusive.

Solution(2):
if there is any value in a[0..size-1] inclusive that is < 1000
the smallest of the values in a[0..size-1] inclusive is returned;
otherwise, 1000 is returned.

 
(b)  [4 marks]
Fill in each blank with a comparison operator (that is, one of: ) to make each of the following conditions a loop invariant.

i size.

If small < 1000 then small a[j] for all integers j such that 0 j i.

If small < 1000 then small = a[j] for some integer j such that 0 j i.

Question 3

[9 marks in total]

Consider the following Java method:

      private static int power (int x, int n) {
          System.out.println ("x=" + x + " n=" + n);
          if (n == 0)
              return 1;
          else {
              int k = power (x*x, n/2); // The `/' does integer division.
              System.out.println ("k=" + k);
              if ( (n%2) == 0 )         // Checks if n is even.
                   return k;
              else
                   return x * k;
          }
       }

 
(a)  [7 marks]
What output would result from the following statement:
System.out.println (power(2,6) + " is the final answer.");

   THE OUTPUT IS:

       x=2 n=6
       x=4 n=3
       x=16 n=1
       x=256 n=0
       k=1
       k=16
       k=64
       64 is the final answer.

 
(b)  [2 marks]
If you were to prove the power method correct, what would you do induction on?

One would do induction on n.

Question 4

[8 marks in total]

The StrNode class, given here, can be used for a linked list of strings.

      class Node {
          public String s;
          public Node next;

          // constructor: details omitted
      }

Write a method called longest, which, given a linked list of strings, will return the length of the longest string in the list. If the list is empty, it should return 0. Your solution must be recursive.

Recall that s.length() gives the length of a string s.

      public static int longest (Node first) {


      ANSWER:


           if (first==null)
               return 0;
           else
               return Math.max(first.s.length(), longest(first.next));

      }