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.

1. Mystery Methods
2. Sieve of Eratosthenes
3. Point
4. Line
5. Least Squares (Linear Regression)

1. Mystery Methods
   In the written portion of your submission, answer the following questions in general, and in just a few words of plain English.
    
   1. 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;
        }

   2. 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;
        }

   3. 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;
        }

2. 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.
    
3. 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...).
    
4. 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.
    
5. 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!