Computer Science 15-100 (APEA Section E), Summer 2008
Homework 5
Due:  Thu 17-Jul-2008 at 6:00pm (online submission and physical copy)
(no late submissions accepted).



  1. Book Exercises
    Do the following Exercises from Chapter 5 (pp 280-282):
    Exercises 5.1 - 5.5 and 5.7 - 5.13
     
  2. gcd (Greatest Common Divisor)
    Write a method with this signature:
      public static int gcd(int x, int y) {
      }

    This method takes two (possibly negative!) integers x and y, and if both are positive, returns their greatest common divisor -- that is, the largest integer that evenly divides into both x and y.  If either x or y is non-positive, the method returns -1.  Here is the start of a test method:
      public static void testGcd() {
          assert(gcd(18,12) == 6);
          assert(gcd(18,-8) == -1);
      }


    Optional aside:  For partial credit, you can solve this the "naive" way, with a loop checking the numbers in the range [1,min(x,y)], and returning the largest factor you find.  But there is a better way!  The great Greek mathematician Euclid gave us a much faster way to find the gcd, as gcd(x,y) = gcd(y,x%y).  So gcd(18,12) == gcd(12, 18%12) == gcd(12,6).  Now we repeat this, gcd(12,6) == gcd(6,0).  When you get a 0, you're done, so the answer is 6.  It works!  And it requires far less arithmetic than the "naive" way.  Cool!  For full credit, write this method using Euclid's algorithm (but if you do, keep it iterative and not recursive -- that is, use a loop!).
     
  3. lcm (Least Common Multiple)
    Write a method with this signature:
      public static int lcm(int x, int y) {
      }

    This method takes two (possibly negative!) integers x and y, and if both are positive, returns their least common multiple -- that is, the smallest integer that both x and y divide evenly into.  If either x or y is non-positive, the method returns -1.  Note:  you must compute the lcm this way:  the product of the lcm(x,y) and the gcd(x,y) always equals the product of x*y.  So, this method finds the lcm by calling the gcd method you just wrote.  Here is the start of a test method:
      public static void testLcm() {
          assert(lcm(18,12) == 36);  // note that 18*12 == 6*36, so x*y == gcd(x,y)*lcm(x,y)
          assert(lcm(18,-8) == -1);
      }


    Optional aside:  do you see why the product of the lcm(x,y) and gcd(x,y) equals x*y?  Express x, y, gcd(x,y), and lcm(x,y) in terms of their prime factorizations.  For each prime p, the gcd(x,y) contains the smaller power in x's and y's factorizations, and the lcm(x,y) contains the larger power.  Think about it...
     
  4. goldbachPrime
    Goldbach's Conjecture states that every even number greater than 2 is the sum of two prime numbers.  For example:
        4 = 2 + 2
        6 = 3 + 3
        8 = 3 + 5
      10 = 3 + 7
    Note that 10 also equals 5+5, so we see there may be more than one such sum for any given even number.  While mathematicians have used computers to assert this conjecture for evens into the trillions and beyond, so it sure seems true, nobody has been able to prove it is always true.  It remains one of the great outstanding problems in mathematics.

    Write a method with this signature:
         public static int goldbachPrime(int n)
    This method takes an int n, and if it is an even integer greater than 2, the method returns the smallest integer p such that p is prime and (n - p) is prime.  Since p + (n - p) equals n, this method really confirms Goldbach's Conjecture for its argument n.  Note that you will need a loop to find the first prime, p, but then you do not need a loop for the second prime -- for any given prime p, just check if (n - p) is prime, too.  If the parameter n is not an even integer greater than 2, just return -1.  Here is the start of a test method:
      public static void testGoldbachPrime() {
          assert(goldbachPrime(3) == -1);
          assert(goldbachPrime(4) ==  2);
          assert(goldbachPrime(6) ==  3);
          assert(goldbachPrime(8) ==  3);
          assert(goldbachPrime(10)==  3);
      }
     
  5. nthTwinPrimes
    Two numbers are twin primes if both numbers are prime and their difference is 2.  So, for example, 3 and 5 are twin primes, as are 5 and 7, and 11 and 13.  Here is a table of the first several twin primes:
         n     nth twin primes
         0         (3, 5)
         1         (5, 7)
         2         (11, 13)
         3         (17, 19)
         4         (29, 31)

    Write a method with this signature:
         public static int nthTwinPrime(int n)
    This method takes an int n and if n is non-negative, returns the first (smaller) of the nth pair of twin primes.  If n is negative, the method returns -1. Here is the start of a test method:
      public static void testNthTwinPrime() {
          assert(nthTwinPrime(-1) == -1);
          assert(nthTwinPrime( 0) ==  3);
          assert(nthTwinPrime( 1) ==  5);
          assert(nthTwinPrime( 2) == 11);
          assert(nthTwinPrime( 3) == 17);
          assert(nthTwinPrime( 4) == 29);
      }
     
  6. Counting Primes
    In this exercise, we will observe an amazing property of the prime numbers!
     
    1. The Prime Counting Function:  pi(n)
      Write a method with this signature:
        public static int pi(int n) {
        }

      This method (which has nothing much to do with the value "pi", but coincidentally shares its name) takes an integer n and returns the number of prime numbers less than or equal to n.  Here is the start of a test method:
        public static void testPi() {
            assert(pi(1) == 0);
            assert(pi(2) == 1);
            assert(pi(3) == 2);
            assert(pi(4) == 2);
            assert(pi(5) == 3);
            assert(pi(100) == 25);  // there are 25 primes in the range [2,100]
        }
       
    2. The Harmonic Number:  h(n)
      Write a method with this signature:
        public static double h(int n) {
        }

      This method returns the sum of the first n terms in the harmonic series:  1/1 + 1/2 + 1/3 + 1/4 + ...  If n is non-positive, the method returns 0.  Here is the start of a test method:
        public static void testH() {
            assert(almostEquals(h(0),0.0);
            assert(almostEquals(h(1),1/1.0                );  // h(1) = 1/1
            assert(almostEquals(h(2),1/1.0 + 1/2.0        );  // h(2) = 1/1 + 1/2
            assert(almostEquals(h(3),1/1.0 + 1/2.0 + 1/3.0);  // h(3) = 1/1 + 1/2 + 1/3
        }
      Note:  here we use "almostEquals" rather than "==" because this method returns a double.
       
    3. Using the Harmonic Number to estimate the Prime Counting Function (Wow!)
      Write a method with this signature:
        public static int estimatedPi(int n) {
        }

      This method uses the Harmonic Number function to estimate the Prime Counting Function.  Think about it.  One counts the number of primes.  The other adds the reciprocals of the integers.  They seem totally unrelated, but they are in fact very deeply related!  In any case, this method takes an integer n and if it is greater than 2,  returns the value (n / (h(n) - 1.5) ), rounded to the nearest integer (and then cast to an int).  If n is 2 or less, the method returns 0.  Here is the start of a test method:
        public static void testEstimatedPi() {
            assert(estimatedPi(100) == 27);
        }
       
    4. Empirical check that this really works:  estimatedPiError
      Write a method with this signature:
        public static int estimatedPiError(int n) {
        }

      This method takes an integer n and returns the absolute value of the difference between the value of our estimation computed by estimatedPi(n) and the actual number of primes less than or equal to n as computed by pi(n).  If n is 2 or less, then method returns 0.  Here is the start of a test method:
        public static void testEstimatedPiError() {
            assert(estimatedPiError(100) == 2); // pi(100) = 25, estimatedPi(100) = 27
            assert(estimatedPiError(200) == 0); // pi(200) = 46, estimatedPi(200) = 46
            assert(estimatedPiError(300) == 1); // pi(300) = 62, estimatedPi(300) = 63
            assert(estimatedPiError(400) == 1); // pi(400) = 78, estimatedPi(400) = 79
            assert(estimatedPiError(500) == 1); // pi(500) = 95, estimatedPi(500) = 94
        }

      Aside:  as you can see, the estimatedPi function is an amazingly accurate estimation of the pi function.  For example, the estimatedPi function predicts that there should be 94 prime numbers up to 500, and in fact there are 95 prime numbers in that range.  And so we must conclude that there is some kind of very deep relationship between the sum of the reciprocals of the integers (1/1 + 1/2 + ...) and the number of prime numbers.  This relationship has been explored in great detail by many mathematicians over the past few hundred years, with some of the most important results in modern mathematics relating to it.
       
  7. Identifying Patterns (Mystery Methods)
    In each of the following exercises, you are given a method that computes a value that can be described in a few words of plain English.  In response, you are two write two methods -- one that provides the plain English description of the computation, and a second that verifies that this in fact is true.

    You should assume all integer parameters are in the range [1,999] and all string parameters are non-null with lengths in the range [1,999].  Do not worry about overflow or other odd cases.

    Note:  there is a right way and a wrong way to solve these problems.  The wrong way is simply to run them and print out the results and look for a pattern.  This is allowed, but it's not serving you well.  The right way is to look at the code, reason your way through it, and derive the pattern without running the code.  Once you have found the pattern, only then should you write your own test method that verifies that you are correct.  Finally, if after a long time of hard thinking you cannot find the pattern, only then should you resort to printing out the values as a hint.

    Also:  please be very strict about the collaboration policy on these problems.  Even an offhand comment may deprive a fellow classmate of the important opportunity to reason through these problems!  As always, if they (or you) need help, the instructor and CA's stand at the ready!

    Math hint (you'll need this for one of the exercises):
       1 + 2 + ... + n = n*(n+1)/2

    The first problem is completed for you.
     
    1. The mystery method:
        public static int mystery1(int n) {
          int result = 0;
            for (int i=0; i<n; i++)
              for (int j=0; j<n; j++)
                result++;
          return result;
        }

      With some reflection, you should see that this method computes the square of its argument.  Hence, its description is:

        public static String describeMystery1() {
          return "computes n squared";
        }

      Note that you could return any similar (in meaning and in brevity) English sentence.  For example, "computes the square of its argument" is ok.  Naturally, the robot grader will not be grading these descriptions.

      Now we need to provide a test method that verifies that this mystery method indeed works as we claim.  Note that you only have to assert this claim over the range [1,999].  Also, if it's impossible to check all values in the legal range (as may be the case for strings), then you should provide some reasonable tests to assert your claim (think about boundary cases, for example).

        public static void testMystery1() {
          for (int n=1; n<1000; n++)
            assert(mystery1(n) == n*n);
        }
       
    2. The mystery method:
        public static int mystery2(int n) {
          int result = 0;
          for (int i=1; i<=n; i++) {
            int sum = 0;
            for (int j=1; j<=n; j++)
              sum += j;
            result += 2*sum - n;
          }
          return result;
        }

      Now you write describeMystery2() and testMystery2().  Note:  that's all you submit for this problem -- these two Java methods (though of course you should include the mystery method itself so your code can compile and run).
       
    3. The mystery method:
        public static boolean mystery3(int n) {
          int s = (int)Math.round(Math.sqrt(n));
          if (s*s != n) return false;
          int i = s/n;
          while (i*i < s)
            i++;
          return (i*i == s);
        }

      Now you write describeMystery3() and testMystery3().
       
    4. The mystery method:
        public static int mystery4(String s) {
          int result = 0;
          while (s.length() > 0) {
            String t = "";
            for (int i=s.length()-1; i>=0; i--) {
              char c = s.charAt(i);
              if ((c >= '0') && (c < '9'))
                t += ((char)(c+1));
              else if ((c > '0') && (c <= '9'))
                result++;
            }
            s = t;
          }
          return result;
        }

      Now you write describeMystery4() and testMystery4().
       
    5. The mystery method:
        public static String mystery5(int n) {
          char b = (char)('a'+3);
          for (int i=n; i/2*2==i; i--) b++;
          String c = "", d = "mccain";
          switch (b/'e') {
            case 3: c = "obama";
            case 2: d = "huckabee";
            case 0:
                    break;
            case 1: char g = 'z';
                    for (int i='a'; i<b; i++) g--;
                    c += g;
            default:
                    d = "clinton";
          }
          return ((n % 2 == 1) ? "o" : "") + b + c + b + d.substring(6);
        }

      Now you write describeMystery5() and testMystery5().
       
    6. Write your own mystery methods
      Now it's your turn.  Write two of your own mystery methods.  Call them myMystery1 and myMystery2.  Include "describeMyMystery" and "testMyMystery" methods for each of them.  Your mystery methods should compute something easily describable in a few English words.  And they should make use of some of the Java constructs that we have used so far in this class (that's the whole point -- to study how these various constructs work).  You will be graded somewhat loosely on this problem, but you will be graded, and you are expected to write high-quality questions (clever enough to be useful, but not "so clever" as to be useless!).

      Note:  you may not just make some trivial adaptations of the previous mystery questions!  Your questions must be quite distinct from these in interesting ways!

      Note:  To help everyone study for the upcoming test, we will share everyone's mystery methods with the entire class (after this assignment's due date).  In this way, you will get a good variety of mystery methods to practice on.

Carpe diem!