Write the following method:
public static boolean sameChars(String s1, String s2)
This method takes two strings and returns true if the two strings are composed of the same characters (though perhaps in different numbers and in different orders) -- that is, if every character that is in the first string, is in the second, and vice versa -- and false otherwise. This test is case-sensitive, so "ABC" and "abc" do not contain the same characters. The method returns false if either string is null, but returns true if both strings are empty (why?). Here is a test method for you:
public static void testSameChars() {
System.out.print("Testing sameChars... ");
assert(sameChars("abc", "abc") == true);
assert(sameChars("abc", "cba") == true);
assert(sameChars("ab", "abc") == false);
assert(sameChars("abc", "ab") == false);
assert(sameChars("ababab", "ababbbb") == true);
assert(sameChars("ababab", "abcabbbb") == false);
assert(sameChars("abcabbbb", "ababab") == false);
assert(sameChars(null, null) == false);
assert(sameChars(null, "abc") == false);
assert(sameChars("abc", null) == false);
System.out.println("Passed all tests!");
}
Helper Method: sameChars1
In writing the sameChars method, you will see that you have to test whether
all the characters in s1 occur somewhere in s2, and then if all the
characters in s2 occur somewhere in s1. This suggests that we write
the following helper method (which in fact you must write):
Write the following method helper method for your sameChars method:
public static
boolean sameChars1(String s1, String s2)
This method works the
same as sameChars, only in one direction: it only checks whether all
the characters in s1 occur somewhere in s2. That is, this method takes
two strings and returns true if the first string is composed only of letters
occurring in the second string (though perhaps in different numbers and in
different orders) -- that is, if every character that is in the first
string, is in the second -- and false otherwise. This test is
case-sensitive, so "ABC" and "abc" do not contain the same characters. The
method returns false if either string is null, but returns true if both
strings are empty (why?). Here is a test method for you:
public static void testSameChars1() {
System.out.print("Testing sameChars1... ");
assert(sameChars1("abc", "abc") == true);
assert(sameChars1("abc", "cba") == true);
assert(sameChars1("ab", "abc") == true); // false for sameChars
assert(sameChars1("abc", "ab") == false);
assert(sameChars1("ababab", "ababbbb") == true);
assert(sameChars1("ababab", "abcabbbb") == true); // false for sameChars
assert(sameChars1("abcabbbb", "ababab") == false);
assert(sameChars1(null, null) == false);
assert(sameChars1(null, "abc") == false);
assert(sameChars1("abc", null) == false);
System.out.println("Passed all tests!");
}
Another Helper Method: contains
In writing the sameChars1
method, you will need to iterate over every character in s1 and test whether
that character occurs in s2 This suggests that we write the yet
another helper method (which you also must write):
Write the following method helper method for your sameChars method:
public static
boolean contains(String s, char c) {
This method takes a
string and a char and returns true if the given char occurs in the given
String and false otherwise. The method also returns false if the String is
null. Here is a test method for you:
turns true if the first string is composed only of letters occurring in the
second string (though perhaps in different numbers and in different orders)
-- that is, if every character that is in the first string, is in the second
-- and false otherwise. This test is case-sensitive, so "ABC" and
"abc" do not contain the same characters. The method returns false if either
string is null, but returns true if both strings are empty (why?).
Here is a test method for you:
public static void testContains() {
System.out.print("Testing contains... ");
assert(contains("abcd",'c') == true);
assert(contains("abcdabcd",'d') == true);
assert(contains("This is a test!",'!') == true);
assert(contains("abcd",'e') == false);
assert(contains("",'f') == false);
assert(contains(null,'g') == false);
System.out.println("Passed all tests!");
}
Reminder: You may not use any String methods except charAt() and length()
in this assignment. Using other String methods will result in zero
points for that problem.
Note: When writing sameChars, we decomposed the problem with the
helper method sameChars1. Then, when writing that method, we further
decomposed the problem with the helper method contains. This approach
of problem solving by repeated decomposition is called
top-down design. It
is a very effective way to design well-written and robust programs,
especially when each helper method is carefully tested with its own test
method (which is called unit
testing).
Note:
Top-down design
via decomposition
into helper
methods along with
unit testing
is a great way to design your programs. You are expected to use
this approach in this and all future programming assignments.
Write the following method:
public static int nthTwinPrime(int n)
This method takes an int value n and returns the nth "twin prime", where a twin prime is a number p that is prime where (p+2) is also prime. So 3 is a twin prime because 5 is prime, and 5 is a twin prime because 7 is prime, but 7 is not a twin prime because 9 is not prime. If n is less than 1, the method should return -1. Here is a test method for you:
public static void testNthTwinPrime() {
System.out.print("Testing nthTwinPrime... ");
assert(nthTwinPrime(-5) == -1);
assert(nthTwinPrime(0) == -1);
assert(nthTwinPrime(1) == 3);
assert(nthTwinPrime(2) == 5);
assert(nthTwinPrime(3) == 11);
assert(nthTwinPrime(4) == 17);
assert(nthTwinPrime(5) == 29);
assert(nthTwinPrime(6) == 41);
System.out.println("Passed all tests!");
}
Note: to receive full credit, you must write at least one
well-chosen helper method (and its corresponding test method) for this
method.
In this exercise, we will observe an amazing property of the prime numbers!
- The Prime Counting Function: pi(n)
Write the following method:
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 a test method:public static void testPi() { System.out.print("Testing pi... "); 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] System.out.println("Passed all tests!"); } - The Harmonic Number: h(n)
Write the following method:
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 a test method:public static void testH() { System.out.print("Testing H... "); assert(almostEqual(h(0),0.0)); assert(almostEqual(h(1),1/1.0 )); // h(1) = 1/1 assert(almostEqual(h(2),1/1.0 + 1/2.0 )); // h(2) = 1/1 + 1/2 assert(almostEqual(h(3),1/1.0 + 1/2.0 + 1/3.0)); // h(3) = 1/1 + 1/2 + 1/3 System.out.println("Passed all tests!"); }Note: here we use "almostEqual" rather than "==" because this method returns a double.
- Using the Harmonic Number to estimate the Prime Counting
Function (Wow!)
Write the following method:
public static int estimatedPi(int n)
This method uses the Harmonic Number function h(n) to estimate the Prime Counting Function pi(n). 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() { System.out.print("Testing estimatedPi... "); assert(estimatedPi(100) == 27); assert(estimatedPi(200) == 46); assert(estimatedPi(300) == 63); System.out.println("Passed all tests!"); } - Empirical check that this really works:
estimatedPiError
Write the following method:
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() { System.out.print("Testing estimatedPiError... "); 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 System.out.println("Passed all tests!"); }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.
Write the following method:
public static int wordCount(String filename)
This method takes a String that should be a filename and returns the number of words in the given file, where a "word" is whatever is returned by a call to scanner.next(). If the file does not exist, the method returns -1. Here is a test method for you:
public static void testWordCount() {
System.out.print("Testing wordCount... ");
// First, create the file "wordCountTest.txt"
String filename = "wordCountTest.txt";
PrintStream out = getFilePrintStream(filename);
out.println("Roses are red,");
out.println("Violets are blue.");
out.println("Some poems rhyme,");
out.println("But not this one.");
// now count the words!
assert(wordCount(filename) == 13);
String nonExistentFilename = "FileThatDoesNotExist.txt";
assert(wordCount(nonExistentFilename) == -1);
System.out.println("Passed all tests!");
}
Note: in general, to receive full credit, you must write well-chosen helper methods
where appropriate. It turns out that this method is simple
enough that it does not need a helper method.
Hint: You should use the getFileScanner helper method
from the notes. Also, note that this method returns null if the file
does not exist.
Hint: You will call scanner.next() to get each word, but we
don't really care what the words themselves are, so you will in fact
ingore the result of this call! Just keep calling scanner.next()
until there is no more input.
Write the following method:
public static int currentTemperature()
This method takes no parameters and computes the current temperature (in degrees fahrenheit) in Pittsburgh as listed on:
http://mobile.srh.noaa.gov/port_mp_ns.php?select=3&CityName=Pittsburgh&site=PBZ&State=PA&warnzone=PAZ021
This web page will list current weather conditions in Pittsburgh like so:
Pittsburgh, PA
Current Local Conditions at:
Pittsburgh International Airport
Lat: 40.51 N Lon: 80.22 W Elev: 1150 ft
Last Update: 09/10/08, 11:51 AM EDT
Weather: A Few Clouds
Temperature: 65°F (18°C)
Humidity: 47 %
Wind Speed: NE 8 MPH
Barometer: 30.29 in. (1026.2 mb)
Dewpoint: 44°F (7°C)
Visibility: 10.00 mi.
The method must read this data, find the line indicating the temperature, and extract the answer from that line. To keep this simple, you should just find the first line that starts with "T" and assume it is the temperature line, then extract the 14th and 15th characters ("65" in the example above) to compute the temperature (which you should assume is between 10 and 99 degrees Fahrenheit, so indeed requires two digits to display). Here is a test method for you:
public static void testCurrentTemperature() {
System.out.print("Testing currentTemperature.. ");
int temp = currentTemperature();
assert((temp > 0) && (temp < 100));
System.out.println("Passed all tests (if current temp is " + temp + ")!");
}
Hint: Here you should use the getUrlTextScanner
helper method from the notes.
Write the following method:
public static void numberGuessingGame()
This method takes no parameters and plays the number guessing game, where the user thinks of a number between 0 and 1000 and the computer guesses it. The user repeatedly instructs the computer if the guess is too low, correct, or too high, and the computer continues guessing until it gets the right answer. Each guess must be exactly halfway between the known limits. Here is exactly what your method's output should look like (with user input underlined, and in this case the user thought of the number 374):
Think of a number between 0 and 1000.
Your number is between 0 and 1000.
I guess: 500
Is this correct? (y/n) n
Is 500 too high? (y/n) y
Your number is between 0 and 499.
I guess: 249
Is this correct? (y/n) n
Is 249 too high? (y/n) n
Your number is between 250 and 499.
I guess: 374
Is this correct? (y/n) y
I got it in 3 guesses!
Let's take a closer look at this. At first, the number is in the range [0, 1000], so the guess is 500 (midway). The user indicates that this is incorrect, and further that it is too high. Since 500 is too high, we now know that 499 is the highest possible answer, so the number is in the range [0, 499]. The guess should be the average of these two numbers, which is 249.5, but we're dealing with integers only here, so we truncate to 249. The user indicates that this is too low, so the lowest possible answer is now 250, so the range is now [250, 499]. The average of these (with truncation) is 374, and that is our new guess. The user indicates that we are correct, so we print out our total guess count and return. If the program gets to the point that no more guesses are possible (because the user either picked a number out of the legal range or otherwise made a mistake), it should print out "Impossible!" and return. Also, if the program gets it on the first guess (how lucky!), it should print out "I got it in 1 guess!" (notice it prints "guess" and not "guesses" in this case).
This method will be tested by hand, so here is the not-very-useful test method for you:
public static void testNumberGuessingGame() {
System.out.print("Testing currentTemperature.. ");
System.out.println("Manual testing required!");
System.out.println("---------------------------------------");
numberGuessingGame();
System.out.println("---------------------------------------");
System.out.println(" ... Passed all tests (if it looks right!)");
}
Note: For user responses to the yes/no questions, you can presume
the user types "y" or "n", and you do not have to deal with other cases.Hint: Remember that your output must exactly match the examples above.
Write a method that takes no parameters and uses the National Weather Service's web page noted above to compute the current windchill in Pittsburgh. To do this, you will have to extract not just the temperature but also the windspeed from that page (assuming the windspeed is 0 if it is not represented as an integer, as may happen for example if it is "Calm"), and then you will have to use the formula for windchill as is provided in this helpful graphic (look near the bottom) from the National Weather Service:
(from: http://www.weather.gov/os/windchill/index.shtml)
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 this method:
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 this method:
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() {
assert(accepts("012300333","01") == true);
assert(accepts("012300333","110") == false);
}
You must also write a few more well-designed test cases.
Note: only attempt this question if you have completed Finite State Machines, part 1.
Write this method:
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() {
assert(toBinary(5,6).equals("000101")); // Convert 5 to 6-bit binary
assert(toBinary(5,2).equals("101")); // Convert 5 to 2-bit binary (requires 3 bits)
assert(toBinary(-5,2) == null);
}
That was just the prelude. Now to the main act. Write this method:
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.