2.3. FLOW-OF-CONTROL STATEMENTS

We use the term flow of control to refer to the sequence of statements that are executed in a program. All of the programs that we have examined to this point have a simple flow of control: the statements are executed one after the other in the order given. Most programs have a more complicated structure where statements may or may not be executed depending on certain conditions (conditionals), or where groups of statements are executed multiple times (loops). These statements truly harness the power of the computer and will equip you to write programs to accomplish a broad variety of tasks that you could not contemplate attempting without a computer.

If statements. Most computations require different actions for different inputs. Program Flip.java uses an if-else statement to print out the results of a coin flip. The table below summarizes some typical situations where you might need to use an if or if-else statement.

PURPOSE	JAVA
absolute value	`if (x <0) x=-x;`
maximum of x and y	`if (x > y) max = x; else max = y;`
income tax rate	`if (income < 47450) rate=0.22; else if (income <114650) rate=0.25; else if (income <174700) rate=0.28; else if (income <311950) rate=0.33; else rate = 0.35;`
error check for arithmetic operation	`if (d == 0) System.out.println("Division by zero"); else System.out.println("Quotient = " + n/d");`
error check for quadratic formula	`d = bb - 4.0c; if (d <0.0) System.out.println("No real roots"); else { d = Math.sqrt(d); System.out.println((-b + d) / 2.0); System.out.println((-b - d) / 2.0); }`

The while statement. Many computations are inherently repetitive. The while enables us to perform a group of statements many times. This enables us to express lengthy computations without writing lots of code. As an example, the program TenHellos.java prints out "Hello World" 10 times. The following four lines of code demonstrate how to use a while loop.

int i = 4;
while (i <= 10) { system.out.println(i + "th Hello" ); i=i + 1;

The program PowersOfTwo.java uses a while loop to print out a table of the powers of 2. In computer science, it's important to be familiar with powers of 2. You should know at least the first 10 values in this table and note that 2¹⁰ is about 1 thousand, 2²⁰ is about 1 million, and 2³⁰ is about 1 billion.

The for statement. Many loops follow the same basic scheme: initialize an index variable to some value and then use a while loop to test an exit condition involving the index variable, using the last statement in the while loop to modify the index variable. Java's for loop is a direct way to express such loops. The following two lines of code are equivalent to the final five lines of code in TenHellos.java:

for (int i = 4; i <= 10; i++) system.out.println(i + "th Hello" );

The idiom i++ is a shorthand notation for i = i + 1 and we use it frequently, especially with for loops.

Applications. The ability to program with loops and conditionals immediately opens up the world of computation to us. To emphasize this fact, we consider a variety of examples below and in the exercises. These programs are carefully crafted -- by studying and appreciating them, you will be in a good position to write your own programs containing loops.

Ruler subdivisions. Program Ruler.java reads in a command line parameter N and prints out the string of ruler subdivision lengths. This program illustrates one of the essential characteristics of loops - the program could hardly be simpler, but it can produce a huge amount of output.

Finite sums. The computational paradigm used in Program PowersOfTwo.java is one that you will use frequently. It uses two variables - one as an index that controls a loop, and the other to accumulate a computational result. Program Harmonic.java uses the same paradigm to evaluate the sum

H_N = 1/1 + 1/2 + 1/3 + 1/4 + ... + 1/N

These numbers, which are known as the Harmonic numbers, arise frequently in the analysis of algorithms. They are the discrete analog of the logarithm: they approximate the area under the curve y = 1/x from x = 1 to x = N. This approximation is a special example of numerical integration which we will consider in Chapter 9.

Computing the square root. How are functions in Java's Math library such as Math.sqrt implemented? Program Sqrt.java uses a classic iterative technique that dates back to Heron of Alexandria in the first century. It is a special case of the more general Newton-Raphson method. For computing the square root of a positive number x, Newton's method is simple to describe: Start with an estimate t. If t is equal to x/t (up to machine precision), then t is equal to a square root of x, so the computation is complete. If not, refine the estimate by replacing t with the average of t and x/t. Each time we perform this update, we get closer to the desired answer. Remarkably, we get the value of the square root of 2 to accurate to 15 decimal places in just 5 iterations of the loop.

Number conversion. Program Binary.java prints the binary (base 2) representation of the decimal number typed as the command line argument. It is based on decomposing the number into a sum of powers of two. For example, the binary representation of 106 is 1101010, which is the same as saying that 106 = 64 + 32 + 8 + 2, or in binary, 1101010 = 1000000 + 100000 + 1000 + 10. To compute the binary representation of N, we consider the powers of 2 less than or equal to N in decreasing order to determine which belong in the binary decomposition (and therefore correspond to a 1 bit in the binary representation).

Gambler's ruin. Our next example is representative of a widely used class of programs, where we use computers to simulate what might happen in the real world, so that we can make informed decisions in all kinds of complicated situations. The problem was originally posed in 1654 by French mathematician Blaise Pascal to his colleague Pierre de Fermat. Suppose a gambler makes a series of fair $1 bets, starting with $50, and continue to play until she either goes broke or has $250. What are the chances that she will go home with $250, and how many bets might she expect to make before winning or losing? Program Gambler.java is a simulation that can help answer these questions. It reads in three command line parameters, the initial stake ($50), the goal amount ($250), and the number of times we want to simulate the game. Then, it uses Math.random to simulate the fair bets, continuing until the gambler goes broke or reaches the goal. It keeps track of the number of wins and the number of bets, and after the specified number of trials, it averages and prints out the results. The program illustrates a nested loop, that is, a loop within a loop.

Factoring. Program Factors.java takes a command line parameter N and prints its prime factorization. In contrast to many of the other programs that we have seen (which we could do in a few minutes with a calculator or pencil and paper), this computation would not be feasible without a computer. This problem is more than a toy mathematical exercise; in fact it lies at the hear of the RSA cryptosystem which we will describe in chapter Chapter 10. The outer for loop iterates over potential factors i of our number N. The inner while checks if i is a factor of N using the condition (N % i == 0) and divides out all factors of i, printing out each factor simultaneously. The key to understanding why the program works is to see that at the beginning of each iteration of the for loop, N has no nontrivial factors less than i. Thus, if i is not prime, it will not divide N; if i is prime, the while loop will do its job. Moreover, since we know that N has no nontrivial factors less than i, we also know that it has none greater than N/i; so we need look no further.

Other conditional and loop constructs. To be complete, we consider four more Java constructs related to conditionals and loops. They are used much less frequently than the if, while, and for statements that we've been working with, but it is worthwhile to be aware of them.

Do-while statements. A do-while loop is almost the same as a while loop except that the loop continuation condition is omitted the first time through the loop. If the conditional initially holds, there is no difference. For example, the following code sets x and y such that (x, y) is randomly distributed inside the circle centered at (0, 0) with radius 1.

double x, y, r;
do {
   x = 2.0 * Math.random() - 1.0;
   y = 2.0 * Math.random() - 1.0;
   r = x*x + y*y;
} while (r > 1);

With Math.random we get points that are randomly distributed in the 2-by-2 square center at (0, 0). We just generate points in this region until we find one that lies inside the unit disk. We always want to generate at least one point so a do-while loop is most appropriate. Note that we declare x and y outside the loop since we will want to access their values after the loop terminates.

Random numbers from the Gaussian distribution.

Add this to book. This do-while loop is a key ingredient in simulating a standard Gaussian (normal) random variable using the rectangular form of the Box-Muller transform. Given a point (x, y) uniformly distributed inside the circle centered on the origin with radius 1 (and not equal to the origin), the quantity x sqrt(-2 ln(r) / r) is normally distributed with mean 0 and standard deviation 1. This method is preferred over the one described in Exercise XYZ for both efficiency and accuracy. Although it involves a loop, the do-while loop is executed only 4 / π = 1.273 times on average. This reduces the overall expected number of calls to transcendental functions. Program StdGaussian.java implements this method.

Break statements. In some situations we want to immediate exit a loop, without letting it run to completion. Java provides the break statement for this purpose. Program Prime.java takes a command line parameter N and prints out true if N is prime, and false otherwise. It illustrates that we can break out of a loop using the "break" statement (as soon as we find an some integer that divides i, we know that i is not prime and can stop looking). Determining whether a number is prime is easy to do if the number is small, but is a challenge if the number is huge. We will look at some better methods later on. Huge prime numbers have important applications in cryptography, so researchers still seek better methods for testing primality.

Lessons

Logic dictates flow of control.
for and while statements are equivalent: use whichever fits.
Simple computations with integers and real numbers already takes us to the unknown.

Q + A

Q. My program is stuck in an infinite loop. How do I stop it?

A. Type <Ctrl-c> at the terminal window. That is, hold down the key labeled Ctrl and press the c symbol.

Q. How can I check whether two strings are equal? Using == doesn't work.

A. To check whether two strings s and t contain the same sequence of characters, use if(s.equals(t)). The reason == doesn't work consistently will become clear in Section 3.1 when we consider objects.

Q. Why is it important to consistently format, indent, and comment code?

A. When writing an essay, your message is more convincing when it is accompanied by proper grammar and punctuation. When writing computer programs, you should follow the same principle. It is even more important when programming since someone may be assigned to maintain and support your code for long periods of time. You will appreciate the importance of good style when it is your task to understand and maintain someone else's code!

Q. How much commenting should I do?

A. There is no definitive answer. As a general rule, the code explains to the computer and programmer what is being done; the comments explain to the programmer why it is being done. At a minimum, comment each program and function with its inputs, outputs, and purpose. Comment each large block of code with its overall purpose. Comment each important variable with its purpose when you define it.

Exercises

Write a program Equal3 that reads in three integer parameters from the command line a prints equal if all three are equal, and not equal otherwise.
What is wrong with each of the following statements?
1. if (a > b) then c = 0;
2. if a > b { c = 0; }
3. if (a > b) c = 0;
4. if (a > b) c = 0 else b = 0;
Write a more general and robust version of Quadratic.java that prints the roots of the polynomial ax² + bx + c and prints an appropriate error message if the discriminant is negative, and behaves appropriately (avoiding division by zero) if a and/or b are zero.
Extend your solution to Exercise 2.2.16 to convert (x, y) to polar coordinates for any values of x and y.
Suppose that i and j are both of type int. What is the value of j after each of the following statements is executed?
1. for (i = 0, j = 0; i <10; i++) j +=i;
2. for (i = 0, j = 1; i <10; i++) j +=j;
3. for (j = 0; j <10; j++) j +=j;
4. for (i = 0, j = 0; i <10; i++) j +=j++;
Rewrite TenHellos.java to make a program Hellos.java that takes the number of lines to print as a command-line argument. You may assume that the argument is less than 1000. Hint: consider using i % 10 and i % 100 to determine whether to use "st", "nd", "rd", or "th" for printing the ith Hello.
Write a program FivePerLine.java that, using one for loop and one if statement, prints the integers from 1000 to 2000 with five integers per line. Hint: use the % operator.
Write a program Average.java that takes an integer N as a command line argument and uses Math.random to print N uniform random variables between 0 and 1, and then prints their average value.
Describe what happens when you invoke Ruler.java with an argument that is too large, such as java Ruler 100.
Write a program PowersOfK.java that takes an integer K as command line argument and prints all the positive powers of K in the Java long data type. Note: the constant Long.MAX_VALUE is the value of the largest integer in long.
Write a program FunctionGrowth.java that prints a table of the values of log N, N, N log N, N², N³, and 2^N for N = 16, 32, 64, ..., 2048. Use tabs ('\t' characters) to line up columns.

What does the following code print out?

int f = 0, g = 1;
for (int i = 0; i <= 15; i++) { system.out.println(f); f=f + g; g=f - g; }

Write a version of the program in the previous exercise that prints the ratio of successive Fibonacci numbers, for all those in Java's int data type.
Expand CarLoan.java from Exercise 2.2.15 to print a table giving the total amount paid and the remaining principal after each monthly payment.

What is the value of M after executing the following code?

int N = 123456789;
int M = 0;
while (N != 0) {
   M = (10 * M) + (N % 10);
   N = N / 10;
}

The sum 1/1 + 1/4 + 1/9 + 1/16 + ... + 1/N² does converge to a constant as N approaches infinity. Indeed, the constant is π² / 6, so this formula can be used to compute the value of π. Which of the following for loops does the job? Assume that N is an int initialized to 1000000 and sum is a double initialized to 0.

(a) for (int i = 1; i <= n; i++) (b) for (int i=1; i <=N; i++) sum=sum + 1 / (i * i); sum=sum + 1.0 / i * i; (c) for (int i=1; i <=N; i++) (d) for (int i=1; i <=N; i++) sum=sum + 1.0 / (i * i); sum=sum + 1 / (1.0 * i * i);

Using the fact that the slope of the tangent to a (differentiable) function f(x) at x = t is f'(t), find the equation of the tangent line and use that equation to find the point where the tangent line intersects the x axis to show that you can use Newton's method to find a root of any function f(x) as follows: at each iteration, replace the estimate t by t - f(t) / f'(t). Then use the fact that f'(t) = 2t for f(x) = x² - c to show that Sqrt.java implements Newton's method for finding the square root of c.
Use the general formula for Newton's method in the previous exercise to develop a program Root.java that takes two command line arguments c and k, and prints the kth root of c. Assume k is a positive integer. You may use Math.pow, but only with an exponent that is a nonnegative integer.
Suppose that x and t are variables of type double and N is a variable of type int. Write a code fragment to set t to x^N / N!.
Modify Binary.java to get a program Modify Kary.java that takes a second command line argument K and converts the first argument to base K. Assume the base is between 2 and 20. For bases greater than 10, use the letters A through K to represent the 11th through 20th digits, respectively.
Write a code fragment that puts the binary representation of an int N into a String s.
Write a version of Gambler.java that uses a for loop instead of a while loop.
Write a program GamblerPlot.java that traces a gambler's ruin simulation by printing a line after each bet that has one asterisk corresponding to each dollar held by the gambler.
Modify Gambler.java to take an extra command line parameter that specifies the (fixed) probability that the gambler wins each bet. Use your program to try to learn how this probability affects the chance of winning and the expected number of bets.
Modify Gambler.java to take an extra command line parameter that specifies the number of bets the gambler is willing to make, so that there are three possible ways for the game to end: the gambler wins, loses, or runs out of time. Add to the output to give the expected amount of money the gambler will have when the game ends.
Modify Factors.java to print just one copy of each of the prime divisors.
Run quick experiments to determine the impact of using the loop continuation condition (i <= n/i) instead of (i <= n) in Factors.java. For each loop continuation condition, find the largest integer M such that when you type in an M digit number, the program is sure to finish within 10 seconds.
Write a program GCD.java that find the greatest common divisor (gcd) of two integers x and y using Euclid's algorithm, which is an iterative computation based on the following observation: If x > y, then if y divides x, the gcd of x and y is y; otherwise the gcd of x and y is the same as the gcd of x % y and y.
Write a program Checkerboard.java that takes one command line parameter N and prints out a two dimensional N-by-N checkerboard pattern with alternating spaces and asterisks, like the following 4-by-4 pattern.
* * * * * * * * * * * * * * * *
Write a program Divisors.java that takes one command line parameter N and prints out an N-by-N table such that there is an asterisk in row i and column j if the gcd of i and j is 1 (i and j are relatively prime), and a space otherwise. See Exercise 2.3.28.

Creative Exercises

Ramanujan's taxi. S. Ramanujan was an Indian mathematician who became famous for his intuition for numbers. When the English mathematician G. H. Hardy came to visit him in the hospital one day, Hardy remarked that the number of his taxi was 1729, a rather dull number. To which Ramanujan replied, "No, Hardy! No, Hardy! It is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways." Verify this claim by writing a program Ramanujan.java that takes a a command line argument N and prints out all integers less than or equal to N that can be expressed as the sum of two cubes in two different ways - find distinct positive integers a, b, c, and d such that a³ + b³ = c³ + d³. Use four nested for loops.
Now, the license plate 87539319 seems like a rather dull number. Determine why it's not.
Checksums. The International Standard Book Number (ISBN) is a 10 digit code that uniquely specifies a book. The rightmost digit is a checksum digit which can be uniquely determined from the other 9 digits from the condition that d₁ + 2d₂ + 3d₃ + ... + 10d₁₀ must be a multiple of 11 (here d_i denotes the ith digit from the right). The checksum digit d₁ can be any value from 0 to 10: the ISBN convention is to use the value X to denote 10. Example: the checksum digit corresponding to 020131452 is 5 since is the only value of d₁ between 0 and and 10 for which d₁ + 2*2 + 3*5 + 4*4 + 5*1 + 6*3 + 7*1 + 8*0 + 9*2 + 10*0 is a multiple of 11. Write a program ISBN.java that takes a 9-digit integer as a command line argument, computes the checksum, and prints out the 10-digit ISBN number. It's ok if you don't print out any leading 0's.
Calendar. Write a program Calendar that takes two command line arguments m and y and prints out the monthly calendar for the mth month of year y. For example, your output for Calendar 2 2009 should be
February 2009 S M Tu W Th F S 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Hint: see programs LeapYear.java and Day.java.
Counting primes. Write a program PrimeCounter.java that takes one command line argument N and prints out the number of primes less than N. Use it to print out the number of primes less than 10 million. Note: if you are not careful to make your program efficient, it may not finish in a reasonable amount of time. Later in Section 2.4, we will learn about a more efficient way to perform this computation called the Sieve of Eratosthenes.
Dragon curves. Write a program Dragon.java that takes a command line parameter N and prints out the instructions for drawing a dragon curve of order N. See exercise 2.2.18.
What happens when you try to compile the following code fragment?
double x; if (a >= 0) x = 3.14; if (a <0) x=2.71; system.out.println(x);
Answer: it complains that the variable x might not have been initialized (even though we can clearly see that x will be initialized by one of the two if statements). You can avoid this problem here by using if-else.
Exponential function. Assume that x and sum are variables of type double. Write a code fragment to use the Taylor series expansion to set the value of sum to
e^x = 1 + x + x²/2! + x³/3! + x⁴/4! + . . .
Trigometric functions. Write two programs Sin.java and Cos.java that compute sin x and cos x using the Taylor series expansions
sin x = x - x³/3! + x⁵/5! - x⁷/7! + . . .
cos x = 1 - x²/2! + x⁴/4! - x⁶/6! + . . .
Experimental analysis. Run experiments to determine the relative costs of Math.exp and the following three methods from Exercise 2.3.36 for the problem of computing e^x: the direct method with nested for loops, the improved method with a single for loop, and the latter with the termination condition (term > 0). For each method, use trial-and-error with a command line argument to determine how many times your computer can perform the computation in 10 seconds.
2D random walk. A two dimensional random walk simulates the behavior of a particle moving in a grid of points. At each step, the random walker moves north, south, east, or west with probability 1/4, independently of previous moves. Write a program RandomWalker.java that takes a command line parameter N and estimates how long it will take a random walker to hit the boundary of a circle of radius N, centered on the starting point. (Theoretical answer: N^2.)
2D random walk. Repeat the previous question, but determine how far away the random walker is from the starting point after N steps. Name your program Random2DWalk.java. (Theoretical answer: sqrt(N).)
Game simulation. In the 1970s game show called "Let's Make a Deal", a contestant is presented with three doors. Behind one door is a valuable prize, behind the other two are gag gifts. After the contestant chooses a door, the host opens up one of the other two doors (never revealing the prize, of course). The contestant is then given the opportunity to switch to the other unopened door. Should the contestant do so? Intuitively, it might seem that the contestant's initial choice door and the other unopened door are equally likely to contain the prize, so there would be no incentive to switch. Write a program MonteHall.java to test this intuition by simulation. Your program should take a command line parameter N, play the game N times using each of the two strategies (switch or don't switch) and print the chance of success for each strategy. Or you can play the game here.
Chaos. Write a program to student the following simple model for population growth, which might be applied to study fish in a pond, bacteria in a test tube, or any of a host of similar situations. We suppose that the population ranges from 0 (extinct) to 1 (maximum population that can be sustained). If the population at time t is x, the we suppose the population at time t+1 to be rx(1-x), where the parameter r, sometimes known as the fecundity parameter, controls the rate of growth. Start with a small population, say x = 0.01, and study the result of iterating the model, for various values of r. For which values of r does the population stabilize at x = 1 - 1/r? Can you say anything about the population when r is 3.5? 3.8? 5? Biologists model population growth of fish in a pond using the logistic equation. Investigate some of its chaotic behavior.
x[i+1] = r x[i] (1 - x[i])

The fecundity parameter r is between 0 and 4 and x[0] is chosen to be between 0 and 1. The iterates x settle into a definite pattern. This pattern is constant if k <3. then starts period doubling with a second bifurcation at 3.5, chaos shortly afterwards, and 3-step period around k=3.8.

Web Exercises

Write a program that takes three integer command line parameters a, b, and c and print out the number of distinct values (1, 2, or 3) among a, b, and c.
Write a program that takes five integer command line parameters and prints out the median (the third largest one).
(harder) Now, try to compute the median of 5 elements such that when executed, it never makes more than 6 total comparisons.
Write a program Hurricane.java that that takes the wind speed (in miles per hour) as an integer command line parameter and prints out whether it qualifies as a hurricane, and if so, whether it is a Category 1, 2, 3, 4, or 5 hurricane. Below is a table of the wind speeds according to the Saffir-Simpson scale.

Category Wind Speed (mph)

1 74 - 95

2 96 - 110

3 111 - 130

4 131 - 155

5 155 and above

Category	Wind Speed (mph)
1	74 - 95
2	96 - 110
3	111 - 130
4	131 - 155
5	155 and above

What is wrong with the following code fragment?

double x = -32.2;
boolean isPositive = (x > 0);
if (isPositive = true) System.out.println(x + " is positive");
else                   System.out.println(x + " is not positive");

Answer: It uses the assignment operator = instead of the equality operator ==. A better solution is to write if (isPositive).

Change/add one character so that the following program prints out 20 x's. There are two different solutions.
int i = 0, n = 20; for (i = 0; i
Will the following code fragment compile? If so, what will it do?
int a = 10, b = 18; if (a = b) System.out.println("equal"); else System.out.println("not equal");
Answer: It uses the assignment operator = instead of the equality operator == in the conditional. In Java, the result of this statement is an integer, but the compiler expects a boolean. As a result, the program will not compile. In some languages (notably C), this code fragment will set the variable a to 18 and print equals.
What does the following code fragment do?
if (x > 0); System.out.println("positive");
Answer: always prints positive regardless of the value of x because of the extra semicolon after the if statement.
Boys and girls. A couple beginning a family decides to keep having children until they have at least one of either sex. Estimate the average number of children they will have via simulation. Also estimate the most common outcome (record the frequency counts for 2, 3, and 4 children, and also for 5 and above). Assume that the probability p of having a boy or girl is 1/2.
Boys and girls. Repeat the previous question, but assume the couple keeps having children until they have another child which is of the same sex as the first child. How does your answer change if p is different from 1/2?
Surprisingly, the average number of children is 2 if p = 0 or 1, and 3 for all other values of p. But the most likely value is 2 for all values of p.
Given two positive integers a and b, what result does the following code fragment leave in c
c = 0; while (b > 0) { if (b % 2 == 1) c = c + a; b = b / 2; a = a + a; }
Answer a * b.
Write a program using a loop and four conditionals to print
12 midnight 1am 2am ... 12 noon 1pm ... 11pm

What does the following program print out?

public class Test {
   public static void main(String[] args) {
      if (10 > 5);
      else; {
          System.out.println("Here");
      };
   }
}

Alice tosses a fair coin until she sees two consecutive heads. Bob tosses another fair coin until he sees a head followed by a tail. Write a program to estimate the probability that Alice will make fewer tosses than Bob? Answer: 39/121.
Rewrite Day.java from Creative Exercise XYZ so that it prints out the day of the week as Sunday, Monday, and so forth instead of an integer between 0 and 6. Use a switch statement.
Number-to-English. Write a program to read in a command line integer between -999,999,999 and 999,999,999 and print out the English equivalent. Here is an exhaustive list of words that your program should use: negative, zero, one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand, million . Don't use hundred, when you can use thousand, e.g., use one thousand five hundred instead of fifteen hundred. Reference.
Gymnastics judging. A gymnast's score is determined by a panel of 6 judges who each decide a score between 0.0 and 10.0. The final score is determined by discarding the high and low scores, and averaging the remaining 4. Write a program GymnasticsScorer.java that takes 6 real command line inputs representing the 6 scores and prints out their average, after throwing out the high and low scores.
Quarterback rating. To compare NFL quarterbacks, the NFL devised a the quarterback rating formula based on the quarterbacks number of completed passes (A), pass attempts (B), passing yards (C), touchdown passes (D), and interception (E) as follows:
1. Completion ratio: W = 250/3 * ((A / B) - 0.3).
2. Yards per pass: X = 25/6 * ((C / B) - 3).
3. Touchdown ratio: Y = 1000/3 * (D / B)
4. Interception ratio: Z = 1250/3 * (0.095 - (E / B))
The quarterback rating is computed by summing up the above four quantities, but rounding up or down each value so that it is at least 0 and and at most 475/12. Write a program QuarterbackRating.java that takes five command line inputs A, B, C, D, and E, and prints out the quarterback rating. Use your program to compute Steve Young's 1994 record-setting season (108.9) in which he completed 324 of 461 passes for 3,969 yards, and threw 35 touchdowns and 10 interceptions.
Decimal expansion of rational numbers. Given two integers p and q, the decimal expansion of p/q has an infinitely repeating cycle. For example, 1/33 = 0.03030303.... We use the notation 0.(03) to denote that 03 repeats indefinitely. As another example, 8639/70000 = 0.1234(142857). Write a program DecimalExpansion.java that reads in two command line integers p and q and prints out the decimal expansion of p/q using the above notation. Hint: use Floyd's rule.
Friday the 13th. What is the maximum number of consecutive days in which no Friday the 13th occurs? Hint: The Gregorian calendar repeats itself every 400 years (146097 days) so you only need to worry about a 400 year interval.
Answer: 426 (e.g., from 8/13/1999 to 10/13/2000).
January 1. Is January 1 more likely to fall on a Saturday or Sunday? Write a program to determine the number of times each occurs in a 400 year interval.
Answer: Sunday (58 times) is more likely than Saturday (56 times).
What does the following code fragment print out?
for (int i = 0; i
What does the following code fragment print out?
for (int i = 0; i

Determine what value gets printed out without using a computer. Choose the correct answer from 0, 100, 101, 517, or 1000.

int cnt = 0;
for (int i = 0; i <10; i++) for (int j=0; j < 10; j++) for (int k=0; k < 10; k++) if (2*i + j>= 3*k)
            cnt++;
System.out.println(cnt);

Rewrite CarLoan.java from Creative Exercise XYZ so that it properly handles an interest rate of 0% and avoids dividing by 0.
Write the shortest Java program you can that reads in an integer N from the command line and print true if (1 + 2 + ... + N) ² is equal to (1³ + 2³ + ... + N³).
Answer: always print true.
Modify Sqrt.java so that it reports an error if the user enters a negative number and works properly if the user enters zero.
What happens if we initialize t to -x instead of x in program Sqrt.java?
Sample standard deviation of uniform distribution. Modify Exercise 8 so that it prints out the sample standard deviation in addition to the average.
Sample standard deviation of normal distribution. that takes an integer N as a command line argument and uses Web Exercise 1 from Section 2.2 to print N standard normal random variables, and their average value, and sample standard deviation.
Thue-Morse sequence. Write a program ThueMorse.java that reads in a command line integer N and prints the Thue-Morse sequence of order N. The first few strings are 0, 01, 0110, 01101001. Each successive string is obtained by flipping all of the bits of the previous string and concatenating the result to the end of the previous string. The sequence has many amazing properties. For example, it is a binary sequence that is cube-free: it does not contain 000, 111, 010101, or sss where s is any string. It is self-similar: if you delete every other bit, you get another Thue-Morse sequence. It arises in diverse areas of mathematics as well as chess, graphic design, weaving patterns, and music composition.
Program Binary.java prints the binary representation of a decimal number N by casting out powers of 2. Write an alternate version Program Binary2.java that is based on the following method: Write 1 if N is odd, 0 if N is even. Divide N by 2, throwing away the remainder. Repeat until N = 0 and read the answer backwards. Use % to determine whether or not N is even, and use string concatenation to form the answer in reverse order.
What does the following code fragment do?
int digits = 0; do { digits++; n = n / 10; } while (n > 0);
Answer the number of bits in the binary representation of a natural number n. We use a do-while loop so that code output 1 if n = 0.
Write a program NPerLine.java that takes a command line parameter N and prints the integers from 10 to 99 with N integers per line.
Modify NPerLine.java so that it prints out the integers from 1 to 1000 with N integers per line. Make the integers line up by printing the right number of spaces before an integer (e.g., three for 1-9, two for 10-99, and one for 100-999).
Suppose a, b, and c are random number uniformly distributed between 0 and 1. What is the probability that a, b, and c form the side length of some triangle? Hint: they will form a triangle if and only if the sum of every two values is larger than the third.
Repeat the previous question, but calculate the probability that the resulting triangle is obtuse, given that the three numbers for a triangle. Hint: the three lengths will form an obtuse triangle if and only if (i) the sum of every two values is larger than the third and (ii) the sum of the squares of every two side lengths is greater than or equal to the square of the third.
Answer.

What is the value of s after executing the following code?

int M = 987654321;
String s = "";
while (M != 0) {
   int digit = M % 10;
   s = s + digit;
   M = M / 10;
}

What is the value of i after the following confusing code is executed?
int i = 10; i = i++; i = ++i; i = i++ + ++i;
Moral: don't write code like this.
Formatted ISBN number. Write a program ISBN2.java that reads in a 9 digit integer from a command line parameter, computes the check digit, and prints out the fully formatted ISBN number, e.g, 0-201-31452-5.
UPC codes. The Universal Product Code (UPC) is a 12 digit code that uniquely specifies a product. The least significant digit d₁(rightmost one) is a check digit which is the uniquely determined by making the following expression a multiple of 10:
(d₁ + d₃ + d₅ + d₇ + d₉ + d₁₁) + 3 (d₂ + d₄ + d₆ + d₈ + d₁₀ + d₁₂)

As an example, the check digit corresponding to 0-48500-00102 (Tropicana Pure Premium Orange Juice) is 8 since
(8 + 0 + 0 + 0 + 5 + 4) + 3 (2 + 1 + 0 + 0 + 8 + 0) = 50

and 50 is a multiple of 10. Write a program that reads in a 11 digit integer from a command line parameter, computes the check digit, and prints out the the full UPC. Hint: use a variable of type long to store the 11 digit number.
Write a program that reads in the wind speed (in knots) as a command line argument and prints out its force according to the Beaufort scale. Use a switch statement.
Thai kickboxing. Write a program that reads in the weight of a Thai kickboxer (in pounds) as a command line argument and prints out their weight class. Use a switch statement.
Making change. Write a program that reads in a command line integer N (number of pennies) and prints out the best way (fewest number of coins) to make change using US coins (quarters, dimes, nickels, and pennies only). For example, if N = 73 then print out
2 quarters 2 dimes 3 pennies
Hint: use the greedy algorithm. That is, dispense as many quarters as possible, then dimes, then nickels, and finally pennies.
Write a program Triangle.java that takes a command line parameter N and prints an N-by-N triangular pattern like the one below.
* * * * * * . * * * * * . . * * * * . . . * * * . . . . * * . . . . . *
Write a program Ex.java that takes a command line parameter N and prints an X like the one below, where each piece of the X consists of 3 asterisks.
* . . . . . * . * . . . * . . . * . * . . . . . * . . . . . * . * . . . * . . . * . * . . . . . *
Write a program BowTie.java that takes a command line parameter N and prints a (2N + 1)-by-(2N + 1) bowtie like the one below. Use two for loops and one if-else statement.
* . . . . . * * * . . . * * * * * . * * * * * * * * * * * * * . * * * * * . . . * * * . . . . . *

What does the program Circle.java print out when N = 5?

for (int i = -N; i <= n; i++) { for (int j=-N; j <=N; j++) { if (i*i + j*j <=N*N) system.out.print("* ");" else system.out.print(". ");" } system.out.println(); }

Seasons. Write a program Season.java that takes two command line integers M and D and prints the season corresponding to month M (1 = January, 12 = December) and day D in the northern hemisphere. Use the following table

SEASON FROM TO

Spring March 21 June 20

Summer June 21 September 22

Fall September 23 December 21

Winter December 21 March 20

SEASON	FROM	TO
Spring	March 21	June 20
Summer	June 21	September 22
Fall	September 23	December 21
Winter	December 21	March 20

Zodiac signs. Write a program Zodiac.java that takes two command line integers M and D and prints the Zodiac sign corresponding to month M (1 = January, 12 = December) and day D. Use the following table

SIGN	FROM	TO
Capricorn	December 22	January 19
Aquarius	January 20	February 17
Pisces	February 18	March 19
Aries	March 20	April 19
Taurus	April 20	May 20
Gemini	May 21	June 20
Cancer	June 21	July 22
Leo	July 23	August 22
Virgo	August 23	September 22
Libra	September 23	October 22
Scorpio	October 23	November 21
Sagittarius	November 22	December 21

Euler's sum of powers conjecture. In 1769 Euler generalized Fermat's Last Theorem and conjectured that it is impossible to find three 4th powers whose sum is a 4th power, or four 5th powers whose sum is a 5th power, etc. The conjecture was disproved in 1966 by exhaustive computer search. Disprove the conjecture by finding positive integers a, b, c, d, and e such that a⁵ + b⁵ + c⁵ + d⁵= e⁵. Write a program Euler.java that reads in a command line parameter N and exhaustively searches for all such solutions with a, b, c, d, and e less than or equal to N. No counterexamples are known for powers greater than 5, but you can join EulerNet, a distributed computing effort to find a counterexample for sixth powers.
Blackjack. Write a program Blackjack.java that takes three command line integers x, y, and z representing your two blackjack cards x and y, and the dealers face-up card z, and prints out the "standard strategy" for a 6 card deck in Atlantic city. Assume that x, y, and z are integers between 1 and 10, representing an ace through a face card. Report whether the player should hit, stand, or split according to these strategy tables. (When you learn about arrays, you will encounter an alternate strategy that does not involve as many if-else statements).
Blackjack with doubling. Modify the previous exercise to allow doubling.
Projectile motion. The following equation gives the trajectory of a ballistic missile as a function of the initial angle theta and windspeed: xxxx. Write a java program to print the (x, y) position of the missile at each time step t. Use trial and error to determine at what angle you should aim the missile if you hope to incinerate a target located 100 miles due east of your current location and at the same elevation. Assume the windspeed is 20 mph due east.
Random walk. Term coined by Hungarian mathematician George Polya in a 1921 paper. Start at 0, go left with probability 1/2, go right with probability 1/2. Reflecting barrier at 0 - if particle hits 0, it must switch direction at next step and return to 1. Absorbing barrier at N - particle stops when it hits state N. Estimate number of steps as a function of N until the particle is absorbed.
Analytical solution: N².
World series. The baseball world series is a best of 7 competition, where the first team to win four games wins the World Series. Suppose the stronger team has probability p > 1/2 of winning each game. Write a program to estimate the chance that the weaker teams wins the World Series and to estimate how many games on average it will take.
Consider the equation (9/4)^x = x^(9/4). One solution is 9/4. Can you find another one using Newton's method?
Sorting networks. Write a program Sort3.java with three if statements (and no loops) that reads in three integers A, B, and C from the command line and prints them out in ascending order.
if (A > B) swap A and B if (A > C) swap A and C if (B > C) swap B and C

Oblivious sorting network. Convince yourself that the following code fragment rearranges the integers stored in the variables A, B, C, and D so that A <= b <=C <=D.

if (A > B) { t = A; A = B; B = t; }
if (B > C) { t = B; B = C; C = t; }
if (A > B) { t = A; A = B; B = t; }
if (C > D) { t = C; C = D; D = t; }
if (B > C) { t = B; B = C; C = t; }
if (A > B) { t = A; A = B; B = t; }
if (D > E) { t = D; D = E; E = t; }
if (C > D) { t = C; C = D; D = t; }
if (B > C) { t = B; B = C; C = t; }
if (A > B) { t = A; A = B; B = t; }

Devise a sequence of statements that would sort 5 integers. How many if statements does your program use?

Optimal oblivious sorting networks. Create a program that sorts four integers using only 5 if statements, and one that sorts five integers using only 9 if statements of the for above? How can you check that your program works for all inputs?

if (A > B) swap A and B
if (C > D) swap C and D
if (A > C) swap A and C
if (B > D) swap B and D
if (B > C) swap B and C

if (A > B) swap A and B
if (D > E) swap D and E
if (A > C) swap A and C
if (B > C) swap B and C
if (A > D) swap A and D
if (C > D) swap C and D
if (B > E) swap B and E
if (B > C) swap B and C
if (D > E) swap D and E

This is useful technique for implementing sorting algorithms in hardware.

Challenge problem. Find an optimal sorting network for 6, 7, and 8 inputs, using 12, 16, and 19 if statements of the form in the previous problem, respectively.
Optimal non-oblivious sorting. Write a program that sorts 5 inputs using only 7 comparisons. Hint: First compare the first two numbers, the second two numbers, and the larger of the two groups, and label them so that a Weather balloon. (Etter and Ingber, p. 123) Suppose that h(t) = 0.12t⁴ + 12t³ - 380t² + 4100t + 220 represents the height of a weather balloon at time t (measured in hours) for the first 48 hours after its launch. Create a table of the height at time t for t = 0 to 48. What is its maximum height? Answer: t= 5.
Bug. What does the following code fragment do?

boolean a = false; if (a = true) System.out.println("a is true"); else System.out.println("a is false");

Answer: it prints out a is true. Note that the conditional uses = instead of ==. This means that a is assigned the value true. Now, the conditional evaluates to true. It is better style to use if (a) to avoid the = vs. == bug.
Bug. What does the following code fragment do?

int a = 17, x = 5, y = 12; if (x > y); { a = 13; } System.out.println(a);

Answer: always prints 17 since there is a spurious semicolon after the if statement.
Application of Newton's method. Write a program BohrRadius.java that finds the radii where the probability of finding the electron in the 4s excited state of hydrogen is zero. The probability is given by: (1 - 3r/4 + r²/8 - r³/192)² e^-r/2, where r is the radius in units of the Bohr radius (0.529173E-8 cm). Use Newton's method. By starting Newton's method at different values of r, you can discover all three roots. Hint: use initial values of r= 0, 5, and 13. Challenge: explain what happens if you use an initial value of r = 4 or 12.