Computer Science 15-110 (Lecture 4), Spring 2010
Homework 9
Due: Thu 1-Apr-2009 at 10pm (email copy to ytay) (no late submissions
accepted).
Hw9 Submission Coordinator: ytay
This is non-collaborative,
so follow the same instructions as
hw1, only
replace "hw1" with "hw9" throughout. There are no
restrictions on what Java constructs you may use.
Place all your code in a single file, Hw9.java.
- Mystery Methods
-
Sieve of Eratosthenes
-
Point
-
Line
-
Least Squares (Linear Regression)
-
Mystery Methods
In the written portion of your submission, answer the following
questions in general, and
in just a few words of plain
English.
-
In general, what does the following method do?
public static boolean f(int[] a, int[] b) {
if ((a == null) || (b == null) || (a.length != b.length))
return false;
int n = a.length;
for (int i=0; i<n; i++) {
boolean ok = true;
for (int j=0; j<n; j++)
ok = ok && (a[j] == b[(i+j)%n]);
if (ok)
return true;
}
return false;
}
-
In general, what does the following method do?
public static char[][] h(String s, int n) {
char[][] result = new char[n][n];
for (int i=0; i<n*n; i++)
result[i/n][i%n] = s.charAt(i%s.length());
return result;
}
-
In general, what does the following method do?
public static double m(double d) {
double q = 0;
double r = 0.0001;
double t = Math.abs(d);
double s = t/2;
while (Math.abs(d-s*s)>r) {
if (s*s>d) t=s;
else q=s;
s = (q+t)/2;
}
return s;
}
-
Sieve of Eratosthenes
Write this method in your Hw9 class:
public static int[] primesUpToN(int n)
This method takes an int n and returns an array containing all the prime
numbers (in increasing order) up to and including n (if is prime, of
course). If no such primes exist, the method returns a non-null empty
array. So, for example, primesUpToN(13) would return the array {2, 3,
5, 7, 11, 13}.
To
receive credit, your solution must use
the Sieve of Eratosthenes (see its
Wikipedia page),
an ancient technique for finding prime numbers. Specifically, in Java
terms, you should create an array of
booleans,
isPrime, where all the values are initially true (except isPrime[0] and
isPrime[1], which you will set to false). Then, follow the steps in
the
algorithm on the Wikipedia page, where you "strike" a number k off the
list (in step 3) by setting isPrime[k] equal to false. When you are
done filling the isPrime array up to n, create an array of the appropriate
size (the number of true values in the isPrime array), then traverse the
isPrime array one time, copying each prime number p (where isPrime[p] is
true) into the resulting array of primes, and return that array.
-
Point
Outside your Hw9 class, but inside your Hw9.java file, create a class named
Point, which represents an ordered pair (x,y) of doubles. Provide a
constructor that takes two doubles, a nice toString method, and the getX and
getY accessors (which both return doubles). No need for setX or setY
mutators.
Finally, write a static method Point.testPointClass that includes a
reasonable test suite for the Point class (simple as it is...).
-
Line
Outside your Hw9 class, but inside your Hw9.java file, create a class named
Line which represents a line (or a linear function in two variables).
Provide two constructors: one which takes two doubles -- the slope and
the y-intercept -- and another which takes two Point instances (from the
Point class you just defined above), where the line goes through the two
Points. Note that this second form allows you to enter vertical lines
(which have no defined slope). Also provide a nice toString method,
and the getSlope and getYIntercept methods (which both return doubles).
If the line has a vertical slope, return Double.POSITIVE_INFINITY as the
slope. Also, provide an eval method, which takes a double value -- the
x value -- and returns the y value of the line at the given x value.
If the line is not defined at the given point, return Double.NaN ("not a
number"). Finally, write a
static method Line.testLineClass that includes a reasonable test suite for
the Line class.
-
Least Squares (Linear Regression)
Write this method in your Line class:
public static Line lineOfBestFit(Point[] points)
This static method takes an arbitrary number of points (supplied in a single
array of an Point instances) and uses linear regression with vertical least
squares to find the best-fitting line through the given points. Here
is a detailed example/tutorial (for a high school math class I taught some
years ago) on how to do this:
http://www.kosbie.net/ml/04-05/honors-precalc/linearRegression.htm
There are other, similar ways to find least squares, but stick to this exact
approach (so our autograder will recognize your solution as correct!).
Finally, write a static method Line.testLineOfBestFit that includes a
reasonable test suite for the lineOfBestFit method.
Carpe diem!