Do the following Exercises from Chapter 5 (pp 280-282):
Exercises 5.1 - 5.5 and 5.7 - 5.13
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() {
verify(gcd(18,12) == 6);
verify(gcd(18,-8) == -1);
}
Optional aside: 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 fun (and for good quiz and test prep), you could write this method using Euclid's algorithm (but if you do, keep it iterative and not recursive -- that is, use a loop!).
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() {
verify(lcm(18,12) == 36); // note that 18*12 == 6*36, so x*y == gcd(x,y)*lcm(x,y)
verify(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...
Write a method with this signature:
public static boolean funnyContains(String s, String key)
}
Note: in writing this method you can only use the length and charAt methods from the String class.
This method takes two (possibly null!) Strings s and key, and returns true if s contains key and false otherwise (or if either string is null), with two caveats: the test for containment can go in either direction (left or right), and it can wraparound the end of the string. So, the string "abc" contains "ba" in reverse. It also contains "ca" due to wraparound, and "ac" in reverse with wraparound. Here is the start of a test method:
public static void testFunnyContains() {
verify(funnyContains("abc","ba") == true);
verify(funnyContains("abc","ca") == true);
verify(funnyContains("abc","ac") == true);
verify(funnyContains("b" ,"bbb") == true); // multiple wraparounds!
}
Write a method with this signature:
public static String makeAdditionProblem(double d1, double d2)
}
This method takes two doubles and if each is in the range [0,9999.9], it returns a single String that contains a nicely formatted addition problem, and returns "out of range" if either parameter is not in the given range, where "nicely-formatted" means:
1. All values are rounded to the nearest 10th
2. All decimal points align vertically
3. The second line has a preceding "+" sign and at least one space before the number
4. The third line contains as many right-aligned dashes as the largest of the two numbers and their sum requires when formatted this way.
5. The fourth line contains the sum of the rounded addends, where the sum is also rounded to the nearest 10th.
6. There is no extra whitespace besides what is required to satisfy the above conditions.
For example, if the method is called with the values 98.46 and 2.03, it would return a string that, when printed out, would display:
98.5
+ 2.0
-----
100.5
This is all stored in one string, though, with newlines (\n's), as such:
" 98.5\n+ 2.0\n -----\n 100.5"
Note #1: You may want to use the format method from the String class here (seeing as you are, well, formatting Strings...).
Here is the start of a test method:
public static void testMakeAdditionProblem() {
verify(makeAdditionProblem(2.3 ,3.5 ).equals(" 2.3\n+ 3.5\n ---\n 5.8"));
verify(makeAdditionProblem(1.05,2.05).equals(" 1.1\n+ 2.1\n ---\n 3.2"));
verify(makeAdditionProblem(-1,3).equals("out of range"));
verify(makeAdditionProblem(98.46,2.03).equals(" 98.5\n+ 2.0\n -----\n 100.5"));
}
Write a method with this signature:
public static String nthSplit(String s, char d, int n)
}
Note: in writing this method you can only use the length, charAt, and substring methods from the String class.
This method takes a String s, a char d (the delimiter), and an int n, and if s contains d at least n times, the method returns a new String comprising all the characters in s after the nth occurrence of d up to either the (n+1)st occurrence of d (which is not included in the result) or the end of the string, whichever comes first. If s does not contain d at least n times, the method returns null. In effect, the method "splits" the string up into a bunch of smaller strings, each separated by the given delimiter, and then returns the nth split string (hence the name, nthSplit). Here is the start of a test method:
public static void testNthSplit() {
verify(nthSplit("ab^cd^efg",'^',0).equals("ab"));
verify(nthSplit("ab^cd^efg",'^',1).equals("cd"));
verify(nthSplit("ab^cd^efg",'^',2).equals("efg"));
verify(nthSplit("ab^cd^efg",'^',3) == null);
}
Note: as you may recall, creating new Strings is wasteful, and should be minimized. For this reason, to receive full credit on this problem, you should not build the resulting string character-by-character using string concatenation. Instead, you should determine the start and end indices of the result, and then use the substring method of the String class to extract the entire substring at once.
Also note: there is a method called "split" in the String class which works similarly to the method just described, but it returns all the split strings in a single array of Strings. Once we learn about arrays (very soon now), we'll be able to write that method ourselves!
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 verify 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() {
verify(goldbachPrime(3) == -1);
verify(goldbachPrime(4) == 2);
verify(goldbachPrime(6) == 3);
verify(goldbachPrime(8) == 3);
verify(goldbachPrime(10)== 3);
}
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() {
verify(nthTwinPrime(-1) == -1);
verify(nthTwinPrime( 0) == 3);
verify(nthTwinPrime( 1) == 5);
verify(nthTwinPrime( 2) == 11);
verify(nthTwinPrime( 3) == 17);
verify(nthTwinPrime( 4) == 29);
}
[ Bonus / Optional ]
Note: this problem has an unusually verbose description, but rest assured it is no more difficult than the preceding problems. Finite State Machines play an important role in the theory of computation.
For this problem, we will consider a Finite State Machine. This is a very simple machine that has some states, which are numbered and which we will label with circles, and transitions between states, which are labeled with a character (here, either '0' or '1'). We begin in the start state, and we start reading the characters in a string (which must be made of only 0's and 1's). For each character, we move from the current state to the next state along the appropriate transition of the machine. At the end of the string, we say the machine accepts the string if the machine ends up in an accept state. Here, we will assume that there are no more than 10 states, labeled 0 through 9, with state 0 as the start state, and with only one accept state. For example, consider this machine:
The machine has 4 states (0, 1, 2, and 3, written as q0, q1, q2, q3). Its start state is q0. The double-circled state is the accept state, which in this case also happens to be q0 (though that is not always the case).
Now, let's see this machine in action. If the input string is "01", the machine starts in q0, follows the 0 to q1, then follows the 1 back to q0. Since it ends in the accept state, we say that the machine accepts the string "01"
For another example, let's try "110". Here, the machine starts in q0, and follows 1 to q2, then follows 1 to q3, then follows 0 again to q3. Since it ends in a non-accept state, we say that the machine does not accept the string "110".
Now, for this problem we need to encode a finite state machine (subject to our limitations of 10 states and only one accept state) in a string. We will do this as follows:
character 0: the accept state
character 1: the transition from state 0 on input 0
character 2: the transition from state 0 on input 1
character 3: the transition from state 1 on input 0
character 4: the transition from state 1 on input 1
character 5: the transition from state 2 on input 0
character 6: the transition from state 2 on input 1
...
So, we would encode the machine from above as this string:
"012300333"
To be sure you understand this, here is some explanation
character 0 (underlined here: "012300333"): the accept state is 0
character 1 (underlined here: "012300333"): state 0 on input 0 transitions to state 1
character 2 (underlined here: "012300333"): state 0 on input 1 transitions to state 2
character 3 (underlined here: "012300333"): state 1 on input 0 transitions to state 3
character 4 (underlined here: "012300333"): state 1 on input 1 transitions to state 0
...
Write a method with this signature:
public static int nextState(String machine, int state, char transition)
This method takes a machine description (like "012300333"), a current state (from 0 to 9), and a character (either 0 or 1) indicating which transition to take from the current state. The method returns the new state (an int from 0 to 9) which results from taking the given transition using the given machine specification.
Then, write a method with this signature:
public static boolean accepts(String machine, String input)
This method takes a machine description and an input string (which is guaranteed to be non-null and non-empty and containing only 1's or 0's), and returns true if the machine ends in an accept state when run on the given input string and false otherwise.
Note: this method will call your nextState() method for each character in the given input string.
Here is the start of a test method:
public static void testAccepts() {
verify(accepts("012300333","01") == true);
verify(accepts("012300333","110") == false);
}
[ Bonus / Optional ]
Write a method with this signature:
public static String toBinary(int n, int bits)
This method takes a non-negative integer and a required number of bits and returns a string of at least "bits" length representing that number in binary (base 2), adding leading 0's as necessary. If the number is longer than the given number of bits, it is not truncated but no leading 0's are added. If the first parameter is negative, the method returns null.
Note: while there are other ways to solve this, here you must work as follows:
Start with your result string equal to "".
If n is zero, just set the result to "0". Otherwise, while the number n > 0, extract the rightmost bit of n by taking the number n % 2, and add this on to the appropriate side of the result string, then divide the number n by 2 to shift it in binary one digit to the right. Keep doing this until n is 0.
Finally, add as many leading 0's as necessary.
Here is the start of a test method:
public static void testToBinary() {
verify(toBinary(5,6).equals("000101")); // Convert 5 to 6-bit binary
verify(toBinary(5,2).equals("101")); // Convert 5 to 2-bit binary (requires 3 bits)
verify(toBinary(-5,2) == null);
}
That was just the prelude. Now to the main act. Write a method with this signature:
public static void printLanguage(String machine, int maxDigits)
This method combines your previous two answers as such: it takes an FSM specification and a maximum number of digits. Then it generates every possible input using maxDigits or fewer, and prints out all the input strings that the FSM accepts in that range. To do this, the program runs a counter from 0 to (2maxDigits-1), and converts these values using the toBinary() method from above, then submits those strings to the accept() method from above. It prints out just those strings that are accepted.
Note: this method must print out to both the console and the file out.txt!
Hint: You do not have to compute the upper bound of (2maxDigits-1). Instead, you can just keep increasing your counter forever, but break out of your loop when toBinary() returns a string that is too long.
Finally, write a test method as such:
public static void testPrintLanguage()
Testing this method can be tricky, seeing as it is a "void". But we also save the output to the file "out.txt". So your test method should run printLanguage, read in the file "out.txt", and compare its contents to a known result.