Computer Science 15-100 (Sections T & U), Spring 2008
Homework 7b
Due:  Fri 29-Feb-2008 at 10:00am (online submission) and at recitation (physical copy)
(no late submissions accepted).

• Be sure to include your name, your Andrew ID, and your section (T or U) clearly on the top of each file in your assignment.
• Name your program and your methods exactly as indicated.
  • You will have exactly one program:
    1. Hw7b.java -- this will contain all the questions
• Use well-named variables, proper indenting, reasonable commenting, etc.  Do not use magic numbers!
• Provide complete (but concise) test cases!
• Provide the UI exactly as indicated.  File-based UI should not include prompts.
• Submit printed solutions in recitation.  Your printed solutions must be identical copies of your emailed solutions!
• Show your work (for the non-programming problems).  Correct answers without supporting calculations will not receive full credit.

1. 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() {
            verify(pi(1) == 0);
            verify(pi(2) == 1);
            verify(pi(3) == 2);
            verify(pi(4) == 2);
            verify(pi(5) == 3);
            verify(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() {
            verify(almostEquals(h(0),0.0);
            verify(almostEquals(h(1),1/1.0                );  // h(1) = 1/1
            verify(almostEquals(h(2),1/1.0 + 1/2.0        );  // h(2) = 1/1 + 1/2
            verify(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() {
            verify(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() {
            verify(estimatedPiError(100) == 2); // pi(100) = 25, estimatedPi(100) = 27
            verify(estimatedPiError(200) == 0); // pi(200) = 46, estimatedPi(200) = 46
            verify(estimatedPiError(300) == 1); // pi(300) = 62, estimatedPi(300) = 63
            verify(estimatedPiError(400) == 1); // pi(400) = 78, estimatedPi(400) = 79
            verify(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.
       
2. 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 verify 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 verify your claim (think about boundary cases, for example).
      
        public static void testMystery1() {
          for (int n=1; n<1000; n++)
            verify(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.
       
3. Write your own code snippets
   This section is based on the questions from quiz 5 question #1.  Only here, you will write a few of these questions.  For this section, you should write 3 methods that are all void and all take no parameters.  Call these methods myMystery3, myMystery4, and myMystery5.  These methods will make use of various Java constructs we have used so far in this class and after some reasonably-easy-to-trace computation, will print out something.  Unlike the previous mystery problems, the goal here is not to describe the computation in English.  Instead, the goal is to hand trace the code and print out the exact output.  So these methods need not compute anything interesting or easily explainable in English.  They just need to use interesting Java constructs in interesting ways and print out a result of some kind.  Ideally, the output is easy to write and is somewhat immune to guessing.
   
   As with the previous problem, you will be graded somewhat loosely on this problem, but you will be graded, and you are expected to write high-quality questions (again, clever enough to be useful, but not "so clever" as to be useless!
   
   Note:  again, you may not just make some trivial adaptations of the questions from quiz 5 (included below)!  Your questions must be quite distinct from these in interesting ways!
   
   Note:  Again, 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.
   
   Note:  unlike your previous mystery methods, for these 3 problems, you do not need a describe method nor a test method, but you must include the actual output of the method in a header comment just before the method.
   
   Here are the questions from quiz 5, modified superficially so they each occur in their own method, supplied here both for your studying purposes and to help you think about the kinds of questions you might write.
   
   Have fun!

   class MyCode {  
     public static void myMysteryA() {
       int x=1;
       do
         x++;
       while (x++ < 3);
       System.out.format("%d\n",x);
     }
     
     public static void myMysteryB() {
       int x=1, y=2;
       for (x=3; x==3; x++) {
         x -= 3/y;
         y++;
       }
       System.out.format("%d,%d\n",x,y);
     }
     
     public static void myMysteryC() {
       int x=1, y=3;
       if ((++x < y) || (++y < x)) x += 10;
       System.out.format("%d,%d\n",x,y);
     }
     
     public static void myMysteryD() {
       int x=1, y=8;
       String z = "";
       while (x < y) {
         if (x % 2 == 1)
           if (y % 2 == 1)
             x++;
           else
             y--;
         else
           y /= 2;
         z += y;
       }
       System.out.format("%d,%d,%s\n",x,y,z);
     }
     
     public static void myMysteryE() {
       int x=1, y=6;
       while (x <= y) {
         x += ((y % x > 0) ? 2 : 1);
         y--;
       }
       System.out.format("%d,%d\n",x,y);
     }
     
     public static void myMysteryF() {
       int x=0,y=0;
       for (int i=0; i<5; i++)
         switch (i/2) {
         case 1:  x++;
                  break;
         case 2:  y++;
                  // note: no break!
         default: x++;
       }
       System.out.format("%d,%d\n",x,y);
     }
     
     public static void myMysteryG() {
       int x=1, y=3, z=5;
       while (x < y*z) {
         x += 1;
         y -= 2;
         z += 3;
       }
       System.out.format("%d,%d,%d\n",x,y,z);
     }
     
     public static void myMysteryH() {
       int x=0,y=0;
       for (int i=10; i>0; i--) {
         x++;
         if (i % 3 == 1)
           continue;
         y++;
         if (i % 4 == 2)
           break;
         x++;
       }
       System.out.format("%d,%d\n",x,y);
     }
     
     public static void myMysteryI() {
       for (int i=0; i<100; i++) {
         int x = i % 10, y = i / 10;
         if (x + y > 16)
           System.out.format("%d,%d\n",x,y);
       }
     }
     
     public static void myMysteryJ() {
       int x=0;
       for (int i=0; i<10; i++) {
         for (int j=0; j<5; j++)
           x++;
         x++;
       }
       System.out.format("%d\n",x);
     }
     
     public static void main(String[] args) {
       System.out.println("A:"); myMysteryA();
       System.out.println("B:"); myMysteryB();
       System.out.println("C:"); myMysteryC();
       System.out.println("D:"); myMysteryD();
       System.out.println("E:"); myMysteryE();
       System.out.println("F:"); myMysteryF();
       System.out.println("G:"); myMysteryG();
       System.out.println("H:"); myMysteryH();
       System.out.println("I:"); myMysteryI();
       System.out.println("J:"); myMysteryJ();    
     }
   }
   

Carpe diem!