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).
- Be sure to include your name, your Andrew ID, and your section clearly on the top of each file in your assignment.
- Name your programs and your methods exactly as indicated.
- You will have exactly one program:
- Hw5.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 your recitation. Your
printed solutions must be identical copies of your emailed solutions!
- Note: You may use loops (do/while/for) or conditionals
("if" statements) to solve these problems.
- Show your work (for the non-programming problems). Correct answers without supporting calculations
will not receive full credit.
- Book Exercises
Do the following Exercises from Chapter 5 (pp 280-282):
Exercises 5.1 - 5.5 and 5.7 - 5.13
- 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!).
- 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...
- 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);
}
- 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);
}
- Counting Primes
In this exercise, we will observe an amazing property of the prime
numbers!
- 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]
}
- 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.
- 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);
}
- 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.
- 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.
- 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);
}
- 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).
- 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().
- 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().
- 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().
- 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!