[Instructions] [Search] [Current] [News] [Syllabus] [Glance] [Links] [Handouts] [Project] [Outlines] [Labs] [Assignments] [Quizzes] [Exams] [Examples] [EIJ] [JPDS] [Tutorial] [API]

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

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.

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 */publicclassFraction {// +--------+--------------------------------------------------// | Fields |// +--------+/** The numerator of the fraction. Can be positive or negative. */protectedintnum;/** The denominator of the fraction. Should be positive. */protectedintdenom;// +--------------+--------------------------------------------// | Constructors |// +--------------+/** * Build a new fraction with value A/B. */publicFraction(intA,intB) {this.num = A;this.denom = B;this.cleanup(); } // Fraction(int,int)// +------------+----------------------------------------------// | Extractors |// +------------+/** Get the numerator of the fraction. */publicintgetNumerator() {returnthis.num; } // getNumerator()/** Get the denominator of the fraction. */publicintgetDenominator() {returnthis.denom; } // getDenominator()/** Return the fraction as a string. */publicString toString() {returnthis.num + "/" +this.denom; } // toString()// +-------------------------+---------------------------------// | Mathematical Operations |// +-------------------------+/** * Add this fraction to another fraction, creating a third * fraction for the result. */publicFraction add(Fraction other) {// A/B + C/D = (AD + BC)/BDintnum =this.num*other.denom + other.num*this.denom;intdenom = other.denom*this.denom;returnnewFraction(num,denom); } // add(Fraction)/** * Multiply this fraction by another fraction, creating * a new fraction. */publicFraction multiply(Fraction other) {// A/B * C/D = (A*C)/(B*D)returnnewFraction(this.num*other.num,this.denom*other.denom); } // multiply(Fraction)/** * Divide this fraction by another fraction, creating * a new fraction. */publicFraction divide(Fraction other) {// A/B / C/D = A/B * 1/(C/D) = A/B * D/C = (AD)/(BC)returnnewFraction(this.num*other.denom,this.denom*other.num); } // divide(Fraction);/** * Negate this fraction, creating a new fraction. */publicFraction negate() {// -(A/B) = (-A)/BreturnnewFraction(-this.num,this.denom); } // negate()/** * Subtract another fraction from this fraction, creating * a new fraction for the result. */publicFraction subtract(Fraction other) {returnadd(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. */protectedvoidcleanup() {// 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.)

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. */publicstaticvoidmain(String[] args) { SimpleOutput out =newSimpleOutput(); Fraction frac =newFraction(1,3); frac.add(newFraction(2,7)); out.println(frac.toString()); } // main(String[])

For some reason, his output is always `1/3`

. **Explain
why Fillip's results are ``incorrect''.**

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. */publicfloattoFloat() {// STUB. What should go here?return0; } // toFloat()

**Help Fiona finish her function.**

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

publicFraction(intnum,intdenom) {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

publicvoidsimplify() {intcommon;// 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);elsecommon = 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.

protectedstaticintgcd(intx,inty) {// STUBreturn1; } // gcd(int,int)

**Fill in the body of the gcd method.**

*Note:* In Java, you can compute remainders with `%`

.

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

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. */publicFraction(intval) {// STUB} // Fraction(int)

**Fill in the body of this constructor.**

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:

- Pieces have
*three*colors: Black, White, and Gray. When you flip a piece, it goes to the next color (Black to White, White to Gray, Gray to Black). - Pieces disappear if you flip them more than five times.
- About one third the time you flip a piece, it moves to one of the empty neighboring spaces, if such a space exists.

They call their game *Oddthello*.

**Sketch an implementation of an OddthelloPiece
class.**

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

/** * Return true about one-thrid of the time. */protectedbooleanwhatever() {returnMath.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.

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.

publicclassPoint{publicdoubledistanceFromOrigin() {returnMath.sqrt(this.x *this.x +this.y *this.y); }publicPoint(doublex,doubley) {this.x = x;this.y = y; }protecteddoublex;publicvoidset(doublenewX,doublenewY) {this.x = newX;this.y = newY; }publicString toString() {return"(" +this.x + "," +this.y + ")"; }publicdoublegetX() {returnthis.x; }publicdoublegetY () {returnthis.y; }publicPoint() {this.x = 0;this.y = 0; }protecteddoubley;publicintgetQuadrant() {if( (this.x > 0) && (this.y > 0) ) {return1; }elseif((this.x < 0 ) && (this.y > 0 )) {return2; }elseif((this.x < 0)&&(this.y< 0) ) {return3; }elseif((this.x > 0) && (this.y < 0)) {return4; }else{return0; }}}

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

importPoint;importSimpleOutput;/** * 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 */publicclassPointTester {/** * 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. */publicstaticvoidreport(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)publicstaticvoidmain(String[] args) {// Prepare for output.SimpleOutput output =newSimpleOutput();// Do the tests. The tests should be self documenting.output.println("Testing zero-parameter constructor"); report(output,newPoint()); output.println("Testing point (1,3)"); Point pt =newPoint(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

Thursday, 10 February 2000

- First version.
- The problem on fractions was modified from a previous exam.

Friday, 11 February 2000

- Clarified.
- Reformatted slightly.
- Distributed.
- Add
`toString`

method to the Fraction class.

[Instructions] [Search] [Current] [News] [Syllabus] [Glance] [Links] [Handouts] [Project] [Outlines] [Labs] [Assignments] [Quizzes] [Exams] [Examples] [EIJ] [JPDS] [Tutorial] [API]

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