Fundamentals of Computer Science II (CSC-152 2000S)


Exam 1: Java Fundamentals

Distributed: Friday, February 11, 2000
Due: 11 a.m., Friday, February 18, 2000
No extensions!

This page may be found online at http://www.math.grin.edu/~rebelsky/Courses/CS152/2000S/Exams/exam.01.html.

Code files:

You may want to use the online version of the exam to gain access to these files.

Policies

There are three problems on the exam. Each is worth 30 points, even though they may not all be of the same complexity or length. You get ten points ``free'' (making 100) for turning the exam in on time.

This examination is open book, open notes, open mind, open computer, open Web. Feel free to use any and all resources available to you except for other people and for exam and homework solutions. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. Do not use exam or homework solutions you find on the Web.

This is a take-home examination. It is likely to take you about ten hours. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted. I may make a solution key available after the exam.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is definitely the hardest exam I have ever taken.'' You may also summarize these policies.

Answer all of your questions electronically. That is, you must write all of your answers on the computer and print them out. You should also email me a copy of your exam (a plain text file, please). Put your answers in the same order that the problems appear in.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by highlighting your answer and including a clear set of work that you used to derive the answer. In any case, if you include a note about the time spent on each problem or subproblem, I will give you three points of extra credit.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

I will also reserve time at the start of classes next week to discuss any general questions you have on the exam.


Problems

A. Fractions

Fillip and Fiona Fictitious are fooling with the Fraction class that we started to define in class. Here is the code for that class.


/**
 * Fractions with integer numerators and denominators.  Once
 * the value of a fraction has been set, that value should
 * not be changed.
 *
 * @author Samuel A. Rebelsky
 * @author Fillip Fictitious
 * @author Fiona Fictitious
 * @version 1.0 of February 2000
 */
public class Fraction
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The numerator of the fraction.  Can be positive or negative. */
  protected int num;

  /** The denominator of the fraction.  Should be positive. */
  protected int denom;

  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Build a new fraction with value A/B.
   */
  public Fraction(int A, int B)
  {
    this.num = A;
    this.denom = B;
    this.cleanup();
  } // Fraction(int,int)

  // +------------+----------------------------------------------
  // | Extractors |
  // +------------+

  /** Get the numerator of the fraction. */
  public int getNumerator() {
    return this.num;
  } // getNumerator()

  /** Get the denominator of the fraction. */
  public int getDenominator() {
    return this.denom;
  } // getDenominator()

  /** Return the fraction as a string. */
  public String toString() {
    return this.num + "/" + this.denom;
  } // toString()

  // +-------------------------+---------------------------------
  // | Mathematical Operations |
  // +-------------------------+

  /** 
   * Add this fraction to another fraction, creating a third
   * fraction for the result.
   */
  public Fraction add(Fraction other) {
    // A/B + C/D = (AD + BC)/BD
    int num = this.num*other.denom + other.num*this.denom;
    int denom = other.denom*this.denom;
    return new Fraction(num,denom);
  } // add(Fraction)

  /**
   * Multiply this fraction by another fraction, creating
   * a new fraction.
   */
  public Fraction multiply(Fraction other) {
    // A/B * C/D = (A*C)/(B*D)
    return new Fraction(this.num*other.num,
                        this.denom*other.denom);
  } // multiply(Fraction)

  /**
   * Divide this fraction by another fraction, creating
   * a new fraction.
   */
  public Fraction divide(Fraction other) {
    // A/B / C/D = A/B * 1/(C/D) = A/B * D/C = (AD)/(BC)
    return new Fraction(this.num*other.denom,
                        this.denom*other.num);
  } // divide(Fraction);

  /**
   * Negate this fraction, creating a new fraction.
   */
  public Fraction negate()
  {
    // -(A/B) = (-A)/B
    return new Fraction(-this.num, this.denom);
  } // negate()

  /**
   * Subtract another fraction from this fraction, creating
   * a new fraction for the result.
   */
  public Fraction subtract(Fraction other)
  {
    return add(other.negate());
  } // subtract(Fraction)


  // +-----------+-----------------------------------------------
  // | Modifiers |
  // +-----------+

  // This class has no modifiers.

  // +---------+-------------------------------------------------
  // | Helpers |
  // +---------+

  /** 
   * "Clean up" the fraction to ensure that the numerator and
   * denominator meet the appropriate standards.
   */
  protected void cleanup()
  {
    // If the denominator is negative, multiply both parts
    // by -1 to make it positive without changing the value
    // of the fraction.
    if (this.denom < 0) {
      this.denom = -this.denom;
      this.num = -this.num;
    }
  } // cleanup()

} // class Fraction



They've had a number of problems, and would like your help. In order to help them, you must write working code for each of the subproblems that require code. (You must also answer the questions appropriately.)

A.1. Addition

Fillip has been testing the addition method, and getting what he thinks are incorrect results. Here's the main method he's been using.

  /** Compute 1/3 + 2/7. */
  public static void main(String[] args) {
    SimpleOutput out = new SimpleOutput();
    Fraction frac = new Fraction(1,3);
    frac.add(new Fraction(2,7));
    out.println(frac.toString());
  } // main(String[])

For some reason, his output is always 1/3. Explain why Fillip's results are ``incorrect''.

A.2. Converstion to Reals

Fiona remembers that we wrote a toReal method in class that converts a fraction to the corresponding real. Unfortunately, she can't find it in the class notes, and this is how far she's gotten.

  /**
   * Convert this fraction to a floating-point value.
   */
  public float toFloat()
  {
    // STUB.  What should go here?
    return 0;
  } // toFloat()

Help Fiona finish her function.

A.3. Simplification

Fillip and Fiona are somewhat frustrated that their fractions fail to appear in simplified form. For example, when they add 1/5 and 3/10, they get 25/50 rather than 1/2. Similarly, when they multiply 2/3 and 9/4, they get 18/12 rather than 3/2.

Hence, they've decided to add a simplify method to the class and update the constructor to use the method. Here's their new constructor

  public Fraction(int num, int denom)
  {
    this.numerator = num;
    this.denominator = denom;
    this.cleanup();
    this.simplify();
  } // Fraction(int, int)

They've asked some math majors, and they say that to simplify a fraction, you need to find the greatest common divisor of the numerator and denominator and that you can use Euclid's algorithm to help find it.

The math majors have told them that Euclid said something like:

The greatest common divisor of two positive numbers, X and Y, with X larger than Y, is either (1) Y, if Y evenly divides X, or (2) the greatest common divisor of Y and the remainder you get when you divide X by Y, if Y does not evenly divide X.

So, Fiona and Fillip started with

  public void simplify()
  {
    int common;	// The greatest common divisor
    // Compute the greatest common divisor.
    // If the numerator is negative, make it positive for the
    // purposes of GCD, since Euclid said "two positive numbers"
    if (this.num < 0)
      common = gcd(-this.num, this.denom);
    else
      common = gcd(this.num, this.denom);
    // Divide numerator and denominator by the gcd.
    this.num = this.num / common;
    this.denom = this.denom / common;
  } // simplify()

Unfortunately, that's about as far as they can get. They know how to set up the gcd method, but can't tell how to turn Euclid's claim into code. Since 1 divides everything, they've used it for their stub.

  protected static int gcd(int x, int y)
  {
    // STUB
    return 1;
  } // gcd(int,int)

Fill in the body of the gcd method.

Note: In Java, you can compute remainders with %.

A.4. Static methods

Explain to the best of your ability why gcd is both static and protected.

A.5. Another constructor

Your Fictitious classmates have decided that whole numbers are, in effect, fractions. They would like to write a constructor that has the following form:

/** Create the fraction whose value is val. */
public Fraction(int val) {
  // STUB
} // Fraction(int)

Fill in the body of this constructor.

B. An Oddthello Piece

Carla and Carl Caffeinated have decided that Othello is not interesting enough, and have added some interesting rule variations that are more natural to implement on the computer. Here are some that they've come up with:

They call their game Oddthello.

Sketch an implementation of an OddthelloPiece class.

Notes on Odthello Problem

1. The following method returns true about 1/3 of the time.

/**
 * Return true about one-thrid of the time.
 */
protected boolean whatever()
{
  return Math.random() < .333;
} // whatever()

2. You may assume that there is a OddthelloBoard class which includes an occupied(int row, int col) method.

3. You need not write working code for this problem. However, your code should in a state that convinces me that you could write working code given more time.

C. Correcting and Commenting Code

At the start of the semester, I handed out some standards for Java programming. Henry and Hermione Hacker don't think that they need to follow those standards. However, they've learned that I won't grade homework that doesn't meet my standards. Unfortunately, they don't know where to begin.

How bad is their code? Here's the first class that they turned in; an implementation of a Point class.


public class Point{
  public double distanceFromOrigin() {
    return Math.sqrt(this.x
      *this.x + this.y *
this.y);
}

    public Point(double x, double y) {
      this.x = x; this.y = y; 
    }

protected double x;

  public void set(double newX, double newY) {
    this.x = newX;
    this.y = newY;
  }

  public String toString()
  { return "(" + this.x + "," + this.y + ")"; } public double getX() {
    return this.x;
  }

  public double getY
  () {
    return this.y;
  }

    public Point() { this.x = 0; this.y = 0; } protected double y;

  public int getQuadrant()
  { if (
      (this.x > 0) && (this.y > 0)
         ) { return 1; } else
    if ((
      this.x < 0
    ) && (
      this.y > 0
       )) { return 2;
}else
    if((this.x < 0)&&(this.y<    0)
    ) { return 3;

}
    else
      if ((this.x > 0) && (this.y < 0)) { return 4; }
                   else {
return 0; }}}
    


Help them turn their Point.java into something that is more readable. You should certainly add comments, fix the badly formatted code, add whitespace where appropriate, and reorganize the code so that similar things are near each other. Your goal is to create a class that is likely to meet my high standards of indentation, organization, uniformity, and commenting.

Make sure to use the existing code (which does work); do not rewrite from scratch.

You may find it helpful to use the following test program.


import Point;
import SimpleOutput;

/**
 * Some simple tests of the Point class.   Distributed to help
 * students develop and test their classes.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of February 2000
 */
public class PointTester {
  /**
   * A helper function that can print out some information
   * about a point.  Note that this is static because it
   * does not need to use any fields or non-static methods
   * from this class.
   */
  public static void report(SimpleOutput pen, Point pt)
  {
    pen.println(pt.toString());
    pen.println("  x: " + pt.getX());
    pen.println("  y: " + pt.getY());
    pen.println("  distance: " + pt.distanceFromOrigin());
    pen.println("  quadrant: " + pt.getQuadrant());
    pen.println();
  } // report(SimpleOutput, Point)

  public static void main(String[] args)
  {
    // Prepare for output.
    SimpleOutput output = new SimpleOutput();
    // Do the tests.  The tests should be self documenting.
    output.println("Testing zero-parameter constructor");
    report(output, new Point());
    output.println("Testing point (1,3)");
    Point pt = new Point(1,3);
    report(output, pt);
    output.println("Setting value to (-3,4)");
    pt.set(-3,4);
    report(output, pt);
    output.println("Setting  value to (0,-10)");
    pt.set(0,10);
    report(output, pt);
  } // main(String[])
} // class PointTester




History

Thursday, 10 February 2000

Friday, 11 February 2000


Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

This page may be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/2000S/Exams/exam.01.html

Source text last modified Tue Feb 15 07:56:04 2000.

This page generated on Tue Feb 15 07:56:21 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu