CS 10: Introduction to Computer Programming

Final Examination

Open-Book, 3 hours, Spring 1997

General Instructions

Read each question carefully.
Make sure that you clearly understand a question before answering it.
Please put your answer to each question on its page.
You may wish to work out an answer on scratch paper before writing it on your answer page; answers that are difficult to read may lose points for that reason.

Name:

Perm:

Question	Value	Score
1	8
2	8
3	18
4	24
5	16
6	16
7	10
Total	100

1. Give an equivalent sequence of Java statements that does not use the for statement. If it cannot be done, say "It cannot be done."

int xPos = 25;

      for ( int count = 1; count <= 10; count++ ) {
         if ( count == 5 )
            continue;
         g.drawString( Integer.toString( count ), xPos, 25 );
         xPos += 10;
      }

Solution:

int xPos = 25, count = 1;

      while ( count <= 10 ) {
         if ( count != 5 ) {
             g.drawString( Integer.toString( count ), xPos, 25 );
             xPos += 10;
                 }
          count++;
      }

2. Give an equivalent sequence of Java statements that does not use the switch statement. If it cannot be done, say "It cannot be done."

switch (count) {

case 0: case 1: case 4: case 5: case 6: case 7: case 8:

newCell[i][j] = DEAD;

break;

case 3:

newCell[i][j] = ALIVE;

break;

case 2:

newCell[i][j] = cell[i][j];

break;

}

Solution:

if ( count == 2 )

newCell[i][j] = cell[i][j];

else if ( count == 3 )

newCell[i][j] = ALIVE;

else if ( 0 <= count && count <= 8 )

newCell[i][j] = DEAD;

3. Create a class Rectangle. The class has attributes length and width, each of which defaults to 1. It has a method that calculates the area of the rectangle. It has set and get methods for both length and width. The set method should verify that length and width are each floating-point numbers larger than 0.0 and less than 20.0. Rectangle also has a predicate method square that returns true if and only if the rectangle is square.

Solution:

public class Rectangle {

private float length, width;

public Rectangle() {

setLength( (float) 1);

setWidth( (float) 1);

}

public Rectangle(float l, float w) {

setLength(l);

setWidth(w);

}

public float getLength() { return length; }

public float getWidth() { return width; }

    public void setLength(float l) {
        length = l;
        if ( l < 0.0 || l > 20.0 )
            length = (float) 0.0;
    }

    public void setWidth(float w) {
        width= w;
        if ( w < 0.0 || w > 20.0 )
            width = (float) 0.0;
    }

public float area() { return length * width; }

public boolean square() { return length == width; }
}

4. Create a class IntegerSet. Each object of the class can hold integers in the range 0 through 100. A set is represented internally as an array of ones and zeros. Array element a[i] is 1 if i is in the set. Array element a[i] is 0, otherwise. For example, for the set {3, 5, 7, 10} a[3] is 1, a[5] is 1, a[7] is 1, and a[10] is 1; all other elements of a are 0.

Provide the following methods:

A no-argument constructor that initializes a set to the "empty" set (i.e., a set that has no integers in it).

Method union creates a third set that is the union of the 2 existing sets (i.e., an element of the third set's array is set to 1 if that element is 1 in either, or both, of the existing sets; otherwise the element of the third set is set to 0).

For example, if a represents the set {0, 2, 4} and b represents the set {2, 3, 4, 5} then a.union(b) represents the set {0, 2, 3, 4, 5}.

Method insertElement inserts a new integer k into a set (by setting a[k] to 1). For example, if a represents the set {0, 2, 4} then a.insertElement(3) modifies a to represent the set {0, 2, 3, 4}.
Method deleteElement deletes integer m (by setting a[m] to 0).
Method print prints a set as a list of numbers separated by spaces, 10 to a line. Print only those elements that are in the set. Print "---" for an empty set. For example, for the set {3, 5, 7, 10}, print would produce the line:

3 5 7 10

public void print(Graphics g) { ... }

and uses the

drawString

method to print the elements onto the

Graphics

object,

Method isEqual returns true if and only if the two sets are equal (i.e., have exactly the same elements).

Solution:

import java.awt.*;

public class IntegerSet {

final static int SIZE = 100;

int a[];

    public IntegerSet() {
        a = new int[SIZE + 1];
        for (int i = 0; i < SIZE; i++)
            a[i] = 0;
    }

public IntegerSet union(IntegerSet s) {
IntegerSet u = new IntegerSet(); // initialize to empty

        for (int i = 0; i <= SIZE; i++)
            if (a[i] == 1 || s.a[i] == 1)
                u.a[i] = 1;
        return u;
    }

    public void insertElement(int e) {
        if ( 0 <= e && e <= SIZE)
            a[e] = 1;
    }

    public void deleteElement(int e) {
        if ( 0 <= e && e <= SIZE)
            a[e] = 0;
    }

    public boolean isEqual(IntegerSet s) {
        for (int i = 0; i <= SIZE; i++)
            if ( a[i] != s.a[i] )
                return false;
        return true;
    }

    public void print(Graphics g) {
        int j = 0, yPos = 15;
        boolean empty = true;

        for (int i = 0; i <= SIZE; i++)
            if ( a[i] == 1 ) {
                empty = false;
                g.drawString(" " + i, 20*j, yPos);
                if ( ++j % 10 == 0 ) {
                    j = 0;
                    yPos += 15;
                }
            }
        if ( empty )
            g.drawString("---", j, yPos);
    }
}

5. Using the following interface for a class HugeInteger, give a HugeInteger method, factor, that returns a HugeInteger that is its smallest factor greater than 1. For example, if factor were applied to a HugeInteger representing 12, it would return a HugeInteger representing 2. The method factor can assume that its HugeInteger is not in the error state. It does not have to be efficient.

// This class deals only with integers >= 0

public class HugeInteger {
    private int digits[];       // digits of huge integer
    final static int SIZE = 10; // number of digits of huge integer
    boolean error;              // if overflow or underflow occurred, then true
                                // else false

// Construct a Huge 0.
public HugeInteger() {}

// Constructor that takes an array of SIZE digits
public HugeInteger(int d[]) {}

// Construct a HugeInteger of value I
public HugeInteger(HugeInteger I) {}

// Return a String representation of a HugeInteger
public String outputHugeInteger() {}

// Add I to this, put result in this
public HugeInteger addHugeIntegers(HugeInteger I) {}

// Subtract I from this, put result in this
public HugeInteger subtractHugeIntegers(HugeInteger I) {}

// Multiply this by I, put result in this
public HugeInteger multiplyHugeIntegers(HugeInteger I) {}

// Divide this by I, put result in this
public HugeInteger divideHugeIntegers(HugeInteger I) {}

// return the remainder of this when divided by I (this is unchanged)
public HugeInteger modulusHugeIntegers(HugeInteger I) {}

// true when this == I
public boolean isEqualTo(HugeInteger I) {}

// true when this < I
public boolean isLessThan(HugeInteger I) {}
}

Solution:

public HugeInteger factor() {

int one[] = {0,0,0,0,0,0,0,0,0,1},

two[] = {0,0,0,0,0,0,0,0,0,2};

HugeInteger Zero = new HugeInteger(),

One = new HugeInteger(one),

T = new HugeInteger(two);

    for (; T.isLessThan(this); T.addHugeIntegers(One)) {
        if (this.modulusHugeIntegers(T).isEqualTo(Zero))
            return T;
    }
    return this;
}

6. Using a method factor that operates according to the specifications of the previous problem, write a HugeInteger method enumerateFactors that uses the method outputHugeInteger to print out all of its prime factors with repetition.   For example, if enumerateFactor were applied to a HugeInteger representing 12, then enumerateFactor would invoke outputHugeInteger with:
    2
    2
    3

It looks like this:

public void enumerateFactors(Graphics g) { ... }

and uses the drawString method to print the factors onto the Graphics object, g.

Solution:

public void enumerateFactors(Graphics g) {

int j = 0,

one[] = {0,0,0,0,0,0,0,0,0,1};

HugeInteger One = new HugeInteger(one),

T = new HugeInteger(this);

for (; !T.isEqualTo(One); T.divideHugeIntegers(T.factor()) )
g.drawString(T.factor().outputHugeInteger(), 20, j += 20);
}

7. Describe the difference between composition and inheritance. Give examples of each.

Solution:

A class is defined by composition when its data members are objects of other classes, implementing "has a" relationship[s]; A class is defined by inheritance when it is an extension of another class, typically implementing an "is a" relationship (e.g., a rhombus is a quadralateral).

For example, if we have the following classes:

public class Birthdate { ... }

public class TelephoneNumber { ... }

public class Employee {
    Birthdate bDate;            // employee's birthdate
    TelephoneNumber tNumber;    // employee's telephone number
    ...
}

public class Janitor extends Employee {
Room access[]; // has access to these rooms
...
}

The class Employee has a Birthdate, a TelephoneNumber, and other attributes; a Janitor is an Employee, with special attributes or behaviors of his own.