Note #0:  we resumed on 2-Feb-05 after a 3-week hiatus (for 1st semester finals).  No homework was due.

Note #1: Most of this week's problems are fairly easy, but a couple may be a bit more challenging for some of you. Please get an early start on these so that you can bring your questions to class (or ask via email).  Please do not leave this until Tuesday night!

Note #2: Each problem this week requires that you write a method. To demonstrate that your method works, you should also write a corresponding program that repeatedly calls the method with suitable arguments and prints out the result.

#0.  Review MethodsExamples.java, which we wrote in class today.

#1. Write a method called "max3" that computes the maximum value of THREE integers.

#2. Write a method called "min3" that computes the minimum value of THREE integers.

#3. Write a method called "median3" that computes the MEDIAN value of THREE integers. Hint: for the case of three numbers, the median is the value that is NOT the maximum NOR the minimum, so add the three values and subtract out the min and max, using the methods you wrote for problems #1 and #2.

#4. Write a method called "xor" that takes two boolean values (either true or false) and returns a boolean value which is true if EITHER of the values is true BUT NOT BOTH of them. This is called the "xor" function, or "eXclusive OR" (where we are excluding the case where both values are true).

#5. Write a method "isFactor" which takes two integers (k and n) and returns true iff ("if and only if") k is a factor of n.

#6. Write a method "isPerfect" which takes an integer and returns true iff that integer is a perfect number (we learned about perfect numbers on an earlier assignment). Your method MUST call the "isFactor" method you wrote for problem #5.

#7. Write a method "isPrime" which takes an integer and returns true iff it is a prime number. Your method MUST call the "isFactor" method you wrote for problem #5.

#8. Write a method "nthPrime" which takes a positive integer "n" and returns the nth prime number, where 2 is the 1st prime number. So:
     nthPrime(1) returns 2
     nthPrime(2) returns 3
     nthPrime(3) returns 5
     nthPrime(4) returns 7
     ...
Your method MUST call the "isPrime" method you wrote for problem #7.

#9. Write a method "rollDie" which takes a positive integer "s", the number of sides a die, and returns a random number in [1,s], which represents the results of one roll of an s-sided die.

#10. Write a method "rollDice" which takes a positive integer "s" and a positive integer "n" and returns the sum of rolling an s-sided die "n" times. This method MUST call the "rollDie" method you wrote for problem #9.

#11. Write a method "rollOdds" which takes a positive integer "s", another positive integer "n", and a third positive integer "sum", and returns a double in the range [0.0,1.0] which represents the probability of obtaining the given sum when rolling an s-sided die "n" times. As you guessed, this method MUST call the "rollDice" method you wrote for problem #10 (that is, I want you to solve this with Monte Carlo methods and not by xact math). Actually, you'll have to call it many, many times (say, at least 1 million), and count how many times the sum was the desired sum, and use this value to compute your estimate of the resulting probability.  As an example, to get a 7 on two rolls of a 6-sided die you need 1+6, 2+5, 3+4, 4+3, 5+2, or 6+1, which is 6 out of 36 possible rolls, so the odds are 6/36 or 0.1666... Thus, rollOdds(6,2,7) should return 0.166666....
 

Note:  This assignment is due on 12-Jan-05, and we will meet that morning as usual.  However, there will be no homework assigned then, and we will not meet for the following 2 weeks.  This will allow everyone to focus on their final projects and final exams.

1. Write a program, CoinFlips.java, which repeatedly reads in a non-negative integer n (exiting only when a negative integer is entered) and simulates flipping a coin n times, printing out an "H" for each Heads and a "T" for each tails.  After the n flips, you should print out the total number of heads and tails and the percentage of heads and tails.  Confirm that as the sample size (number of coin flips) gets larger, our observed probability (say, of a coin toss turning up heads) approaches our expected probability (50% in this case).
    
2. Write a program, FindingE.java, which which repeatedly reads in a non-negative integer n (exiting only when a negative integer is entered) and then considers n random numbers in [0,1) (that is, it makes n calls to Math.random()).  For this problem, let us call a sequence of numbers a run if the numbers are increasing except for the last number of the run which is smaller than the second-to-last number.  Thus, each of the following are runs:
        0.3, 0.5, 0.9, 0.2  (run of length 4)
        0.2, 0.1  (run of length 2)
        0.7, 0.72, 0.8, 0.99, 0.0 (run of length 5)
   It should be clear that the minimum possible length of a run is 2 (right?).  Now, among your "n" random numbers, you should compute how many runs there are ("runs") and the average run length, which is almost exactly  "n / runs" (extra credit:  why is it not exactly this value?).  For example, say that n=10 and your 10 random numbers are:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   The first run is:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   The second run is:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   The third run is:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   There is no complete fourth run (it starts at 0.1, but the list ends before the run ends).  Thus, there are 3 runs, and the average run length is approximately 10/3 = 3.33333...
   
   Your program should print out "n", the total number of runs, and the ratio "n/runs".
   
   The fascinating thing is that, as "n" gets large (perhaps very large), the value "n/runs" will approach the mystical value of e (2.71828183...) -- confirm this is true for your program!  Amazing!
    
3. Here, you should write FindingEAgain.java, which is similar to the previous problem, only this time we define a run as a sequence of numbers whose sum exceeds 1 (so you keep adding numbers to the run until their sum exceeds 1).  Thus, using the same example from above, we see we get different runs.  The 10 numbers are:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   The first run is:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   The second run is:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   The third run is:
        0.2  0.7  0.3  0.5  0.1  0.3  0.4  0.9  0.6  0.1
   
   Again, there is no complete fourth run (it starts at 0.1, but the list ends before the run ends).  Thus, there are 3 runs, just as before (even though the runs themselves are different), and the average run length is approximately 10/3 = 3.33333...
   
   Your program should print out "n", the total number of runs, and the ratio "n/runs".
   
   The fascinating thing is that, even with this new definition of runs, as "n" gets large (perhaps very large), the value "n/runs" will approach the mystical value of e (2.71828183...) -- confirm this is true for your program!  Incredible!
   
   By the way:  these problems are inspired by:
        http://www.maa.org/pubs/Calc_articles/ma020.pdf
   This problem is #2 and the preceding problem is #6 on that page.
    
4. Write a program which uses Math.random() to roll a 6-sided die (that is, to choose a random integer in the range [1,6]).  You should repeatedly read in an integer n, exiting only when a negative integer is entered, and print out the results of n die rolls (your output will look like:  "13264534431...").  You should also keep 6 counters, one for each side, and keep a count of how many times each side is rolled.  At the end, you should print out your six counts, and you should observe that all six are very near each other (if not, then you have done something wrong!).
   
   Hint #1:  Since Math.random() returns a value in the range [0,1), what range will 2*Math.random() be in?  Answer:  [0,2).  How about 3*Math.random()?  Answer:  [0,3).  Continue with that line of logic...
   
   Hint #2:  Math.random() returns doubles, but we need integers here.  Remember that you can cast a double into an integer as follows:
        int x;
        double d;
        d  = 3.14;
        x = (int)(d);  // here, we cast the double d into an integer
   When a double is cast into an integer, its decimal part is truncated (deleted).  Thus, in this example, x will be assigned the value 3.  But you must be careful when you cast.  For example, consider the following:
        x = 2 * ((int)(Math.random());
   This will always evaluate to 0.  Why?  Because Math.random() is in [0,1), and this value is immediately cast into an integer, which always evaluates to 0 (think about it), and this 0 is then multiplied by 2.  In this case, what was probably desired is more like:
        x = (int)(2 * Math.random());
   Here, the result of Math.random() is first multiplied by 2, giving a number in [0,2), and this number is cast to an integer, producing an integer in [0,1] (why not in [0,2]?).

Note: most students did not sufficiently master the material from last week.  Thus, first, redo that material.  You should be able to write simple "for" loops, starting from EmptyProgram.java, in one or two minutes at most.  Practice until you achieve that level of mastery!

To help you practice, here are more problems requiring "for" loops.  Be sure to start each one with EmptyProgram.java.  Please bring all your programs on a floppy disk to our next class.

1. Write a program, SumOfCubes.java, which repeatedly reads in a non-negative integer n (exiting only when a negative integer is entered) and prints out 1³ + 2³ + ... + n³.
    
2. As we noted in class, the sum of cubes to n equals the square of the sum of integers to n.  That is:
                1³ + 2³ + ... + n³ = (1 + 2 + ... + n)²
   Write a program, SumsOfCubesAndIntegers.java, which repeatedly reads in a non-negative integer n (exiting only when a negative integer is entered) and confirms that the two sides of this equation indeed are equal for that value of n.
    
3. Write a program, ParabolaPoints.java, which reads in three doubles -- a, b, and c -- followed by one non-negative integer k, and prints the values of the function y = ax² + bx + c for the first k integers.  That is, your program should function as follows (where user input is underlined):
                Enter a:  1.5
                Enter b:  2.5
                Enter c:  3.5
                Enter k:  4
                x     y = 1.5x^2 + 2.5x + 3.5
                1     7.5
                2     14.5
                3     24.5
                4     37.5
   Verify your program's output on a few equations using your calculator.
    
4. Write a program, Power.java, which reads in two non-negative integers, n and k, and prints out the value of n^k.  Note that you may not use "Math.pow" here.  Instead, you should use a "for" loop to repeatedly multiply n by itself k times.
    

5. The Maclaurin series for arctan(x) is a formula which allows us to compute an approximation to arctan(x) as a polynomial in x.  The formula is:
   
                arctan(x)  =  x - x³/3 + x⁵/5 - x⁷/7 + x⁹/9 - x¹¹/11 + . . .
   
   Write a program, ArctanSeries.java, which reads in a double x, and a positive integer k, and prints out the partial sum from the first k terms in this series and also prints out the value of Math.atan(x), which computes the arctangent directly.  Do the values agree?  Do they get closer as you increase k?  They should!
   
   Hint #1:  If the user enters 0.5 for x and 3 for k, you should compute:
                   0.5 - 0.5³/3 + 0.5⁵/5 = 0.464583....
   That is, the first 3 terms of the series with x = 0.5.  This turns out to be a good approximation, even with only 3 terms, as:
                   arctan(0.5) = 0.4636476....
   
   Hint #2:  For this problem, you will need to use Math.pow(a,b) which computes a^b.  Also, be sure your running sum is a double and not an integer!
   
   Hint #3:  Recall in class how we computed an alternating sum (adding, subtracting, adding,...) using a variable called "sign".  This is an integer initially set to 1.  We switch its sign, from positive to negative or from negative to positive, by setting it equal to its negation:
                sign = -sign;
   Now, just multiply each term by this alternating sign.  Voila!
    

6. From our math class, we know that, in radians, tan(π/4) = 1 and thus π/4 = arctan(1) and thus:
                π = 4 arctan(1) 
   We will combine this with the previous question to write a program that computes the value of pi!  By replacing x with 1 in the Maclaurin expansion of arctan(x), we see that:
                π = 4 (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + . . . )  
   Amazing!  Write a program PiFromArctan.java which reads in a positive integer k and uses this formula to approximate pi with the first k terms of the sum.  Be sure to multiply the sum by 4.  Also, confirm that it takes over 300 terms in order to get 2 decimals of precision in pi.
    
7. Leonard Euler, one of the greatest math minds ever, proved the following:
                π² = 6 (1/1² + 1/2² + 1/3² + 1/4² + 1/5² + ... )
   Astonishing!  This is also useful, since it converges to pi faster than the arctan series above.  To demonstrate this, write a program PiFromEuler.java which reads in a positive integer k and uses Euler's formula to approximate pi with the first k terms of this sum.  Be sure to multiply by 6 and then take the square root (since Euler's formula finds pi squared, not pi).  Finally, confirm that this converges faster than the previous method.

Note:  At the start of class we took Quiz #2 (see Quiz2.java).

1. Study and understand the following programs:
   * LoopingForever.java
   * NicerLoopingForever.java
   * SumFromOneToN.java
   * CuriousMultipleOf7.java
    
2. Write a program, Factorial.java, which repeatedly reads in a non-negative integer n (exiting only when a negative integer is entered) and prints out n! -- that is, n factorial, which is n * (n-1) * ... * 2 * 1.
   Hint #1:  This program is very similar to SumFromOneToN.java
   Hint #2:  0! = 1, not 0.
    
3. Write a program, NChooseK.java, which repeatedly reads in a non-negative integer n (exiting only when a negative integer is entered) followed by a second non-negative integer k (where 0 <= k <= n), and prints out the number of ways you can choose k items from among n total items.  We call this "n-choose-k", and the formula for "n-choose-k" is:  n! / (k! * (n-k)!).  So, for example:
        7-choose-2 = 7! / (2! * 5!) = 7*6/2 = 21.
   This means that there are 21 ways to choose 2 items from 7 total items.
    
4. Write a program, MakingChange.java, which repeatedly reads in an integer in [0,100), exiting only when a negative integer is entered, and makes appropriate change for that many cents. So, if the user enters, say, 73, your program should print that the change is 2 quarters, 2 dimes, and 3 pennies.
   Hint #1:  With integer division, 73 / 25 equals exactly 2, which is exactly the number of quarters you need (think about this!).
   Hint #2:  You can use % (mod, the remainder operator) to find how many cents remain after you give the two quarters.  Consider:  73 % 25 equals 23 (again, think about this!).
   Hint #3:  When you solve a problem like this, be sure to have a very clear grasp first of how you would solve this problem without Java.  For example, would you first figure out how many quarters to give or how many pennies to give?  However you would do it without Java is precisely how you should do it with Java!
    
5. Write a program, LargestProperDivisorOfN.java, which repeatedly reads in a positive integer n (exiting only when n is non-positive), and prints out the largest proper divisor of n (that is, the largest factor of n that is less than n itself).  To do this, set a variable "largestFactor" to 1, and use a "for" loop to run a counter from 2 to (n-1).  At each step, check if your counter is a factor of n (recall your IsFactor.java program from last week!).  If it is, set "largestFactor" to that number.  When you are done, print out the value of "largestFactor".  For example, your program may run like this (with user input underlined):
        Enter a positive number (or <=0 to exit):  34
        The largest factor of 34 less than itself is:  17
    
6. Write a program, IsPrime.java, which repeatedly reads in a positive integer n (exiting only when n is non-positive) and prints out whether or not n is a prime number.
   Hint #1:  This is really easy once you have LargestProperDivisorOfN.java working properly (think about it -- what is the largest proper divisor of any prime number?).
   Hint #2:  1 is not prime (2 is the smallest prime).
    
7. A perfect number is a positive integer which is the sum of its positive integer factors (these are just the prime factors plus 1 and the number itself). The first three perfect numbers are:
      6 = 1 + 2 + 3,
      28 = 1 + 2 + 4 + 7 + 14
      496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
   Write a Java program, IsPerfect.java, which reads in a positive integer n (exiting if n <= 0) and prints out whether or not n is a perfect number.
   Hint:  As with IsPrime.java, this program is very similar to LargestProperDivisorOfN.java.
    
8. Write a program, CRT.java, which prints out the smallest positive integer that has a remainder of 1 when divided by 17, a remainder of 3 when divided by 37, and a remainder of 5 when divided by 217.
   Hint #1:  This program is very much like CuriousMultipleOf7.java.
   Hint #2:  The answer is less than 250,000.
   Cool Factoid:  Ancient Chinese mathematicians were able to solve problems of this kind without the aid of Java programs!  They did it with a famous and very clever result called the Chinese Remainder Theorem.  If you would like to see the math needed to replace your simple Java program, check out the following link:
        http://www.cut-the-knot.org/blue/chinese.shtml

Note #1:  At the start of class we took Practice Quiz #2 (see PracticeQuiz2.java).

1. Rewrite each program from last week's assignment starting from this:  EmptyProgram.java.
   You must be able to easily write these programs from scratch, without referring to your notes!
    
2. Write a program, TriangleArea.java, which reads in three doubles -- the lengths of the sides of a triangle -- and prints out the area of the triangle using Heron's Formula:
   
   Note that if the three lengths cannot form a triangle, then you must print that out instead.  This occurs when the sum of any two sides is not greater than the third side, or if any of the sides is not positive.
    
3. Write a program, MilitaryToStandardTime.java, which reads in two integers -- the hour and minute in military time (so hours run from 0 to 23, minutes from 0 to 59) -- and prints out the same time in standard time.  For example, your program may run like this (with user input underlined):
        Enter the hour in military time:  3
        Enter the minute:  17
        The current time is:  3:17 a.m.
   or:
        Enter the hour in military time:  14
        Enter the minute:  32
        The current time is:  2:32 p.m.
   Hint:  A common mistake is to fail to handle the first hour of the day properly -- be sure that 0:17 maps to 12:17am.
    
4. On page 143 of our Precalculus textbook, you were asked to prove the following identity:
        tan x (cot x  cos x  + sin x) = sec x
   Here, we will not prove it, but merely emprically confirm it.  To do this, write a program, TrigIdentity.java, which reads in one double, x, and computes both the left-hand-side and the right-hand-side of the identity (printing out both values), then confirms that these are equal (well, very nearly equal, say within 0.000001, since doubles are not exactly equal in Java).  If they are equal, your program should print out that all seems ok, and if they are NOT equal, your program should declare that the identity is false!

Note #1:  At the start of class we took Quiz #1 (see Quiz1.java).
Note #2:  This week's assignment is abridged due to Thanksgiving (gobble, gobble!!!)

1. Study and understand the following programs:
   *  DoublesAsApproximates.java
   *  IfStatements.java
    
2. Write a program, PerpendicularLine.java, which reads in two doubles -- the slope "m" and y-intercept "b" of a line.  Your program should print out the equation of a line that is perpendicular to the given line and shares the same y-intercept.  Note:  if the first line is horizontal (that is, if the slope is 0), you must detect this and handle it gracefully (by printing out a helpful message about the line being horizontal, so its perpendicular is vertical, and hence does not have a defined slope).
    
3. Write a program, LineIntersections.java, which reads in four doubles -- the slope "m1" and y-intercept "b1" of one line, then the slope "m2" and y-intercept "b2" of a second line.  Your program should print out that point (x,y) where the two lines intersect.  However, your program must handle the special cases of the two lines being parallel or the two lines being the same line -- in both cases, you should print out a suitable message.
    
4. Write a program, PointInUnitCircle.java, which reads in two doubles -- a value "x" and a value "y", representing the point (x,y) -- and prints out whether or not that point lies inside the unit circle.
    
5. Write a program, AlmostEqual.java, which reads in two doubles and prints out whether or not the two values are within 0.00001 of each other.  Print out a suitable message either way.
   Hint:  For this, you may wish to use Math.abs(x), which computes the absolute value of its argument.
    
6. Write a program, IsFactor.java, which reads in two integers (not doubles) and prints out whether the smaller of the two integers is a factor of the larger of the two integers (regardless of which order the two numbers are entered in).  Either way, print out a suitable message.  For example, your program may run like this (with user input underlined):
        Enter a number:  8
        Enter another number:  2
        2 is a factor of 8
   or:
        Enter a number:  2
        Enter another number:  9
        2 is NOT a factor of 9
   Hint #1:  after you read in the two input values, create two variables, "smaller" and "larger", and use Math.min and Math.max to set these values based on the input values, then test whether "smaller" is a factor of "larger".
   Hint #2:  you will want to use the "%" (mod) operator, where (x % y) returns the remainder of x when divided by y.  So, for example, (13 % 5) equals 3.

1. Study and understand the following programs:
   *  HelloWorld.java
   *  IntegerSum.java
   *  DoubleSum.java
   *  IntegerMinAndMax.java
    
2. For each of the following programs, be sure to include useful prompts and "pretty" output.
    
3. Write a program, MyName.java, that prints out your name.
    
4. Write a program, IntegerQuotient.java, that reads in two integers and prints out their quotient.
    
5. Write a program, DoubleQuotient.java, that reads in two doubles and prints out their quotient.
    
6. Explain (briefly) how the two previous programs differ.  In particular, give some examples where the same input to the two programs produce different outputs, and explain why this occurs.  Place this explanation in a comment at the head of DoubleQuotient.java.
    
7. Write a program, AverageOfTwoIntegers.java, that reads in two integers and prints out their average.
    
8. Write a program, TrigValues.java, that reads in a double (an angle measure in degrees, not radians!) and prints out the sine, cosine, tangent, secant, cosecant, and cotangent for that angle.
   Hint #1:  For this, you will need Math.sin(x), Math.cos(x), and Math.tan(x).
   Hint #2:  These Math functions accept angles in radians, not degrees.  You'll have to do something about that!
   Hint #3:  You do not have to gracefully handle division-by-zero, (such as the cot(0)), though it may be interesting to see what your program does in this case.
    
9. Write a program, QuadraticRoots.java, that reads in three doubles a, b, and c -- the coefficients of a quadratic equation y = ax² + bx + c -- and prints out the two zeroes as found by the Quadratic Formula.
   Hint #1:  For this, you will need Math.sqrt(x), which computes the square root of its argument.
   Hint #2:  You may assume that the equation has two roots (though it may be interesting to see what your program does when the input only has one or zero roots).
    
10. What to submit and how to submit it:  For this and future weeks, bring a floppy disk (with your name clearly labeled on it) with all of your programs to class.  At the start of class, be prepared to show/discuss any/all of the programs from this week.
     
11. The Quiz:  study for a quick quiz on this material first thing Wednesday morning (11/24).  You will find that the quiz will be remarkably like one of the homework problems.  You will have <5 minutes to do the quiz.  If you do the homework and study just a bit, the quiz should be easy.  If you do not, though, the quiz will be basically impossible!

1. Install Java and JCreator (see Software Installation Procedures)
2. Get on the "ml-java-math" mailing list
3. Take Quiz #0 prior to attending class (see Quiz0.java)