For this problem, you will analyze data from the Beijing 2008 Olympics by reading it from a file. First, copy this file to your hard drive: beijingOlympics.txt. The file contains a comma-separated list of each country that won at least one medal in these Olympics, and the number of gold, silver, and bronze medals they received, as such:
| Country | Gold | Silver | Bronze | Total |
| China | 51 | 21 | 28 | 100 |
| USA | 36 | 38 | 36 | 110 |
| Russian Fed. | 23 | 21 | 28 | 72 |
| Great Britain | 19 | 13 | 15 | 47 |
| ... | ... | ... | ... | ... |
The question we will be addressing is: which country won overall?
This depends on how you weight the gold, silver, and bronze medals.
For example, if you only count gold medals (give them a weight of 1 each,
with silvers and bronzes weighted 0 each), then China clearly won. But
if you weight each medal equally (all with a weight of 1, say), then the
United States (USA in the chart) won. There are other weightings, too,
of course. For example, if you think gold medals and silver medals are
each worth 1, but bronze medals are worth -3 (peculiar, yes, but also quite
legal), then there turns out to be a 3-way tie between the Czech Republic,
Poland, and Spain (all with 6 total points by those weights).
Based on this description, write a method, beijingOlympicsWinner, that takes 3 (possibly-negative,
possibly-zero) integers, the weightings for gold, silver, and bronze medals
(in that order), and a fourth parameter -- a String containing the path to
the data file -- and returns a string containing the name of the overall
winning country (exactly as the name appears in the first column). If
there is a tie, then return all the winning country names in a single
string, separated by vertical bars ("|"), ordered in the same order they
appear in the file. So, with the weightings of 1, 1, and -3 from
above, you would return "Spain|Poland|Czech Republic" (as they appear in
that order when listed by total medals, which is how the file is arranged).
Note: when we test your method, we will use a different data file --
same format, but different data.
Hint: you might want to tell the scanner to use a comma as a
delimiter!
Hint: The autograder is very picky. Be sure to name your method
exactly as specified, with exactly the same parameters and return
type!
For this problem, you will use real-time weather data supplied by the National Weather Service in a format designed for mobile devices. First, look at this page: http://mobile.srh.noaa.gov/. Then, in the "Local Weather Information by:" field, enter "Pittsburgh, PA" (without the quotes) and click Go. On that next page, click Current Conditions. At that point, you will be at this site:
http://mobile.srh.noaa.gov/port_mp_ns.php?select=3&CityName=Pittsburgh&site=PBZ&State=PA&warnzone=PAZ021
And you will see current weather conditions in Pittsburgh, something like this (where we have highlighted the temperature reading):
Pittsburgh, PA
Current Local Conditions at:
Pittsburgh International Airport
Lat: 40.51 N Lon: 80.22 W Elev: 1150 ft
Last Update: 10/02/09, 04:51 PM EDT
Weather: Overcast
Temperature: 58°F (14°C)
Humidity: 90 %
Wind Speed: S 7 MPH
Barometer: 29.66 in. (1005.1 mb)
Dewpoint: 55°F (13°C)
Visibility: 10.00 mi.
Based on this description, write a method, miamiHeat, that takes no
parameters and returns a single integer -- how many degrees Fahrenheit
warmer it is at this time in Miami, FL, as compared to Pittsburgh, PA.
For example, at the same time the data above was read, the temperature in
Miami, FL, was 75 degrees Fahrenheit (sigh...), so the difference is 75-32,
or 43 degrees. So the method would return 43. Of course, this
value changes constantly, and your method must return the current
difference, whatever it is. Also, if Pittsburgh is warmer than Miami
(not likely in the next few months), then the method would return a negative
value.
Note: as should be apparent, to complete this problem you will
have to follow the steps given above to find the URL for Miami's current
weather conditions.
Further note: it is very hard to write a good test method for
real-time varying data. Anything remotely reasonable will be accepted.
Hint: Once again... The autograder is very picky. Be sure to
name your method exactly as specified, with exactly the same
parameters and return type!
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).
Note: it is very hard to write a good test method for void methods. Anything remotely reasonable will be accepted.
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. The autograder requires this!
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.
Among his lesser-known exploits, the great German mathematician and astronomer Johannes Kepler studied how polygons can tile the plane or portions of the plane. For a fair bit of bonus, in a file named Lab5BonusKeplerPolygon.java, paint any of the following figure of Kepler's:
Do not be put off by the apparent complexity. Yes, it requires a clever combination of loops and trigonometry (sine and cosine), but you can do this! At least you can do it well enough to get a fair bit of bonus for your effort. Give it a try!!!!
Enjoy!!!
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.
Note: Place your solutions to this and the next bonus problems in the file Lab5BonusFSM.java.
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.