2.4. INPUT AND OUTPUT

This section is under construction.

In this section we want to be able to process huge amounts of data. Java supports receiving user input from: command line arguments, the terminal window, a keyboard, a mouse, a file, and the network. In Java you can send output to: the terminal window, a graphical window, a sound card, a file, or the network. We will focus mainly on string processing and image processing.

Command line arguments. Program Random.java reads in a command line argument N and prints out N pseudo-random integers between 0 and 99. Using command line is a useful way to read in a small number of user input values, and we have become accustomed to using this approach. There are two significant limitations of using command line arguments. First, it is unwieldy to enter large amounts of data. Second, the command line parameters must be specified before the program begins execution. Thus, there is no way for the user to interact with the program while it is running.

Standard output. Most popular operating systems (Windows, Mac OS X, Linux) provide a device called standard output that represents an abstract place to send output. Typically standard output is associated with an application known as the Terminal (Mac OS X), Command Prompt (Windows), or Shell (Unix). We'll use the term terminal window to generically refer to this application. The System.out.println method sends its output to standard output. Since by default standard output goes to the terminal window, all of the output in program Random.java appears in the terminal window. The main advantage of having standard output is that we aren't required to associate standard output with the terminal window. Instead, we can redirect standard output to a file for permanent storage. Executing Random with the following command

java Random 100 > output.txt

creates a file named output.txt that contains 100 random values. No output appears in the terminal window. This enables us to save away information for later retrieval. Note that we do not have to change Random.java in any way for this to work; nor do we need to recompile Random.java.

Standard input. Most popular operating systems also provide a device known as standard input that represents an abstract place to receive input. Standard input empowers us to overcome the two main obstacle associated with command line inputs. First, it is easy to deal with large quantities of data. Second, the input data is read in while the program is executing. This enables us to devise interactive programs which prompt the user for information and respond accordingly.

As with standard output, standard input is typically associated with the terminal window. More specifically, the user enters data by typing at the keyboard and the result appears in the terminal window. Java provides support for reading in data from standard input. However, it is a bit cumbersome to use. Instead, we provide a custom-made library called StdIn.java to facilitate reading integers, real numbers, booleans, and strings from standard input. Program Add.java demonstrates how to use this library.

System.out.println("Type the first integer");
int x = StdIn.readInt();
System.out.println("Type the second integer");
int y = StdIn.readInt();
int z = x + y;
System.out.println("Their sum is " + z);

The key statement int x = StdIn.readInt(); waits until the user types in an integer into the terminal window, and then assigns this value to the variable x. As with Integer.parseInt, if the user enters an invalid value, then the program halts and reports an error. To compile Add.java, you must put StdIn.java in the current directory since it is not part of the Java language or library. Now when you compile Add.java with

% javac Add

the system will automatically compile StdIn.java if needed. Below is a sample execution of the program in which the user types in the integers 5 and 33.

% java Add
Type the first integer
5
Type the second integer
33
Their sum is 38

The table below summarizes all of the available operations with the StdIn library.

COMMAND	RETURN TYPE	PURPOSE
`isEmpty`	`boolean`	test if the input stream is empty
`readBoolean`	`boolean`	read in `yes`, `1`, or `true` for true, `no`, `0`, or `false` for false.
`readInt`	`int`	read in an integer
`readLong`	`long`	read in a long integer
`readDouble`	`double`	read in a double precision real number
`readFloat`	`float`	read in a single precision real number
`readString`	`String`	read in a string

Average and standard deviation. Now we consider a more realistic application of the library StdIn.java. Program Average.java reads in a sequence of real numbers from standard input and print their average μ and standard deviation σ to standard output. The standard deviation of the values x₁, x₂, ..., x_n, is given by the following formulae:

The key data input loop below illustrates two important methods in the StdIn library. First, to read in a real number from standard input, we use StdIn.readDouble. Second, since we don't know how many input values the user will enter, we repeatedly call the method StdIn.isEmpty, which is true if there is no more data to process, and false otherwise.

while (!StdIn.isEmpty()) {
   double x = StdIn.readDouble();
   n++;
   sum  = sum  + x;
   sum2 = sum2 + x*x;
}

When the above loop terminates, n contains the number of data values read in, sum contains the sum of all of the values, and sum2 contains the sum of the squares of all the values. From these quantities (and the formulae above), we can readily compute the average and standard deviation.

The user enters data by typing at the keyboard, and signifies the end of the input with an operating system specific value. On Windows use <Return> <Ctrl-z>; on Mac OS X, Linux and Unix, use <Return> <Ctrl-d>.

% java Average
10.0 5.0 6.0
3.0 7.0 32.0
<Ctrl-d>
Number  = 6
Average = 10.5
Standard deviation = 9.844626283748239

Note that StdIn treats all whitespace equally: it does not matter whether we enter the six numbers on the same line or spread them out over several lines. Caveat to the reader: this textbook formula for computing the standard deviation is numerically unstable and should not be used for serious applications. See Section XYZ to learn why this is bad and how to fix it. (Or replace this example to use integers, and warn about overflow.)

Interactive user input. Another prime reason to use standard input (instead of command line input) is for interactive user input. Program TwentyQuestions.java prompts the user to think of an integer between zero and one million and then asks the user to respond with yes or no to statements of the form My number is less than or equal to x? for various values of x until the program can deduce the chosen integer. The program is adaptive in the sense that the program asks different questions depending on each response from the user. We use an important algorithmic strategy known as binary search to deduce the answer in at most 20 questions. We maintain an interval [lo, hi] in which we know the chosen integer lies. At each step, we take the midpoint mid = (lo + hi) / 2 and ask the user if their number is less than or equal to it. This eliminates roughly half of the remaining possibilities and we adjust the interval to [lo, mid] or [mid + 1, hi] accordingly. Since 2²⁰ > 1,000,000, we are ensured of finding the correct integer after 20 questions. The user responds to the questions by typing either yes or no. We use the library method readBoolean in StdIn to read in the user's response. This method returns false if the user enters 0, false, or no, and it returns true if the user types 1, true, or yes.

Character input. The library StdIn is designed to read in input values (integers, real numbers, or strings), separated by whitespace. In text processing applications, we often want to read in the input on a character-by-character basis, including all whitespace characters. We plan to incorporate reading in data one character at a time and one line at a time, but are lazily waiting until Java 1.5, which makes this task much easier. In the meantime you can use CharStdIn.java As a simple example of how to use it, the following code fragment counts the number of characters n entered on standard input.

int n = 0;
while (!CharStdIn.isEmpty()) {
   char c = CharStdIn.readChar();
   n++;
}

Such a program is particularly useful when used in conjunction with redirecting standard input. The following command prints out the number of characters in a file named human-genome.txt.

% java Count

Connecting two programs. Most common operating systems include a mechanism called piping to connect two different programs. As an example, we can make the output of Random.java (a user-specified number of random numbers) be the input of Average.java with the following command.

% java Random 1000 | java Average
Number  = 100000
Average = 49.34004
Standard deviation = 28.831414686039942

Note that the piping symbol | is the same one on your keyboard that you use with the boolean operator ||.

Another useful application of piping is to connect your Java program with a program built in to the operating system. The program more is included on most operating systems. It reads data from standard input and displays it to standard output one screenful at a time. This is useful when you are debugging a program that produces alot of output (possibly because its in an infinite loop), but the output whizzes by the screen too fast for you to observe it. In this case, you can use the following command to show the 1,000 lines of output, one screenful at a time.

% java Random 1000 | more

2D graphics. We have seen that standard output is a very useful abstraction to represent a generic text output stream. Its flexibility enables us to send the output of a program to the terminal window or a file without having to edit or re-compile the program. We want the same type of abstraction for graphics output that we have for text output. That is, we would like to write a Java program to produce a picture that we can display on the screen or save to file. At the same time, we want creating pictures to be as easy as reading text data with StdIn.

Program StdDraw.java is a version that can draw graphics in a window or save the output to a JPEG or PNG file. Requires the helper program Draw.java.

In this book, we will use our StdDraw library to produce static and animated graphics. It simulates the behavior of a turtle moving in a two dimensional space. The turtle has a pen strapped to its back, and can draw while it moves. StdDraw.java is a rather complicated program, so do not worry about the details of its implementation yet. We will come back to it in Section XYZ. For now, we will focus on using it to plot graphics. We will introduce the drawing commands gradually, as our programs need them.

As our first example, program Plot.java reads in (x, y) values from standard input and plots them to the screen. We first specify the dimensions (in pixels) of the graphics window using the method StdDraw.create. In this plotting application, we expect all x and y coordinates to be real numbers between 0 and 512 so we specify a 512-by-512 drawing canvas. The method StdDraw.go(x, y) instructs the turtle to move to a particular location, specified by its x and y coordinates. Now, the turtle is hovering over that location. The method StdDraw.spot(d) instructs the turtle to drop a circular spot of ink of diameter d, centered on the current location. The method StdDraw.show displays the results to the screen.

StdDraw.create(512, 512);
while (!StdIn.isEmpty()) {
   double x = StdIn.readDouble();
   double y = StdIn.readDouble();
   StdDraw.go(x, y);
   StdDraw.spot(3);
}
StdDraw.show();

In order to use the graphics library, put a copy of StdDraw.java and Draw.java in your working directory. Since Plot.java uses the standard input library too, don't forget to include a copy of StdIn.java in your working directory too. Then, compile your program as usual.

% javac Plot.java

2D random walk.

Program RandomWalk.java simulates a 2D random walk and animate the results. Start at the center of a 2N-by-2N grid. The current location is displayed in blue; the trail in white.

Chaos game.

Program Chaos.java plays the chaos game on a triangle: Start at one of the vertices of an equilateral triangle. Then pick one of the three vertices at random and move halfway from the current point to that vertex. Draw each point that you visit. What pattern emerges? The images below represent snapshots of the chaos game after 1,000, 10,000, and 100,000 steps. You might recognize the figure as the Sierpinski triangle.

Bouncing balls. Program BouncingBall.java implements a ball moving in the 512-by-512 box. The balls bounce off the walls. We apply a standard graphics technique to create the illusion of movement: draw the object, calculate its new position, clear the screen, and repeat. We achieve this using StdDraw.pause and StdDraw.clear. The first command pauses for a specified number of milliseconds (allowing the turtle to rest and reload its ink cartridge); the second command clears the screen to the default color (or a user-specified color).

More graphics commands. The examples above illustrates how to use some of the standard graphics commands. The table below summarizes most of the available commands.

COMMAND	ARGUMENTS	ACTION
`create`	`int w` `int h`	Specifies the dimensions of the drawing canvas in pixels. Typical values for `w` and `h` are 512 and 512.
`penUp`		Lift the pen up.
`penDown`		Put the pen down.
`fillOn`		Set the fill mode to on.
`fillOff`		Set the fill mode to off.
`go`	`double x` `double y`	Make the current location (x, y). If the pen is down, draw the line from the old location to the current location. If the pen is up, don't draw anything.
`spot`		Draws one pixel at the current location in the current foreground color.
`spot`	`double d`	Draws a circular spot of diameter d, centered on the current location, using the current foreground color. Fill in the circle according to the fill mode.
`spot`	`double w` `double h`	Draws a rectangular w-by-h spot, centered on the current location, using the current foreground color. Fill in the rectangle according to the fill mode.
`spot`	`String s`	Draws a JPEG, GIF, or PNG image, centered on the current location. The image file must be in the current directory.
`spot`	`String s` `int w` `int h`	Draws a JPEG, GIF, or PNG image, scaled to a w-by-h rectangle, centered on the current location, The image file must be in the current directory.
`play`	`String s`	Plays a WAV, MIDI, or AU sound file. The sound file must be in the current directory.
`clear`		Clears the screen to the current background color. Useful in animations.
`setColor`	`Color c`	Sets the foreground color to c.
`setColorRGB`	`int r int g int b`	Sets the background color to the RGB color (r, g, b), where r, g, and b are integers between 0 and 255.
`setColorHSB`	`int h` `int s` `int b`	Sets the background color to the HSB color (h, s, b), where h, s, and b are integers between 0 and 255.
`clear`	`Color c`	Sets the background color to c and clears the screen using this color. Typical values are `Color.black` and `Color.blue`. Here is more information on using colors in Java.
`pause`	`int t`	Pause for t milliseconds. Useful in animations.
`rotate`	`double d`	Rotate the orientation d degrees counterclockwise. All subsequent `goForward` commands will be with respect to this orientation. Any images plotted using `StdDraw.spot` will also be rotated accordingly.
`goForward`	`double s`	Go forward in the current direction s steps, drawing the line from the current location to the new location if the pen is down.
`write`	`String s`	Write the text string s, centered on the current location.
`show`		Display the image on the screen.
`save`	`String s`	Save the image as a JPEG, GIF, or PNG according to the extension of the filename s.
`setScale`	`double xmin` `double ymin` `double xmax` `double ymax`	Rescale the coordinates so that the window goes from (xmin, ymin) to (xmax, ymax).

Creating animated GIFs. Currently our graphics library does not support saving animated file formats like MPEG, animated GIF, or AVI. However, with an external utility (e.g., ImageMagick) the process is not difficult, and we have used it to create some of the animations on this booksite. The idea is to use StdDraw.save to save a sequence of PNG files named frame100.png, frame101.png, frame102.png, and so on. Assuming ImageMagick is installed (Unix, Linux, OS X, and Windows are all supported) you can use the command

convert -delay 100 frame*.png animation.gif

The convert program stitches together the frames (in alphabetical order) and displays them every 100 miliseconds (one second). Here is an animated GIF created using this process. It is a visualization of a process known as percolation. See Section 9.8.

Swing GUI. A graphical user interface (GUI) is.... Swing is Java's built-in library of GUI widgets. It includes primitives for creating buttons, menus, scrollbars, and many other common graphical components that everyday applications (browser, email client, word processor) use. The text editor JEdit that you have been using to write your programs is written in Java. We will defer interactive graphics until later, but just to give you an idea of what is possible, GUI.java is a bare-bones Java program that contains a clickable button. Each operating system displays the program using its own look-and-feel to blend in with native applications. Below is the same program under Windows XP, Windows NT, and Mac OS X.

Q + A

Q. Can I re-read data from standard input.

A. No. You only get one shot.

Q. How does the library StdIn.isEmpty know when there is no more data available on standard input?

A. If standard input is redirected from a file, then it's when you reach the end of the data in the file. However, when you are typing information in the terminal window, you must rely on an operating system specific sequence of keystrokes. On Windows use <Return> <Ctrl-z>; on Mac OS X, Linux and Unix, use <Return> <Ctrl-d>.

Q. What happens if my program attempts to read data from standard input after it is exhausted?

A. You will get the following error

java.lang.RuntimeException: Tried to read from empty stdin

Use StdIn.isEmpty to check whether there is more input available.

Q. What is the symbol for the end of a line?

A. Different operating systems use different symbols. On Unix systems, the newline character is '\n', on Windows each line is terminated by a string of two characters "\r\n", on Macs each line is terminated by the string "\n\r". When writing a program, you should avoid using operating system specific features or else it might not work as expected on other systems. Use System.out.println() to print a new line, or the following to determine the sequence of characters that represents a new line.

String NEWLINE = System.getProperty("line.separator");

Q. Which of the following is more efficient?

String s;
while (!StdIn.isEmpty()) {        while (!StdIn.isEmpty()) {
    s = StdIn.readString();           String s = StdIn.readString();
    ...                               ...
}                                 }

A. No difference in terms of efficiency. The second is better style because it limits the visibility of the variable s. We'll talk more about scope in Section 2.6.

Q. How do I create colors for use with the graphics library?

A. Here's a primer on using colors in Java.

Q. What are the main differences of the PNG, JPEG, and PostScript graphics formats?

A. The graphics on most web pages are in PNG, GIF, or JPEG format. All three formats are raster-based - they store the set of pixels and color gradations needed to represent a picture. PNG and GIF are ideal for displaying figures with straight lines and geometric figures, while JPEG is best suited for photographs. PostScript is a vector-based format. For example, it represents a circle as a geometric object instead of a collection of thousands of pixels. The quality does not degrade if you enlarge or shrink it. For this reason, most printers use PostScript to print documents and graphics.

Q. What does the error message Exception in thread "main" java.lang.NoClassDefFoundError: StdIn mean?

A. You probably forgot to put StdIn.java in your current working directory and compile it.

Q. How can I run a program with graphical output remotely?

A. If you want to display the image, you will need an X server (e.g., Exceed for Windows or XFree86 for OS X). If you aren't interested in seeing the output on the screen (but instead want to save the image to a file), run your application with with java -Djava.awt.headless=true.

Lessons

Use the command line to read in parameters, and use standard input to read in large quantities of data.
Use our graphics library to draw pictures to the screen.

Exercises

Write a program Sum5.java that reads in five integers from standard input and prints out their sum.
Write a program MaxMin.java that reads in integers (as many as the user enters) from standard input and prints out the maximum and minimum values read in.
Write a program DeleteX.java that reads in text from standard input and deletes all occurrences of the letter X. To filter a file and remove all X's, run your program with the following command:
% java DeleteX output.txt
Write a program ThreeLargest.java that reads integers from standard input and prints out the three largest inputs.
Write a program GeometricMean.java that reads in positive real numbers from standard input and prints out their geometric mean. The geometric mean of N positive numbers x₁, x₂, ..., x_N is (x₁ * x₂ * ... * x_N)^1/N. Hint: consider taking logs to avoid overflow.
Write a program HarmonicMean.java that reads in positive real numbers from standard input and prints out their harmonic mean. The harmonic mean of N positive numbers x₁, x₂, ..., x_N is (1/x₁ + 1/x₂ + ... + 1/x_N) / (1 / N).
Write a program Pnorm.java that takes a command line parameter p, reads in real numbers from standard input, and prints out their p-norm. The p-norm norm of a vector (x₁, ..., x_N) is defined to be the pth root of (|x₁|^p + |x₂|^p + ... + |x_N|^p).

Consider the following Java program.

public class Mystery {
   public static void main(String[] args) {
      int i = StdIn.readInt();
      int j = StdIn.readInt();
      System.out.println((i-1));
      System.out.println((j*i));
   }
}

Suppose that the file input.txt contains

5 1

What does the following command do?

java Mystery

Repeat the previous exercise but use the following command instead
java Mystery

Consider the following Java program.

public class Mystery {
   public static void main(String[] args) {
      int i = StdIn.readInt();
      int j = StdIn.readInt();
      int k = i + j;
      System.out.println(j);
      System.out.println(k);
   }
}

Suppose that the file input.txt contains the integers 1 and 1. What does the following command do?

java Mystery

Consider the Java program Ruler.java.

public class Ruler {
   public static void main(String[] args) {
      int n = StdIn.readInt();
      String s = StdIn.readString();
      System.out.println((n+1) + " " + s + (n+1)  + s);
   }
}

Suppose that the file input.txt contains the integers 1 and 1. What does the following command do?

java Ruler

Consider the Java program Dragon.java.

public class Dragon {
   public static void main(String[] args) {
      String dragon = StdIn.readString();
      String nogard = StdIn.readString();
      System.out.print(dragon + "L" + nogard);
      System.out.print(" ");
      System.out.print(dragon + "R" + nogard);
      System.out.println();
   }
}

Suppose that the file input.txt contains the strings F and F. What does the following command do?

java Dragon

Write a program TenPerLine.java that takes a sequence of integers between 0 and 99 and prints them nicely 10 per line. Pipe the output of java Random N through java TenPerLine to get N integers between 0 and 99, printed 10 per line.
Modify Add.java so that it re-asks the user to enter two positive integers if the user types in a non-positive integer.
Modify TwentyQuestions.java so that it re-asks the user to enter a response if the user types in something other than true or false. Hint: add a do-while loop within the main loop.
Write a program LowerCase.java that reads in a text from standard input and prints it back out to standard output, replacing each uppercase letter with the corresponding lowercase letter. Use Character.toLowerCase(c) to convert the character c to lowercase.
Nonagram. Write a program to plot a nonagram.
Star polygons. Write a program StarPolygon.java that takes two command line inputs p and q, and plots the {p/q}-star polygon.
Complete graph. Write a program to plot that takes an integer N, plots an N-gon, where each vertex lies on a circle of radius 256. Then draw a gray line connecting each pair of vertices.
Necker cube. Write a program NeckerCube.java to plot a Necker cube.
What happens if you move the StdDraw.clear(Color.black) command to before the beginning of the while loop in BouncingBall.java? Answer: try it and observe a nice woven 3d pattern with the given starting velocity and position.
What happens if you change the parameter of StdDraw.pause to 0 or 1000 in BouncingBall.java?
What happens if you move the command StdDraw.play outside of the if statement to the body of the loop in BouncingBall.java?
Modify BouncingBall.java so that the earth rotates 20 degrees after each frame. Name your program RotatingBall.java.
Write a program to plot a circular ring of width 10 like the one below using two calls to StdDraw.spot.
Write a program to plot a circular ring of width 10 like the one below using a nested for loop and many calls to StdDraw.spot(0).
Write a program to plot the Olympic rings.
Write a program to plot 128 filled circles, centered on (256, 256), of various diameters and colors like the one below.

Creative Exercises

Word count. Write a program WordCount.java that reads in text from standard input and prints out the number of words in the text. For our purposes, a word is a sequence of non-whitespace characters, surrounded by whitespace. Use the library StdIn.
Word and line count. Modify WordCount.java so that reads in text from standard input and prints out the number of characters, words, and lines in the text. Use the library CharStdIn.
Longest consecutive streak. Write a program Repeats.java that reads in a sequence of integers and prints out the integer that appears the most times in-a-row. For example, if the input is 1 2 2 1 5 1 1 7 7 7 7 1 1 then your program should print out the integer 7.
Centroid. Given the positions and masses of N object, compute their center-of-mass or centroid. The centroid is defined to be the average position of the N objects, weighted by mass. That is if the positions and masses are given by (x_i, y_i, m_i), then the center of mass (x, y, m) is given by:
m = m₁ + m₂ + ... + m_N x = (m₁x₁ + ... + m_nx_N) / m x = (m₁y₁ + ... + m_ny_N) / m
Write a program CenterOfMass.java that reads in a sequence of positions and masses (x_i, y_i, m_i) from standard input and prints out their center of mass (x, y, m). Hint: model your program after Average.java.
Signal analysis. Write a program SignalAnalyzer.java that reads in a sequence of real numbers between -1 and 1 and prints out their average magnitude, average power, and the number of zero crossings. The average magnitude is the average of the absolute values of the data values. The average power is the value of the squares of the data values. The number of zero crossings is the number of times a data value transitions from a strictly negative number to a strictly positive number, or vice versa. These three statistics are widely used to analyze digital signals.
Rainfall problem. Write a program Rainfall.java that reads in nonnegative integers (representing rainfall) one at a time until 999999 is entered, and then prints out the average of value (not including 999999).
Missing integer. Write a program that reads in N-1 distinct integers between 1 and N and determines the missing value.
Closest points. Write a program to read in three command line arguments x, y, z, and a sequence of points (x_i, y_i, z_i) from standard input, and print out the point closest to (x, y, z). Recall that the square of the distance between (x, y, z) and (x_i, y_i, z_i) is (x - x_i)² + (y - y_i)² + (z - z_i)².
Optimization: it is possible to do without using Math.sqrt.
Remove duplicates. Write a program Duplicates.java that reads in a sequence of integers and prints back out the integers, except that it removes repeated values if they appear consecutively. For example, if the input is 1 2 2 1 5 1 1 7 7 7 7 1 1, your program should print out 1 2 1 5 1 7 1.
Run length encoding. Write a program RunLengthEncoder.java that encodes a binary input using run length encoding. Write a program RunLengthDecoder.java that decodes a run length encoded message.
Print a random word. Read a list of N words from standard input, where N is unknown ahead of time, and print out one of the N words uniformly at random. Do not store the word list. Instead, use Knuth's method: when reading in the ith word, select it with probability 1/i to be the selected word, replacing the previous champion. Print out the word that survives after reading in all of the data.
Caesar cipher. Julius Caesar sent secret messages to Cicero using a scheme that is now known as a Caesar cipher. Each letter is replaced by the letter k positions ahead of it in the alphabet (and you wrap around if needed). The table below gives the Caesar cipher when k = 3.
Original: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Caesar: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
For example the message "VENI, VIDI, VICI" is converted to "YHQL, YLGL, YLFL". Write a program Caesar.java that takes a command line parameter k and applies a Caesar cipher with shift = k to a sequence of letters read from standard input. If a letter is not an uppercase letter, simply print it back out.
Caesar cipher decoding. How would you decode a message encrypted using a Caesar cipher? Hint: you should not need to write any more code.
Parity check. A Boolean matrix has the parity property when each row and each column has an even sum. This is a simple type of error-correcting code because if one bit is corrupted in transmission (bit is flipped from 0 to 1 or from 1 to 0) it can be detected and repaired. Here's a 4 x 4 input file which has the parity property:
1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1
Write a program ParityCheck.java that takes an integer N as a command line input and reads in an N-by-N Boolean matrix from standard input, and outputs if (i) the matrix has the parity property, or (ii) indicates which single corrupted bit (i, j) can be flipped to restore the parity property, or (iii) indicates that the matrix was corrupted (more than two bits would need to be changed to restore the parity property). Use as little internal storage as possible. Hint: you do not even have to store the matrix!
Takagi's function. Plot Takagi's function: everywhere continuous, nowhere differentiable.
Hitchhiker problem. You are interviewing N candidates for the sole position of American Idol. Every minute you get to see a new candidate, and you have one minute to decide whether or not to declare that person the American Idol. You may not change your mind once you finish interviewing the candidate. Suppose that you can immediately rate each candidate with a single real number between 0 and 1, but of course, you don't know the rating of the candidates not yet seen. Devise a strategy and write a program AmericanIdol that has at least a 25% chance of picking the best candidate (assuming the candidates arrive in random order), reading the 500 data values from standard input. Solution: interview for N/2 minutes and record the rating of the best candidate seen so far. In the next N/2 minutes, pick the first candidate that has a higher rating than the recorded one. Analysis: at least 25% since you will get the best candidate if the second best candidate arrives in the first N/2 minutes, and the best candidate arrives in the final N/2 minutes. This can be improved slightly to 1/e = 0.36788 by using essentially the same strategy, but switching over at time N/e.
Checkerboard. Write a program CheckerBoard.java that takes a command line input N and plots an N-by-N checkerboard. Always color the lower left square red. Draw the squares in red and black. Below is the desired output for N = 5, 10, and 25.
Nested diamonds. Write a program Diamonds.java that takes a command line input N and plots N nested squares and diamonds. Below is the desired output for N = 3, 4, and 5.
Regular polygons. Write a program Polygon.java that takes a command line parameter N and draws a regular N-gon (isosceles triangle when N = 3, square when N = 4, pentagon, when N = 5, etc.) Use StdDraw.rotate to avoid messy trigonometry.
Nested polygons. Write a program Polygons.java that draws nested polygons like the picture below.
Bulging squares. Write a program BulgingSquares.java that draws the following optical illusion from Akiyoshi Kitaoka The center appears to bulge outwards even though all squares are the same size.
Spiraling mice. Suppose that N mice that start on the vertices of a regular polygon with N sides, and they each head toward the nearest other mouse (in counterclockwise direction) until they all meet. Write a program to draw the logarithmic spiral paths that they trace out by drawing nested N-gons, rotated and shrunk as in this animation.
Turtle. Draw a picture of a turtle (perhaps more artistically than the one below).
Spiral. Write a program to draw a spiral like the one below.
Rose. Write a program Rose.java that takes a command line input N and plots an order rose with N petals (if N is odd) or 2N petals (if N is even). Plot the polar coordinates (r, θ) of the function f(θ) = sin(N × θ) for θ ranging from 0 to 360 degrees. Hint: use StdDraw.rotate and StdDraw.goForward to position the turtle and Math.toRadians to convert from degrees into radians before using Math.sin. Below is the desired output for N = 4, 7, and 8.
Globe. Write a program Globe.java that takes a real command line input α and plots a globe-like pattern with parameter α. Plot the polar coordinates (r, θ) of the function f(θ) = cos(α × θ) for θ ranging from 0 to 7200 degrees. Below is the desired output for α = 0.8, 0.9, and 0.95.
Drawing strings. Write a program HelloTurtle.java that takes a string s and an integer N as command line inputs, and writes the string N times at a random location, and in a random color.

Barnsley fern. Write a program Barnsley.java that takes a command line argument N and plots a sequence of N points according to the following rules. Set (x, y) = (0.5, 0). Then update (x, y) to one of the following four quantities according to the probabilities given.

PROBABILITY	NEW X	NEW Y
2%	0.5	0.27y
15%	-0.139x + 0.263y + 0.57	0.246x + 0.224y - 0.036
13%	0.170x - 0.215y + 0.408	0.222x + 0.176y + 0.0893
70%	0.781x + 0.034y + 0.1075	-0.032x + 0.739y + 0.27

The pictures below show the results after 500, 1000, and 10,000 iterations.

Iterated function system. An Iterated function system (IFS) is a general way to produce fractals like the Sierpinski triangle and the Barnsley Fern. Experiment with different affine transformations and produce some interesting pictures. For example, try the following to get trees.

PROB	NEW X	NEW Y
10%	0.05	0.6y
10%	-0.05x	-0.5y 1.0
20%	0.46x - 0.15y	0.39x + 0.38y + 0.6
20%	0.47x - 0.15y	0.17x + 0.42y + 1.1
20%	0.43x + 0.28y	-0.25x + 0.45y + 1.0
20%	0.42x + 0.26y	-0.35x + 0.31y + 0.7

Rotated jokers. Write a program RotatedJokers.java that plots an 3-by-4 grid of the image joker.gif, where each image is rotated 30 degrees from the previous one.
Spirographs. Write a program Spirograph.java to read in three parameters R, r, and a, and animates the resulting spirograph. A spirograph or epicycloid is a curve formed by rolling a circle of radius r around a larger fixed circle or radius R. If the pen offset of the pen point from the center of the rolling circle is (r+a), then the equation of the resulting curve at time t is given by
x(t) = (R+r)*cos(t) - (r+a)*cos(((R+r)/r)*t) y(t) = (R+r)*sin(t) - (r+a)*sin(((R+r)/r)*t)
(Such curves were popularized by Hasbro's game Spirograph which contains discs with gear teeth on the edges. The disks contains small holes so that you could put a pen in it and trace the path.) For a dramatic 3d effect, draw a circular image, e.g., earth.gif instead of a dot, and show it rotating over time. Here's a picture of the resulting spirograph when R = 180, r = 40, and a = 15.
Rotating table. You are seated at a rotating square table (like a lazy Susan), and there are four coins placed in the four corners of the table. Your goal is to flip the coins so that they are either all heads or all tails, at which point a bell rings to notify you that you are done. You may select any two of them, determine their orientation, and (optionally) flip either or both of them over. To make things challenging, you are blindfolded, and the table is spun after each time you select two coins. Write a program RotatingTable.java that initializes the coins to random orientations. Then, it prompts the user to select two positions (1-4), and identifies the orientation of each coin. Next, the user can specify which, if any of the two coins to flip. The process repeats until the user solves the puzzle.
Rotating table solver. Write another program RotatingTableSolver.java to solve the rotating table puzzle. One effective strategy is to choose two coins at random and flip them to heads. However, if you get really unlucky, this could take an arbitrary number of steps. Goal: devise a strategy that always solves the puzzle in at most 5 steps.
Hex. Hex is a two-player board game popularized by John Nash while a graduate student at Princeton University, and later commercialized by Parker Brothers. It is played on a hexagonal grid in the shape of an 11-by-11 diamond. Write a program Hex.java that draws the board.
Clock. Write a program Clock.java that displays an animation of the second, minute, and hour hands of an analog clock. Use the method StdDraw.pause(1000) to update the display roughly once per second. Hint: this may be one of the rare times when you want to use the % operator with a double - it works the way you would probably expect. You can avoid geometry calculations by using StdDraw.rotate.
Projectile motion with drag. Write a program BallisticMotion.java that plots the trajectory of a ball that is shot with velocity v at an angle theta. Account for gravitational and drag forces. Assume that the drag force is proportional to the square of the velocity. Using Newton's equations of motions and the Euler-Cromer method, update the position, velocity, and acceleration according to the following equations:
v = sqrt(vx*vx + vy*vy) ax = - C * v * vx ay = -G - C * v * vy vx = vx + ax * dt vy = vy + ay * dt x = x + vx * dt y = y + vy * dt
Use G = 9.8, C = 0.002, and set the initial velocity to 180 and the angle to 60 degrees.
Oscilloscope. Write a program Oscilloscope.java to simulate the output of an oscilloscope and produce Lissajous patterns. They are named after the French physicist, Jules A. Lissajous, who studied the patterns that arise when two mutually perpendicular periodic disturbances occur simultaneously. Assume that the vertical and horizontal inputs are sinusoidal:
x = A sin (w_xt + φ_x) y = B sin (w_yt + φ_y) A, B = amplitudes w_x, w_y = angular velocity φ_x, φ_Y = phase factors
For example, the first image below has A = B = 1, w_x = 2, w_y = 3, φ_x = 30 degrees, φ_y = 45 degrees. The other two have parameters (1, 1, 2, 3, 20, 45) and (1, 1, 5, 3, 30, 45)
Simple harmonic motion. Repeat the previous exercise, but animate the Lissajous patterns as in this applet. Ex: A = B = w_x = w_y = 1, but at each time t draw 100 (or so) points with φ_x ranging from 0 to 720 degrees, and φ_x ranging from 0 to 1080 degrees.
Bouncing ball with gravity. Modify BouncingBall.java to incorporate gravity in the vertical direction.

Bresenham's line drawing algorithm. To plot a line segment from (x1, y1) to (x2, y2) on a monitor, say 1024-by-1024, you need to make a discrete approximation to the continuous line and determine exactly which pixels to turn on. Bresenham's line drawing algorithm is a clever solution that works when the slope is between 0 and 1 and x1

int dx  = x2 - x1;
int dy  = y2 - y1;
int y   = y1;
int eps = 0;

for (int x = x1; x <= x2; x++) { stddraw.go(x, y); stddraw.spot(0); eps +=dy; if (2*eps>= dx)  {
       y++;
       eps -= dx;
    }
}

Modify Bresenham's algorithm to handle arbitrary line segments.

Web Exercises and Unfinished Exercises

Time series analysis. This problem investigates two methods for forecasting in time series analysis. Moving average or exponential smoothing.
Polar plots. Create any of these polar plots.
Composing a Mozart minuet. In 1787, Wolfgang Amadeus Mozart invented rule of generating Minuets by pasting together 32 random measures. Can we download the archive of MIDI files and play them with Turtle graphics??? Perhaps this goes with arrays or a huge sequence of if-else statements. another resource.