Programming and Computer Science in Java:

See Course Home Page.

**Due
Date: Wed, Mar 12, 2003**

For each of the following questions, anything which your
programs *compute* must be computed within a new method, and not directly
inside your main method.

** Question 1:**
Write a Java program which reads in a positive integer n and computes the
cubed root of n. Note that you may
not use Math.pow(), but rather must adapt the binary search algorithm which you
used in Lab 1 to guess a number between 1 and 1 million.
To accomplish this, you must “box in” your answer with a “lo”
guaranteed to be no larger than the answer, and a “hi” guaranteed to be no
smaller. We can start with a
“lo” of 0 and a “hi” of n.

** Question 2:**
Find pi using Monte Carlo techniques, by throwing darts randomly into the
unit circle, as we discussed in class today.

** Question
3:** Write a Java program
which reads in three positive integers, n, r, and k, and prints out the kth
digit (after the decimal point) of the rth root of n.
So if you read in 3, 1, 2, you should print out the 1st digit after the
decimal point of the square root of 3. The
answer, thus, is 7, in this case.

** Question 4:** [ Most of this question is
borrowed from http://linus.socs.uts.edu.au/~rons/mss/Lect8.html
]: Over 5000 years ago, the ancient Babylonians discovered a
method for computing the square root of 2. They probably used that number (about
1.4) to construct right angles for the foundations of their buildings. This
iterative algorithm is still the simplest way to compute square roots.

If x is any number close to sqrt(2), then x^{2}
will be close to 2, which makes x close to 2/x. But 2/x will be on the other
side of sqrt(2) from x. That is, if x is less than sqrt(2), then 2/x will be
greater than sqrt(2), and vice versa.

For example, suppose that x = 1.6. Then 2/x = 1.25, which is on the other side of sqrt(2). This crossing over the limit is the key to the algorithm because it means that the average of x and 2/x must be between them and therefore closer to the objective sqrt(2). So the Babylonian Algorithm consists of choosing some number x that is close to sqrt(2), and then repeatedly replacing x by its average with 2/x.

Note that, due to roundoff errors, a constant (say 0.5E-8) is necessary to ensure that the algorithm terminates after a solution of sufficient accuracy has been found.

Your task is to write a Java program which reads in a positive integer n and uses the Babylonian Algorithm to compute the square root of n, and then prints out the answer.

** Question 5:**
Which is more efficient (that is, requires fewer steps) to compute the
square root of an integer, the Babylonian Algorithm or the Binary Search
Algorithm? We will address this
empirically. Change your programs
to not take any input. Rather, they
should compute the square roots of all integers in the range [1,100,000].
Next, keep a count of every guess your algorithm makes.
Print out the total number of guesses required for each algorithm, and
then if these are within 10%, print out that the algorithms are roughly
equivalent, otherwise print out which algorithm wins and by how much.

** Question 6:**
The natural logarithm of 2 is written ln(2), and can be computed as
follows:

ln(2)
= 1/1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + …

Write a Java program which uses this technique to compute the ln(2), stopping when the next term to be added or subtracted is smaller than 0.00001. Verify your answer by comparing with the value of ln(2) computed by using the builtin Java method, Math.log() (which computes the natural logarithm).

** Question 7:**
There are two digits a and b (so a and b are both in [0,9]) such that the
following is true:

(PI - a) / b = 1/(2 x 3 x 4) – 1/(4 x 5 x 6) + 1/(6 x 7 x 8) - 1/(8 x 9 x 10) + …

Write a Java program which correctly determines the values of a and b.

Hint #1: For any given a and b, keep expanding this expression until the next term is smaller than 0.000000001.

*Hint #2: At that point, because
there are infinitely many terms remaining, you don’t know how far away from
the answer you remain, so be generous, and assume that this result equals the
desired answer if they are within 0.01 of each other.
*

Good luck!

DK

See Course Home Page.