A data structure is a way to organize data in a computer (usually to save time or space). Data structures play an essential role in computer programming—indeed, CHAPTER 4 of this book is devoted to the study of classic data structures of all sorts.

A one-dimensional array (or array) is a data structure that stores a sequence of values, all of the same type. We refer to the components of an array as its elements. We use indexing to refer to the array elements: If we have n elements in an array, we think of the elements as being numbered from 0 to n-1 so that we can unambiguously specify an element with an integer index in this range.

A two-dimensional array is an array of one-dimensional arrays. Whereas the elements of a one-dimensional array are indexed by a single integer, the elements of a two-dimensional array are indexed by a pair of integers: the first index specifies the row, and the second index specifies the column.

Often, when we have a large amount of data to process, we first put all of the data into one or more arrays. Then we use indexing to refer to individual elements and to process the data. We might have exam scores, stock prices, nucleotides in a DNA strand, or characters in a book. Each of these examples involves a large number of values that are all of the same type. We consider such applications when we discuss input/output in SECTION 1.5 and in the case study that is the subject of SECTION 1.6. In this section, we expose the basic properties of arrays by considering examples where our programs first populate arrays with values computed from experimental studies and then process them.

• Declare the array.

• Create the array.

• Initialize the array elements.

To declare an array, you need to specify a name and the type of data it will contain. To create it, you need to specify its length (the number of elements). To initialize it, you need to assign a value to each of its elements. For example, the following code makes an array of n elements, each of type double and initialized to 0.0:

Click here to view code image

double[] a;                    // declare the array
a = new double[n];             // create the array
for (int i = 0; i < n; i++)    // initialize the array
   a[i] = 0.0;

The first statement is the array declaration. It is just like a declaration of a variable of the corresponding primitive type except for the square brackets following the type name, which specify that we are declaring an array. The second statement creates the array; it uses the keyword new to allocate memory to store the specified number of elements. This action is unnecessary for variables of a primitive type, but it is needed for all other types of data in Java (see SECTION 3.1). The for loop assigns the value 0.0 to each of the n array elements. We refer to an array element by putting its index in square brackets after the array name: the code a[i] refers to element i of array a[]. (In the text, we use the notation a[] to indicate that variable a is an array, but we do not use a[] in Java code.)

The obvious advantage of using arrays is to define many variables without explicitly naming them. For example, if you wanted to process eight variables of type double, you could declare them with

Click here to view code image

double a0, a1, a2, a3, a4, a5, a6, a7;

and then refer to them as a0, a1, a2, and so forth. Naming dozens of individual variables in this way is cumbersome and naming millions is untenable. Instead, with arrays, you can declare n variables with the statement double[] a = new double[n] and refer to them as a[0], a[1], a[2], and so forth. Now, it is easy to define dozens or millions of variables. Moreover, since you can use a variable (or other expression computed at run time) as an array index, you can process arbitrarily many elements in a single loop, as we do above. You should think of each array element as an individual variable, which you can use in an expression or as the left-hand side of an assignment statement.

As our first example, we use arrays to represent vectors. We consider vectors in detail in SECTION 3.3; for the moment, think of a vector as a sequence of real numbers. The dot product of two vectors (of the same length) is the sum of the products of their corresponding elements. The dot product of two vectors that are represented as one-dimensional arrays x[] and y[], each of length 3, is the expression x[0]*y[0] + x[1]*y[1] + x[2]*y[2]. More generally, if each array is of length n, then the following code computes their dot product:

double sum = 0.0;
for (int i = 0; i < n; i++)
   sum += x[i]*y[i];

The simplicity of coding such computations makes the use of arrays the natural choice for all kinds of applications.

The table on the facing page has many examples of array-processing code, and we will consider even more examples later in the book, because arrays play a central role in processing data in many applications. Before considering more sophisticated examples, we describe a number of important characteristics of programming with arrays.

double[] a = new double[n];
for (int i = 0; i < n; i++)
   a[i] = Math.random();

for (int i = 0; i < n; i++)
   System.out.println(a[i]);

double max = Double.NEGATIVE_INFINITY;
for (int i = 0; i < n; i++)
   if (a[i] > max) max = a[i];

double sum = 0.0;
for (int i = 0; i < n; i++)
   sum += a[i];
double average = sum / n;

for (int i = 0; i < n/2; i++)
{
   double temp = a[i];
   a[i] = a[n-1-i];
   a[n-i-1] = temp;
}

double[] b = new double[n];
for (int i = 0; i < n; i++)
   b[i] = a[i];

double[] a = new double[n];

The code to the left of the equals sign constitutes the declaration; the code to the right constitutes the creation. The for loop is unnecessary in this case because Java automatically initializes array elements of any primitive type to zero (for numeric types) or false (for the type boolean). Java automatically initializes array elements of type String (and other nonprimitive types) to null, a special value that you will learn about in CHAPTER 3.

Click here to view code image

String[] SUITS = { "Clubs", "Diamonds", "Hearts", "Spades" };

String[] RANKS =
{
   "2", "3", "4", "5", "6", "7", "8", "9", "10",
   "Jack", "Queen", "King", "Ace"
};

Now, we can use the two arrays to print a random card name, such as Queen of Clubs, as follows:

Click here to view code image

int i = (int) (Math.random() * RANKS.length);
int j = (int) (Math.random() * SUITS.length);
System.out.println(RANKS[i] + " of " + SUITS[j]);

This code uses the idiom introduced in SECTION 1.2 to generate random indices and then uses the indices to pick strings out of the two arrays. Whenever the values of all array elements are known (and the length of the array is not too large), it makes sense to use this method of initializing the array—just put all the values in curly braces on the right-hand side of the equals sign in the array declaration. Doing so implies array creation, so the new keyword is not needed.

Click here to view code image

String[] deck = new String[RANKS.length * SUITS.length];
for (int i = 0; i < RANKS.length; i++)
   for (int j = 0; j < SUITS.length; j++)
      deck[SUITS.length*i + j] = RANKS[i] + " of " + SUITS[j];

After this code has been executed, if you were to print the contents of deck[] in order from deck[0] through deck[51], you would get

2 of Clubs
2 of Diamonds
2 of Hearts
2 of Spades
3 of Clubs
3 of Diamonds
...
Ace of Hearts
Ace of Spades

String temp = deck[i];
deck[i] = deck[j];
deck[j] = temp;

For example, if we were to use this code with i equal to 1 and j equal to 4 in the deck[] array of the previous example, it would leave 3 of Clubs in deck[1] and 2 of Diamonds in deck[4]. You can also verify that the code leaves the array unchanged when i and j are equal. So, when we use this code, we are assured that we are perhaps changing the order of the values in the array but not the set of values in the array.

Click here to view code image

int n = deck.length;
for (int i = 0; i < n; i++)
{
   int r = i + (int) (Math.random() * (n-i));
   String temp = deck[i];
   deck[i] = deck[r];
   deck[r] = temp;
}

Proceeding from left to right, we pick a random card from deck[i] through deck[n-1] (each card equally likely) and exchange it with deck[i]. This code is more sophisticated than it might seem: First, we ensure that the cards in the deck after the shuffle are the same as the cards in the deck before the shuffle by using the exchange idiom. Second, we ensure that the shuffle is random by choosing uniformly from the cards not yet chosen.

public class Sample
{
   public static void main(String[] args)
   {  // Print a random sample of m integers
      // from 0 ... n-1 (no duplicates).
      int m = Integer.parseInt(args[0]);
      int n = Integer.parseInt(args[1]);
      int[] perm = new int[n];

      // Initialize perm[].
      for (int j = 0; j < n; j++)
          perm[j] = j;

      // Take sample.
      for (int i = 0; i < m; i++)
      {  // Exchange perm[i] with a random element to its right.
         int r = i + (int) (Math.random() * (n-i));
         int t = perm[r];
         perm[r] = perm[i];
         perm[i] = t;
      }

      // Print sample.
      for (int i = 0; i < m; i++)
         System.out.print(perm[i] + " ");
      System.out.println();
   }
}

  m    | sample size
  n    | range
perm[] | permutation of 0 to n-1

% java Sample 6 16
9 5 13 1 11 8
% java Sample 10 1000
656 488 298 534 811 97 813 156 424 109
% java Sample 20 20
6 12 9 8 13 19 0 2 4 5 18 1 14 16 17 3 7 11 10 15

If the values of r are chosen such that each value in the given range is equally likely, then the elements perm[0] through perm[m-1] are a uniformly random sample at the end of the process (even though some values might move multiple times) because each element in the sample is assigned a value uniformly at random from those values not yet sampled. One important reason to explicitly compute the permutation is that we can use it to print a random sample of any array by using the elements of the permutation as indices into the array. Doing so is often an attractive alternative to actually rearranging the array because it may need to be in order for some other reason (for instance, a company might wish to draw a random sample from a list of customers that is kept in alphabetical order).

To see how this trick works, suppose that we wish to draw a random poker hand from our deck[] array, constructed as just described. We use the code in Sample with n = 52 and m = 5 and replace perm[i] with deck[perm[i]] in the System.out.print() statement (and change it to println()), resulting in output such as the following:

3 of Clubs
Jack of Hearts
6 of Spades
Ace of Clubs
10 of Diamonds

Sampling like this is widely used as the basis for statistical studies in polling, scientific research, and many other applications, whenever we want to draw conclusions about a large population by analyzing a small random sample.

Click here to view code image

double[] harmonic = new double[n];
for (int i = 1; i < n; i++)
   harmonic[i] = harmonic[i-1] + 1.0/i;

Then you can just use the code harmonic[i] to refer to the ith harmonic number. Precomputing values in this way is an example of a space–time tradeoff: by investing in space (to save the values), we save time (since we do not need to recompute them). This method is not effective if we need values for huge n, but it is very effective if we need values for small n many different times.

Click here to view code image

if      (m ==  1) System.out.println("Jan");
else if (m ==  2) System.out.println("Feb");
else if (m ==  3) System.out.println("Mar");
else if (m ==  4) System.out.println("Apr");
else if (m ==  5) System.out.println("May");
else if (m ==  6) System.out.println("Jun");
else if (m ==  7) System.out.println("Jul");
else if (m ==  8) System.out.println("Aug");
else if (m ==  9) System.out.println("Sep");
else if (m == 10) System.out.println("Oct");
else if (m == 11) System.out.println("Nov");
else if (m == 12) System.out.println("Dec");

We could also use a switch statement, but a much more compact alternative is to use an array of strings, consisting of the names of each month:

Click here to view code image

String[] MONTHS =
{
   "", "Jan", "Feb", "Mar", "Apr", "May", "Jun",
       "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"
};
System.out.println(MONTHS[m]);

This technique would be especially useful if you needed to access the name of a month by its number in several different places in your program. Note that we intentionally waste one slot in the array (element 0) to make MONTHS[1] correspond to January, as required.

With these basic definitions and examples out of the way, we can now consider two applications that both address interesting classical problems and illustrate the fundamental importance of arrays in efficient computation. In both cases, the idea of using an expression to index into an array plays a central role and enables a computation that would not otherwise be feasible.

Coupon collecting is no toy problem. For example, scientists often want to know whether a sequence that arises in nature has the same characteristics as a random sequence. If so, that fact might be of interest; if not, further investigation may be warranted to look for patterns that might be of importance. For example, such tests are used by scientists to decide which parts of genomes are worth studying. One effective test for whether a sequence is truly random is the coupon collector test: compare the number of elements that need to be examined before all values are found against the corresponding number for a uniformly random sequence. CouponCollector (PROGRAM 1.4.2) is an example program that simulates this process and illustrates the utility of arrays. It takes a command-line argument n and generates a sequence of random integers between 0 and n-1 using the code (int) (Math.random() * n)—see PROGRAM 1.2.5. Each integer represents a card: for each card, we want to know if we have seen that card before. To maintain that knowledge, we use an array isCollected[], which uses the card as an index; isCollected[i] is true if we have seen a card i and false if we have not. When we get a new card that is represented by the integer r, we check whether we have seen it before by accessing isCollected[r]. The computation consists of keeping count of the number of distinct cards seen and the number of cards generated, and printing the latter when the former reaches n.

As usual, the best way to understand a program is to consider a trace of the values of its variables for a typical run. It is easy to add code to CouponCollector that produces a trace that gives the values of the variables at the end of the while loop. In the accompanying figure, we use F for the value false and T for the value true to make the trace easier to follow. Tracing programs that use large arrays can be a challenge: when you have an array of length n in your program, it represents n variables, so you have to list them all. Tracing programs that use Math.random() also can be a challenge because you get a different trace every time you run the program. Accordingly, we check relationships among variables carefully. Here, note that distinct always is equal to the number of true values in isCollected[].

public class CouponCollector
{
   public static void main(String[] args)
   {
      // Generate random values in [0..n) until finding each one.
      int n = Integer.parseInt(args[0]);
      boolean[] isCollected = new boolean[n];
      int count = 0;
      int distinct = 0;

      while (distinct < n)
      {
         // Generate another coupon.
         int r = (int) (Math.random() * n);
         count++;
         if (!isCollected[r])
         {
            distinct++;
            isCollected[r] = true;
         }
      }  // n distinct coupons found.
      System.out.println(count);
   }
}

       n       | # coupon values (0 to n-1)
isCollected[i] | has coupon i been collected?
     count     | # coupons
   distinct    | # distinct coupons
       r       | random coupon

% java CouponCollector 1000
6583
% java CouponCollector 1000
6477
% java CouponCollector 1000000
12782673

Without arrays, we could not contemplate simulating the coupon collector process for huge n; with arrays, it is easy to do so. We will see many examples of such processes throughout the book.

One approach to counting primes is to use a program like Factors (PROGRAM 1.3.9). Specifically, we could modify the code in Factors to set a boolean variable to true if a given number is prime and false otherwise (instead of printing out factors), then enclose that code in a loop that increments a counter for each prime number. This approach is effective for small n, but becomes too slow as n grows.

PrimeSieve (PROGRAM 1.4.3) takes a command-line integer n and computes the prime count using a technique known as the Sieve of Eratosthenes. The program uses a boolean array isPrime[] to record which integers are prime. The goal is to set isPrime[i] to true if the integer i is prime, and to false otherwise. The sieve works as follows: Initially, set all array elements to true, indicating that no factors of any integer have yet been found. Then, repeat the following steps as long as i <= n/i:

• Find the next smallest integer i for which no factors have been found.

• Leave isPrime[i] as true since i has no smaller factors.

• Set the isPrime[] elements for all multiples of i to false.

When the nested for loop ends, isPrime[i] is true if and only if integer i is prime. With one more pass through the array, we can count the number of primes less than or equal to n.

public class PrimeSieve
{
   public static void main(String[] args)
   {  // Print the number of primes <= n.
      int n = Integer.parseInt(args[0]);
      boolean[] isPrime = new boolean[n+1];
      for (int i = 2; i <= n; i++)
         isPrime[i] = true;

      for (int i = 2; i <= n/i; i++)
      {  if (isPrime[i])
         {  // Mark multiples of i as nonprime.
            for (int j = i; j <= n/i; j++)
               isPrime[i * j] = false;
         }
      }

      // Count the primes.
      int primes = 0;
      for (int i = 2; i <= n; i++)
         if (isPrime[i]) primes++;
      System.out.println(primes);
   }
}

    n      | argument
isPrime[i] | is i prime?
  primes   | prime counter

% java PrimeSieve 25
9
% java PrimeSieve 100
25
% java PrimeSieve 1000000000
50847534

As usual, it is easy to add code to print a trace. For programs such as PrimeSieve, you have to be a bit careful—it contains a nested for-if-for, so you have to pay attention to the curly braces to put the print code in the correct place. Note that we stop when i > n/i, as we did for Factors.

With PrimeSieve, we can compute π(n) for large n, limited primarily by the maximum array length allowed by Java. This is another example of a space–time tradeoff. Programs like PrimeSieve play an important role in helping mathematicians to develop the theory of numbers, which has many important applications.

The mathematical abstraction corresponding to such tables is a matrix; the corresponding Java construct is a two-dimensional array. You are likely to have already encountered many applications of matrices and two-dimensional arrays, and you will certainly encounter many others in science, engineering, and computing applications, as we will demonstrate with examples throughout this book. As with vectors and one-dimensional arrays, many of the most important applications involve processing large amounts of data, and we defer considering those applications until we introduce input and output, in SECTION 1.5.

Extending Java array constructs to handle two-dimensional arrays is straightforward. To refer to the element in row i and column j of a two-dimensional array a[][], we use the notation a[i][j]; to declare a two-dimensional array, we add another pair of square brackets; and to create the array, we specify the number of rows followed by the number of columns after the type name (both within square brackets), as follows:

Click here to view code image

double[][] a = new double[m][n];

We refer to such an array as an m-by-n array. By convention, the first dimension is the number of rows and the second is the number of columns. As with one-dimensional arrays, Java initializes all elements in arrays of numbers to zero and in boolean arrays to false.

Click here to view code image

double[][] a;
a = new double[m][n];
for (int i = 0; i < m; i++)
{  // Initialize the ith row.
   for (int j = 0; j < n; j++)
      a[i][j] = 0.0;
}

This code is superfluous when initializing the elements of a two-dimensional array to zero, but the nested for loops are needed to initialize the elements to some other value(s). As you will see, this code is a model for the code that we use to access or modify each element of a two-dimensional array.

Click here to view code image

for (int i = 0; i < m; i++)
{  // Print the ith row.
   for (int j = 0; j < n; j++)
      System.out.print(a[i][j] + " ");
   System.out.println();
}

If desired, we could add code to embellish the output with row and column indices (see EXERCISE 1.4.6). Java programmers typically tabulate two-dimensional arrays with row indices running top to bottom from 0 and column indices running left to right from 0.

Click here to view code image

double[][] a =
{
   { 99.0, 85.0, 98.0,  0.0 },
   { 98.0, 57.0, 79.0,  0.0 },
   { 92.0, 77.0, 74.0,  0.0 },
   { 94.0, 62.0, 81.0,  0.0 },
   { 99.0, 94.0, 92.0,  0.0 },
   { 80.0, 76.5, 67.0,  0.0 },
   { 76.0, 58.5, 90.5,  0.0 },
   { 92.0, 66.0, 91.0,  0.0 },
   { 97.0, 70.5, 66.5,  0.0 },
   { 89.0, 89.5, 81.0,  0.0 },
   {  0.0,  0.0,  0.0,  0.0 }
};

Compile-time initialization of a of an 11-by-4 double array

Click here to view code image

double[][] c = new double[n][n];
for (int i = 0; i < n; i++)
   for (int j = 0; j < n; j++)
      c[i][j] = a[i][j] + b[i][j];

Similarly, you can multiply two matrices. You may have learned matrix multiplication, but if you do not recall or are not familiar with it, the Java code below for multiplying two square matrices is essentially the same as the mathematical definition. Each element c[i][j] in the product of a[][] and b[][] is computed by taking the dot product of row i of a[][] with column j of b[][].

Click here to view code image

double[][] c = new double[n][n];
for (int i = 0; i < n; i++)
{
   for (int j = 0; j < n; j++)
   {
      // Dot product of row i and column j.
      for (int k = 0; k < n; k++)
         c[i][j] += a[i][k]*b[k][j];
   }
}

Click here to view code image

for (int i = 0; i < a.length; i++)
{
   for (int j = 0; j < a[i].length; j++)
      System.out.print(a[i][j] + " ");
   System.out.println();
}

This code tests your understanding of Java arrays, so you should take the time to study it. In this book, we normally use square or rectangular arrays, whose dimension are given by the variable m or n. Code that uses a[i].length in this way is a clear signal to you that an array is ragged.

Click here to view code image

double[][][] a = new double[n][n][n];

and then refer to an element with code like a[i][j][k], and so forth.

Two-dimensional arrays provide a natural representation for matrices, which are omnipresent in science, mathematics, and engineering. They also provide a natural way to organize large amounts of data—a key component in spreadsheets and many other computing applications. Through Cartesian coordinates, two- and three-dimensional arrays also provide the basis for models of the physical world. We consider their use in all three arenas throughout this book.

The dog’s escape probability is certainly dependent on the size of the city. In a tiny 5-by-5 city, it is easy to convince yourself that the dog is certain to escape. But what are the chances of escape when the city is large? We are also interested in other parameters. For example, how long is the dog’s path, on the average? How often does the dog come within one block of escaping? These sorts of properties are important in the various applications just mentioned.

SelfAvoidingWalk (PROGRAM 1.4.4) is a simulation of this situation that uses a two-dimensional boolean array, where each element represents an intersection. The value true indicates that the dog has visited the intersection; false indicates that the dog has not visited the intersection. The path starts in the center and takes random steps to places not yet visited until getting stuck or escaping at a boundary. For simplicity, the code is written so that if a random choice is made to go to a spot that has already been visited, it takes no action, trusting that some subsequent random choice will find a new place (which is assured because the code explicitly tests for a dead end and terminates the loop in that case).

Note that the code depends on Java initializing all of the array elements to false for each experiment. It also exhibits an important programming technique where we code the loop exit test in the while statement as a guard against an illegal statement in the body of the loop. In this case, the while loop-continuation condition serves as a guard against an out-of-bounds array access within the loop. This corresponds to checking whether the dog has escaped. Within the loop, a successful dead-end test results in a break out of the loop.

public class SelfAvoidingWalk
{
   public static void main(String[] args)

   {  // Do trials random self-avoiding
      // walks in an n-by-n lattice.
      int n = Integer.parseInt(args[0]);
      int trials = Integer.parseInt(args[1]);
      int deadEnds = 0;
      for (int t = 0; t < trials; t++)
      {
         boolean[][] a = new boolean[n][n];
         int x = n/2, y = n/2;
         while (x > 0 && x < n-1 && y > 0 && y < n-1)
         {  // Check for dead end and make a random move.
            a[x][y] = true;
            if (a[x-1][y] && a[x+1][y] && a[x][y-1] && a[x][y+1])
            {  deadEnds++; break;  }
            double r = Math.random();
            if      (r < 0.25) { if (!a[x+1][y]) x++; }
            else if (r < 0.50) { if (!a[x-1][y]) x--; }
            else if (r < 0.75) { if (!a[x][y+1]) y++; }
            else if (r < 1.00) { if (!a[x][y-1]) y--; }
         }
      }
      System.out.println(100*deadEnds/trials + "% dead ends");
   }
}

    n    | lattice size
 trials  | # trials
deadEnds | # trials resulting in a dead end
 a[][]   | intersections visited
  x, y   | current position
    r    | random number in (0, 1)

% java SelfAvoidingWalk 5 100
0% dead ends
% java SelfAvoidingWalk 20 100
36% dead ends
% java SelfAvoidingWalk 40 100
80% dead ends
% java SelfAvoidingWalk 80 100
98% dead ends

% java SelfAvoidingWalk 5 1000
0% dead ends
% java SelfAvoidingWalk 20 1000
32% dead ends
% java SelfAvoidingWalk 40 1000
70% dead ends
% java SelfAvoidingWalk 80 1000
95% dead ends

As you can see from the sample runs on the facing page, the unfortunate truth is that your dog is nearly certain to get trapped in a dead end in a large city. If you are interested in learning more about self-avoiding walks, you can find several suggestions in the exercises. For example, the dog is virtually certain to escape in the three-dimensional version of the problem. While this is an intuitive result that is confirmed by our tests, the development of a mathematical model that explains the behavior of self-avoiding walks is a famous open problem; despite extensive research, no one knows a succinct mathematical expression for the escape probability, the average length of the path, or any other important parameter.

Arrays are prominent in many of the programs that we consider, and the basic operations that we have discussed here will serve you well in addressing many programming tasks. When you are not using arrays explicitly (and you are sure to do so frequently), you will be using them implicitly, because all computers have a memory that is conceptually equivalent to an array.

The fundamental ingredient that arrays add to our programs is a potentially huge increase in the size of a program’s state. The state of a program can be defined as the information you need to know to understand what a program is doing. In a program without arrays, if you know the values of the variables and which statement is the next to be executed, you can normally determine what the program will do next. When we trace a program, we are essentially tracking its state. When a program uses arrays, however, there can be too huge a number of values (each of which might be changed in each statement) for us to effectively track them all. This difference makes writing programs with arrays more of a challenge than writing programs without them.

Arrays directly represent vectors and matrices, so they are of direct use in computations associated with many basic problems in science and engineering. Arrays also provide a succinct notation for manipulating a potentially huge amount of data in a uniform way, so they play a critical role in any application that involves processing large amounts of data, as you will see throughout this book.

A. In Java, both are legal and essentially equivalent. The former is how arrays are declared in C. The latter is the preferred style in Java since the type of the variable int[] more clearly indicates that it is an array of integers.

Q. Why do array indices start at 0 instead of 1?

A. This convention originated with machine-language programming, where the address of an array element would be computed by adding the index to the address of the beginning of an array. Starting indices at 1 would entail either a waste of space at the beginning of the array or a waste of time to subtract the 1.

Q. What happens if I use a negative integer to index an array?

A. The same thing as when you use an index that is too large. Whenever a program attempts to index an array with an index that is not between 0 and the array length minus 1, Java will issue an ArrayIndexOutOfBoundsException.

Q. Must the entries in an array initializer be literals?

A. No. The entries in an array initializer can be arbitrary expressions (of the specified type), even if their values are not known at compile time. For example, the following code fragment initializes a two-dimensional array using a command-line argument theta:

Click here to view code image

double theta = Double.parseDouble(args[0]);
double[][] rotation =
{
   { Math.cos(theta), -Math.sin(theta) },
   { Math.sin(theta),  Math.cos(theta) },
};

Q. Is there a difference between an array of characters and a String?

A. Yes. For example, you can change the individual characters in a char[] but not in a String. We will consider strings in detail in SECTION 3.1.

Q. What happens when I compare two arrays with (a == b)?

A. The expression evaluates to true if and only if a[] and b[] refer to the same array (memory address), not if they store the same sequence of values. Unfortunately, this is rarely what you want. Instead, you can use a loop to compare the corresponding elements.

Q. What happens when I use an array in an assignment statement like a = b?

A. The assignment statement makes the variable a refer to the same array as b—it does not copy the values from the array b to the array a, as you might expect. For example, consider the following code fragment:

int[] a = { 1, 2, 3, 4 };
int[] b = { 5, 6, 7, 8 };
a = b;
a[0] = 9;

After the assignment statement a = b, we have a[0] equal to 5, a[1] equal to 6, and so forth, as expected. That is, the arrays correspond to the same sequence of values. However, they are not independent arrays. For example, after the last statement, not only is a[0] equal to 9, but b[0] is equal to 9 as well. This is one of the key differences between primitive types (such as int and double) and nonprimitive types (such as arrays). We will revisit this subtle (but fundamental) distinction in more detail when we consider passing arrays to functions in SECTION 2.1 and reference types in SECTION 3.1.

Q. If a[] is an array, why does System.out.println(a) print something like @f62373, instead of the sequence of values in the array?

A. Good question. It prints the memory address of the array (as a hexadecimal integer), which, unfortunately, is rarely what you want.

Q. Which other pitfalls should I watch out for when using arrays?

A. It is very important to remember that Java automatically initializes arrays when you create them, so that creating an array takes time proportional to its length.

1.4.2 Describe and explain what happens when you try to compile a program with the following statement:

int n = 1000;
int[] a = new int[n*n*n*n];

1.4.3 Given two vectors of length n that are represented with one-dimensional arrays, write a code fragment that computes the Euclidean distance between them (the square root of the sums of the squares of the differences between corresponding elements).

1.4.4 Write a code fragment that reverses the order of the values in a one-dimensional string array. Do not create another array to hold the result. Hint: Use the code in the text for exchanging the values of two elements.

1.4.5 What is wrong with the following code fragment?

int[] a;
for (int i = 0; i < 10; i++)
   a[i] = i * i;

1.4.6 Write a code fragment that prints the contents of a two-dimensional boolean array, using * to represent true and a space to represent false. Include row and column indices.

1.4.7 What does the following code fragment print?

int[] a = new int[10];
for (int i = 0; i < 10; i++)
   a[i] = 9 - i;
for (int i = 0; i < 10; i++)
   a[i] = a[a[i]];
for (int i = 0; i < 10; i++)
   System.out.println(a[i]);

1.4.8 Which values does the following code put in the array a[]?

int n = 10;
int[] a = new int[n];
a[0] = 1;
a[1] = 1;
for (int i = 2; i < n; i++)
   a[i] = a[i-1] + a[i-2];

1.4.9 What does the following code fragment print?

int[] a = { 1, 2, 3 };
int[] b = { 1, 2, 3 };
System.out.println(a == b);

1.4.10 Write a program Deal that takes an integer command-line argument n and prints n poker hands (five cards each) from a shuffled deck, separated by blank lines.

1.4.11 Write a program HowMany that takes a variable number of command-line arguments and prints how many there are.

1.4.12 Write a program DiscreteDistribution that takes a variable number of integer command-line arguments and prints the integer i with probability proportional to the ith command-line argument.

1.4.13 Write code fragments to create a two-dimensional array b[][] that is a copy of an existing two-dimensional array a[][], under each of the following assumptions:

a. a[][] is square

b. a[][] is rectangular

c. a[][] may be ragged

Your solution to b should work for a, and your solution to c should work for both b and a, and your code should get progressively more complicated.

1.4.14 Write a code fragment to print the transposition (rows and columns exchanged) of a square two-dimensional array. For the example spreadsheet array in the text, you code would print the following:

Click here to view code image

99  98  92  94  99  90  76  92  97  89
85  57  77  32  34  46  59  66  71  29
98  78  76  11  22  54  88  89  24  38

1.4.15 Write a code fragment to transpose a square two-dimensional array in place without creating a second array.

1.4.16 Write a program that takes an integer command-line argument n and creates an n-by-n boolean array a[][] such that a[i][j] is true if i and j are relatively prime (have no common factors), and false otherwise. Use your solution to EXERCISE 1.4.6 to print the array. Hint: Use sieving.

1.4.17 Modify the spreadsheet code fragment in the text to compute a weighted average of the rows, where the weights of each exam score are in a one-dimensional array weights[]. For example, to assign the last of the three exams in our example to be twice the weight of the first two, you would use

Click here to view code image

double[] weights = { 0.25, 0.25, 0.50 };

Note that the weights should sum to 1.

1.4.18 Write a code fragment to multiply two rectangular matrices that are not necessarily square. Note: For the dot product to be well defined, the number of columns in the first matrix must be equal to the number of rows in the second matrix. Print an error message if the dimensions do not satisfy this condition.

1.4.19 Write a program that multiplies two square boolean matrices, using the or operation instead of + and the and operation instead of *.

1.4.20 Modify SelfAvoidingWalk (PROGRAM 1.4.4) to calculate and print the average length of the paths as well as the dead-end probability. Keep separate the average lengths of escape paths and dead-end paths.

1.4.21 Modify SelfAvoidingWalk to calculate and print the average area of the smallest axis-aligned rectangle that encloses the dead-end paths.

Click here to view code image

int[] frequencies = new int[13];
for (int i = 1; i <= 6; i++)
   for (int j = 1; j <= 6; j++)
      frequencies[i+j]++;

double[] probabilities = new double[13];
for (int k = 1; k <= 12; k++)
   probabilities[k] = frequencies[k] / 36.0;

The value probabilities[k] is the probability that the dice sum to k. Run experiments that validate this calculation by simulating n dice throws, keeping track of the frequencies of occurrence of each value when you compute the sum of two uniformly random integers between 1 and 6. How large does n have to be before your empirical results match the exact results to three decimal places?

1.4.23 Longest plateau. Given an array of integers, find the length and location of the longest contiguous sequence of equal values for which the values of the elements just before and just after this sequence are smaller.

1.4.24 Empirical shuffle check. Run computational experiments to check that our shuffling code works as advertised. Write a program ShuffleTest that takes two integer command-line arguments m and n, does n shuffles of an array of length m that is initialized with a[i] = i before each shuffle, and prints an m-by-m table such that row i gives the number of times i wound up in position j for all j. All values in the resulting array should be close to n / m.

1.4.25 Bad shuffling. Suppose that you choose a random integer between 0 and n-1 in our shuffling code instead of one between i and n-1. Show that the resulting order is not equally likely to be one of the n! possibilities. Run the test of the previous exercise for this version.

1.4.26 Music shuffling. You set your music player to shuffle mode. It plays each of the n songs before repeating any. Write a program to estimate the likelihood that you will not hear any sequential pair of songs (that is, song 3 does not follow song 2, song 10 does not follow song 9, and so on).

1.4.27 Minima in permutations. Write a program that takes an integer command-line argument n, generates a random permutation, prints the permutation, and prints the number of left-to-right minima in the permutation (the number of times an element is the smallest seen so far). Then write a program that takes two integer command-line arguments m and n, generates m random permutations of length n, and prints the average number of left-to-right minima in the permutations generated. Extra credit: Formulate a hypothesis about the number of left-to-right minima in a permutation of length n, as a function of n.

1.4.28 Inverse permutation. Write a program that reads in a permutation of the integers 0 to n-1 from n command-line arguments and prints the inverse permutation. (If the permutation is in an array a[], its inverse is the array b[] such that a[b[i]] = b[a[i]] = i.) Be sure to check that the input is a valid permutation.

1.4.29 Hadamard matrix. The n-by-n Hadamard matrix H(n) is a boolean matrix with the remarkable property that any two rows differ in exactly n / 2 values. (This property makes it useful for designing error-correcting codes.) H(1) is a 1-by-1 matrix with the single element true, and for n > 1, H(2n) is obtained by aligning four copies of H(n) in a large square, and then inverting all of the values in the lower right n-by-n copy, as shown in the following examples (with T representing true and F representing false, as usual).

Write a program that takes an integer command-line argument n and prints H(n). Assume that n is a power of 2.

1.4.30 Rumors. Alice is throwing a party with n other guests, including Bob. Bob starts a rumor about Alice by telling it to one of the other guests. A person hearing this rumor for the first time will immediately tell it to one other guest, chosen uniformly at random from all the people at the party except Alice and the person from whom they heard it. If a person (including Bob) hears the rumor for a second time, he or she will not propagate it further. Write a program to estimate the probability that everyone at the party (except Alice) will hear the rumor before it stops propagating. Also calculate an estimate of the expected number of people to hear the rumor.

1.4.31 Counting primes. Compare PrimeSieve with the method that we used to demonstrate the break statement, at the end of SECTION 1.3. This is a classic example of a space–time tradeoff: PrimeSieve is fast, but requires a boolean array of length n; the other approach uses only two integer variables, but is substantially slower. Estimate the magnitude of this difference by finding the value of n for which this second approach can complete the computation in about the same time as java PrimeSeive 1000000.

1.4.32 Minesweeper. Write a program that takes three command-line arguments m, n, and p and produces an m-by-n boolean array where each element is occupied with probability p. In the minesweeper game, occupied cells represent bombs and empty cells represent safe cells. Print out the array using an asterisk for bombs and a period for safe cells. Then, create an integer two-dimensional array with the number of neighboring bombs (above, below, left, right, or diagonal).

* * . . .       * * 1 0 0
. . . . .       3 3 2 0 0
. * . . .       1 * 1 0 0

Write your code so that you have as few special cases as possible to deal with, by using an (m+2)-by-(n+2) boolean array.

1.4.33 Find a duplicate. Given an integer array of length n, with each value between 1 and n, write a code fragment to determine whether there are any duplicate values. You may not use an extra array (but you do not need to preserve the contents of the given array.)

1.4.34 Self-avoiding walk length. Suppose that there is no limit on the size of the grid. Run experiments to estimate the average path length.

1.4.35 Three-dimensional self-avoiding walks. Run experiments to verify that the dead-end probability is 0 for a three-dimensional self-avoiding walk and to compute the average path length for various values of n.

1.4.36 Random walkers. Suppose that n random walkers, starting in the center of an n-by-n grid, move one step at a time, choosing to go left, right, up, or down with equal probability at each step. Write a program to help formulate and test a hypothesis about the number of steps taken before all cells are touched.

1.4.37 Bridge hands. In the game of bridge, four players are dealt hands of 13 cards each. An important statistic is the distribution of the number of cards in each suit in a hand. Which is the most likely, 5–3-3–2, 4–4-3–2, or 4–3–3–3?

1.4.38 Birthday problem. Suppose that people enter an empty room until a pair of people share a birthday. On average, how many people will have to enter before there is a match? Run experiments to estimate the value of this quantity. Assume birthdays to be uniform random integers between 0 and 364.

1.4.39 Coupon collector. Run experiments to validate the classical mathematical result that the expected number of coupons needed to collect n values is approximately n H_n, where H_n in the nth harmonic number. For example, if you are observing the cards carefully at the blackjack table (and the dealer has enough decks randomly shuffled together), you will wait until approximately 235 cards are dealt, on average, before seeing every card value.

1.4.40 Riffle shuffle. Compose a program to rearrange a deck of n cards using the Gilbert–Shannon–Reeds model of a riffle shuffle. First, generate a random integer r according to a binomial distribution: flip a fair coin n times and let r be the number of heads. Now, divide the deck into two piles: the first r cards and the remaining n – r cards. To complete the shuffle, repeatedly take the top card from one of the two piles and put it on the bottom of a new pile. If there are n₁ cards remaining in the first pile and n₂ cards remaining in the second pile, choose the next card from the first pile with probability n₁ / (n₁ + n₂) and from the second pile with probability n₂ / (n₁ + n₂). Investigate how many riffle shuffles you need to apply to a deck of 52 cards to produce a (nearly) uniformly shuffled deck.

1.4.41 Binomial distribution. Write a program that takes an integer commandline argument n and creates a two-dimensional ragged array a[][] such that a[n][k] contains the probability that you get exactly k heads when you toss a fair coin n times. These numbers are known as the binomial distribution: if you multiply each element in row i by 2ⁿ, you get the binomial coefficients—the coefficients of x^k in (x+1)ⁿ—arranged in Pascal’s triangle. To compute them, start with a[n][0] = 0.0 for all n and a[1][1] = 1.0, then compute values in successive rows, left to right, with a[n][k] = (a[n-1][k] + a[n-1][k-1]) / 2.0.

The abbreviation I/O is universally understood to mean input/output, a collective term that refers to the mechanisms by which programs communicate with the outside world. Your computer’s operating system controls the physical devices that are connected to your computer. To implement the standard I/O abstractions, we use libraries of methods that interface to the operating system.

You have already been accepting arguments from the command line and printing strings in a terminal window; the purpose of this section is to provide you with a much richer set of tools for processing and presenting data. Like the System.out.print() and System.out.println() methods that you have been using, these methods do not implement pure mathematical functions—their purpose is to cause some side effect, either on an input device or an output device. Our prime concern is using such devices to get information into and out of our programs.

An essential feature of standard I/O mechanisms is that there is no limit on the amount of input or output, from the point of view of the program. Your programs can consume input or produce output indefinitely.

One use of standard I/O mechanisms is to connect your programs to files on your computer’s external storage. It is easy to connect standard input, standard output, standard drawing, and standard audio to files. Such connections make it easy to have your Java programs save or load results to files for archival purposes or for later reference by other programs or other applications.

A Java program takes input strings from the command line and prints a string of characters as output. By default, both command-line arguments and standard output are associated with the application that takes commands (the one in which you have been typing the java and javac commands). We use the generic term terminal window to refer to this application. This model has proved to be a convenient and direct way for us to interact with our programs and data.

For reference, and as a starting point, RandomSeq (PROGRAM 1.5.1) is a program that uses this model. It takes a command-line argument n and produces an output sequence of n random numbers between 0 and 1.

Now we are going to complement command-line arguments and standard output with three additional mechanisms that address their limitations and provide us with a far more useful programming model. These mechanisms give us a new bird’s-eye view of a Java program in which the program converts a standard input stream and a sequence of command-line arguments into a standard output stream, a standard drawing, and a standard audio stream.

public class RandomSeq
{
   public static void main(String[] args)
   {  // Print a random sequence of n real values in [0, 1)
      int n = Integer.parseInt(args[0]);
      for (int i = 0; i < n; i++)
         System.out.println(Math.random());
   }
}

% java RandomSeq 1000000
0.2498362534343327
0.5578468691774513
0.5702167639727175
0.32191774192688727
0.6865902823177537
...

To use both command-line arguments and standard output, you have been using built-in Java facilities. Java also has built-in facilities that support abstractions like standard input, standard drawing, and standard audio, but they are somewhat more complicated to use, so we have developed a simpler interface to them in our StdIn, StdDraw, and StdAudio libraries. To logically complete our programming model, we also include a StdOut library. To use these libraries, you must make StdIn.java, StdOut.java, StdDraw.java, and StdAudio.java available to Java (see the Q&A at the end of this section for details).

The standard input and standard output abstractions date back to the development of the UNIX operating system in the 1970s and are found in some form on all modern systems. Although they are primitive by comparison to various mechanisms developed since then, modern programmers still depend on them as a reliable way to connect data to programs. We have developed for this book standard drawing and standard audio in the same spirit as these earlier abstractions to provide you with an easy way to produce visual and aural output.

Since the first time that we printed double values, we have been distracted by excessive precision in the printed output. For example, when we use System.out.print(Math.PI) we get the output 3.141592653589793, even though we might prefer to see 3.14 or 3.14159. The print() and println() methods present each number to up to 15 decimal places even when we would be happy with only a few. The printf() method is more flexible. For example, it allows us to specify the number of decimal places when converting floating-point numbers to strings for output. We can write StdOut.printf("%7.5f", Math.PI) to get 3.14159, and we can replace System.out.print(t) with

Click here to view code image

StdOut.printf("The square root of %.1f is %.6f", c, t);

in Newton (PROGRAM 1.3.6) to get output like

Click here to view code image

The square root of 2.0 is 1.414214

Next, we describe the meaning and operation of these statements, along with extensions to handle the other built-in types of data.

• w is the field width, the number of characters that should be written. If the number of characters to be written exceeds (or equals) the field width, then the field width is ignored; otherwise, the output is padded with spaces on the left. A negative field width indicates that the output instead should be padded with spaces on the right.

• .p is the precision. For floating-point numbers, the precision is the number of digits that should be written after the decimal point; for strings, it is the number of characters of the string that should be printed. The precision is not used with integers.

• c is the conversion code. The conversion codes that we use most frequently are d (for decimal values from Java’s integer types), f (for floating-point values), e (for floating-point values using scientific notation), s (for string values), and b (for boolean values).

The field width and precision can be omitted, but every specification must have a conversion code.

The most important thing to remember about using printf() is that the conversion code and the type of the corresponding argument must match. That is, Java must be able to convert from the type of the argument to the type required by the conversion code. Every type of data can be converted to String, but if you write StdOut.printf("%12d", Math.PI) or StdOut.printf("%4.2f", 512), you will get an IllegalFormatConversionException run-time error.

Click here to view code image

StdOut.printf("PI is approximately %.2f.
", Math.PI);

prints the line

PI is approximately 3.14.

Note that we need to explicitly include the newline character in the format string to print a new line with printf().

Click here to view code image

String formats = "%3s  $%6.2f   $%7.2f   $%5.2f
";
StdOut.printf(formats, month[i], pay, balance, interest);

to print the second and subsequent lines in a table like this (see EXERCISE 1.5.13):

Click here to view code image

     payment    balance  interest
Jan  $299.00   $9742.67   $41.67
Feb  $299.00   $9484.26   $40.59
Mar  $299.00   $9224.78   $39.52
...

Formatted printing is convenient because this sort of code is much more compact than the string-concatenation code that we have been using to create output strings. We have described only the basic options; see the booksite for more details.

"           512"
"512           "

"       1595.17"
"1595.1680011"
"    1.5952e+03"

"  Hello, World"
"Hello, World  "
"Hello         "

• Those for reading individual values, one at a time

• Those for reading lines, one at a time

• Those for reading characters, one at a time

• Those for reading a sequence of values of the same type

Generally, it is best not to mix functions from the different categories in the same program. These methods are largely self-documenting (the names describe their effect), but their precise operation is worthy of careful consideration, so we will consider several examples in detail.

For example, consider the program AddInts, which takes a command-line argument n, then reads n numbers from standard input, adds them, and prints the result to standard output. When you type java AddInts 4, after the program takes the command-line argument, it calls the method StdIn.readInt() and waits for you to type an integer. Suppose that you want 144 to be the first value. As you type 1, then 4, and then 4, nothing happens, because StdIn does not know that you are done typing the integer. But when you then type <Return> to signify the end of your integer, StdIn.readInt() immediately returns the value 144, which your program adds to sum and then calls StdIn.readInt() again. Again, nothing happens until you type the second value: if you type 2, then 3, then 3, and then <Return> to end the number, StdIn.readInt() returns the value 233, which your program again adds to sum. After you have typed four numbers in this way, AddInts expects no more input and prints the sum, as desired.

public class TwentyQuestions
{
   public static void main(String[] args)
   {  // Generate a number and answer questions
      // while the user tries to guess the value.
      int secret = 1 + (int) (Math.random() * 1000000);
      StdOut.print("I'm thinking of a number ");
      StdOut.println("between 1 and 1,000,000");
      int guess = 0;
      while (guess != secret)
      {  // Solicit one guess and provide one answer.
         StdOut.print("What's your guess? ");
         guess = StdIn.readInt();
         if (guess == secret) StdOut.println("You win!");
         if (guess < secret)  StdOut.println("Too low ");
         if (guess > secret)  StdOut.println("Too high");
      }
   }
}

secret | secret value
 guess | user's guess

% java TwentyQuestions
I'm thinking of a number between 1 and 1,000,000
What's your guess? 500000
Too high
What's your guess? 250000
Too low
What's your guess? 375000
Too high
What's your guess? 312500
Too high
What's your guess? 300500
Too low
...

Standard input is a substantial step up from the command-line-arguments model that we have been using, for two reasons, as illustrated by TwentyQuestions and Average. First, we can interact with our program—with command-line arguments, we can provide data to the program only before it begins execution. Second, we can read in large amounts of data—with command-line arguments, we can enter only values that fit on the command line. Indeed, as illustrated by Average, the amount of data can be potentially unlimited, and many programs are made simpler by that assumption. A third raison d’être for standard input is that your operating system makes it possible to change the source of standard input, so that you do not have to type all the input. Next, we consider the mechanisms that enable this possibility.

public class Average
{
   public static void main(String[] args)
   {  // Average the numbers on standard input.
      double sum = 0.0;
      int n = 0;
      while (!StdIn.isEmpty())
      {  // Read a number from standard input and add to sum.
         double value = StdIn.readDouble();
         sum += value;
         n++;
      }
      double average = sum / n;
      StdOut.println("Average is " + average);
   }
}

 n  | count of numbers read
sum | cumulated sum

% java Average
10.0 5.0 6.0
3.0
7.0 32.0
<Ctrl-D>
Average is 10.5

% java RandomSeq 100000 > data.txt
% java Average < data.txt
Average is 0.5010473676174824
% java RandomSeq 100000 | java Average
Average is 0.5000499417963857

Click here to view code image

% java RandomSeq 1000 > data.txt

specifies that the standard output stream is not to be printed in the terminal window, but instead is to be written to a text file named data.txt. Each call to System.out.print() or System.out.println() appends text at the end of that file. In this example, the end result is a file that contains 1,000 random values. No output appears in the terminal window: it goes directly into the file named after the > symbol. Thus, we can save away information for later retrieval. Note that we do not have to change RandomSeq (PROGRAM 1.5.1) in any way for this mechanism to work—it uses the standard output abstraction and is unaffected by our use of a different implementation of that abstraction. You can use redirection to save output from any program that you write. Once you have expended a significant amount of effort to obtain a result, you often want to save the result for later reference. In a modern system, you can save some information by using cut-and-paste or some similar mechanism that is provided by the operating system, but cut-and-paste is inconvenient for large amounts of data. By contrast, redirection is specifically designed to make it easy to handle large amounts of data.

public class RangeFilter
{
   public static void main(String[] args)
   {  // Filter out numbers not between lo and hi.
      int lo = Integer.parseInt(args[0]);
      int hi = Integer.parseInt(args[1]);
      while (!StdIn.isEmpty())
      {  // Process one number.
         int value = StdIn.readInt();
         if (value >= lo && value <= hi)
            StdOut.print(value + " ");
      }
      StdOut.println();
   }
}

  lo  | lower bound of range
  hi  | upper bound of range
value | current number

% java RangeFilter 100 400
358 1330 55 165 689 1014 3066 387 575 843 203 48 292 877 65 998
358 165 387 203 292
<Ctrl-D>

% java Average < data.txt

This command reads a sequence of numbers from the file data.txt and computes their average value. Specifically, the < symbol is a directive that tells the operating system to implement the standard input stream by reading from the text file data.txt instead of waiting for the user to type something into the terminal window. When the program calls StdIn.readDouble(), the operating system reads the value from the file. The file data.txt could have been created by any application, not just a Java program—many applications on your computer can create text files. This facility to redirect from a file to standard input enables us to create data-driven code where you can change the data processed by a program without having to change the program at all. Instead, you can keep data in files and write programs that read from the standard input stream.

Click here to view code image

% java RandomSeq 1000 | java Average

specifies that the standard output stream for RandomSeq and the standard input stream for Average are the same stream. The effect is as if RandomSeq were typing the numbers it generates into the terminal window while Average is running. This example also has the same effect as the following sequence of commands:

Click here to view code image

% java RandomSeq 1000 > data.txt
% java Average < data.txt

In this case, the file data.txt is not created. This difference is profound, because it removes another limitation on the size of the input and output streams that we can process. For example, you could replace 1000 in the example with 1000000000, even though you might not have the space to save a billion numbers on our computer (you, however, do need the time to process them). When RandomSeq calls System.out.println(), a string is added to the end of the stream; when Average calls StdIn.readInt(), a string is removed from the beginning of the stream. The timing of precisely what happens is up to the operating system: it might run RandomSeq until it produces some output, and then run Average to consume that output, or it might run Average until it needs some input, and then run RandomSeq until it produces the needed input. The end result is the same, but your programs are freed from worrying about such details because they work solely with the standard input and standard output abstractions.

For many common tasks, it is convenient to think of each program as a filter that converts a standard input stream to a standard output stream in some way, with piping as the command mechanism to connect programs together. For example, RangeFilter (PROGRAM 1.5.4) takes two command-line arguments and prints on standard output those numbers from standard input that fall within the specified range. You might imagine standard input to be measurement data from some instrument, with the filter being used to throw away data outside the range of interest for the experiment at hand.

Several standard filters that were designed for Unix still survive (sometimes with different names) as commands in modern operating systems. For example, the sort filter puts the lines on standard input in sorted order:

% java RandomSeq 6 | sort
0.035813305516568916
0.14306638757584322
0.348292877655532103
0.5761644592016527
0.7234592733392126
0.9795908813988247

We discuss sorting in SECTION 4.2. A second useful filter is grep, which prints the lines from standard input that match a given pattern. For example, if you type

% grep lo < RangeFilter.java

you get the result

Click here to view code image

     // Filter out numbers not between lo and hi.
     int lo = Integer.parseInt(args[0]);
         if (value >= lo && value <= hi)

Programmers often use tools such as grep to get a quick reminder of variable names or language usage details. A third useful filter is more, which reads data from standard input and displays it in your terminal window one screenful at a time. For example, if you type

% java RandomSeq 1000 | more

you will see as many numbers as fit in your terminal window, but more will wait for you to hit the space bar before displaying each succeeding screenful. The term filter is perhaps misleading: it was meant to describe programs like RangeFilter that write some subsequence of standard input to standard output, but it is now often used to describe any program that reads from standard input and writes to standard output.

Processing large amounts of information plays an essential role in many applications of computing. A scientist may need to analyze data collected from a series of experiments, a stock trader may wish to analyze information about recent financial transactions, or a student may wish to maintain collections of music and movies. In these and countless other applications, data-driven programs are the norm. Standard output, standard input, redirection, and piping provide us with the capability to address such applications with our Java programs. We can collect data into files on our computer through the web or any of the standard devices and use redirection and piping to connect data to our programs. Many (if not most) of the programming examples that we consider throughout this book have this ability.

As with StdIn and StdOut, our standard drawing abstraction is implemented in a library StdDraw that you will need to make available to Java (see the first Q&A at the end of this section). Standard drawing is very simple. We imagine an abstract drawing device capable of drawing lines and points on a two-dimensional canvas. The device is capable of responding to the commands that our programs issue in the form of calls to methods in StdDraw such as the following:

Like the methods for standard input and standard output, these methods are nearly self-documenting: StdDraw.line() draws a straight line segment connecting the point (x₀, y₀) with the point (x₁, y₁) whose coordinates are given as arguments. StdDraw.point() draws a spot centered on the point (x, y) whose coordinates are given as arguments. The default scale is the unit square (all x- and y-coordinates between 0 and 1). StdDraw displays the canvas in a window on your computer’s screen, with black lines and points on a white background. The window includes a menu option to save your drawing to a file, in a format suitable for publishing on paper or on the web.

When you use a computer to create drawings, you get immediate feedback (the drawing) so that you can refine and improve your program quickly. With a computer program, you can create drawings that you could not contemplate making by hand. In particular, instead of viewing our data as merely numbers, we can use pictures, which are far more expressive. We will consider other graphics examples after we discuss a few other drawing commands.

For example, the two-call sequence

StdDraw.setXscale(x0, x1);
StdDraw.setYscale(y0, y1);

sets the drawing coordinates to be within a bounding box whose lower-left corner is at (x₀, y₀) and whose upper-right corner is at (x₁, y₁). Scaling is the simplest of the transformations commonly used in graphics. In the applications that we consider in this chapter, we use it in a straightforward way to match our drawings to our data.

The pen is circular, so that lines have rounded ends, and when you set the pen radius to r and draw a point, you get a circle of radius r. The default pen radius is 0.002 and is not affected by coordinate scaling. This default is about 1/500 the width of the default window, so that if you draw 200 points equally spaced along a horizontal or vertical line, you will be able to see individual circles, but if you draw 250 such points, the result will look like a line. When you issue the command StdDraw.setPenRadius(0.01), you are saying that you want the thickness of the line segments and the size of the points to be five times the 0.002 standard.

---

Program 1.5.5 Standard input-to-drawing filter

Click here to view code image

public class PlotFilter
{
   public static void main(String[] args)
   {
      // Scale as per first four values.
      double x0 = StdIn.readDouble();
      double y0 = StdIn.readDouble();
      double x1 = StdIn.readDouble();
      double y1 = StdIn.readDouble();
      StdDraw.setXscale(x0, x1);
      StdDraw.setYscale(y0, y1);

     // Read the points and plot to standard drawing.
      while (!StdIn.isEmpty())
      {
         double x = StdIn.readDouble();
         double y = StdIn.readDouble();
         StdDraw.point(x, y);
      }
   }
}

---

 x0  | left bound
 y0  | bottom bound
 x1  | right bound
 y1  | top bound
x, y | current point

This program reads a sequence of points from standard input and plots them to standard drawing. (By convention, the first four numbers are the minimum and maximum x- and y-coordinates.) The file USA.txt contains the coordinates of 13,509 cities in the United States

---

---

The arguments for circle() and filledCircle() define a circle of radius r centered at (x, y); the arguments for square() and filledSquare() define a square of side length 2r centered at (x, y); the arguments for rectangle() and filledRectangle() define a rectangle of width 2r₁ and height 2r₂, centered at (x, y); and the arguments for polygon() and filledPolygon() define a sequence of points that are connected by line segments, including one from the last point to the first point.

In this code, Font and Color are nonprimitive types that you will learn about in SECTION 3.1. Until then, we leave the details to StdDraw. The available pen colors are BLACK, BLUE, CYAN, DARK_GRAY, GRAY, GREEN, LIGHT_GRAY, MAGENTA, ORANGE, PINK, RED, WHITE, YELLOW, and BOOK_BLUE, all of which are defined as constants within StdDraw. For example, the call StdDraw.setPenColor(StdDraw.GRAY) changes the pen to use gray ink. The default ink color is BLACK. The default font in StdDraw suffices for most of the drawings that you need (you can find information on using other fonts on the booksite). For example, you might wish to use these methods to annotate function graphs to highlight relevant values, and you might find it useful to develop similar methods to annotate other parts of your drawings.

Shapes, color, and text are basic tools that you can use to produce a dizzying variety of images, but you should use them sparingly. Use of such artifacts usually presents a design challenge, and our StdDraw commands are crude by the standards of modern graphics libraries, so that you are likely to need an extensive number of calls to them to produce the beautiful images that you may imagine. By comparison, using color or labels to help focus on important information in drawings is often worthwhile, as is using color to represent data values.

One reason to use double buffering is for efficiency when performing a large number of drawing commands. Incrementally displaying a complex drawing while it is being created can be intolerably inefficient on many computer systems. For example, you can dramatically speed up PROGRAM 1.5.5 by adding a call to enableDoubleBuffering() before the while loop and a call to show() after the while loop. Now, the points appear all at once (instead of one at a time).

Our most important use of double buffering is to produce computer animations, where we create the illusion of motion by rapidly displaying static drawings. Such effects can provide compelling and dynamic visualizations of scientific phenomenon. We can produce animations by repeating the following four steps:

• Clear the offscreen canvas.

• Draw objects on the offscreen canvas.

• Copy the offscreen canvas to the onscreen canvas.

• Wait for a short while.

In support of the first and last of these steps, StdDraw provides three additional methods. The clear() methods clear the canvas, either to white or to a specified color. To control the apparent speed of an animation, the pause() method takes an argument dt and tells StdDraw to wait for dt milliseconds before processing additional commands.

• Clear the offscreen canvas to white.

• Draw a black ball at the new position on the offscreen canvas.

• Copy the offscreen canvas to the onscreen canvas.

• Wait for a short while.

To create the illusion of movement, we iterate these steps for a whole sequence of positions of the ball (one that will form a straight line, in this case). Without double buffering, the image of the ball will rapidly flicker between black and white instead of creating a smooth animation.

BouncingBall (PROGRAM 1.5.6) implements these steps to create the illusion of a ball moving in the 2-by-2 box centered at the origin. The current position of the ball is (r_x, r_y), and we compute the new position at each step by adding v_x to r_x and v_y to r_y. Since (v_x, v_y) is the fixed distance that the ball moves in each time unit, it represents the velocity. To keep the ball in the standard drawing window, we simulate the effect of the ball bouncing off the walls according to the laws of elastic collision. This effect is easy to implement: when the ball hits a vertical wall, we change the velocity in the x-direction from v_x to –v_x, and when the ball hits a horizontal wall, we change the velocity in the y-direction from v_y to –v_y. Of course, you have to download the code from the booksite and run it on your computer to see motion. To make the image clearer on the printed page, we modified BouncingBall to use a gray background that also shows the track of the ball as it moves (see EXERCISE 1.5.34).

Standard drawing completes our programming model by adding a “picture is worth a thousand words” component. It is a natural abstraction that you can use to better open up your programs to the outside world. With it, you can easily produce the function graphs and visual representations of data that are commonly used in science and engineering. We will put it to such uses frequently throughout this book. Any time that you spend now working with the sample programs on the last few pages will be well worth the investment. You can find many useful examples on the booksite and in the exercises, and you are certain to find some outlet for your creativity by using StdDraw to meet various challenges. Can you draw an n-pointed star? Can you make our bouncing ball actually bounce (by adding gravity)? You may be surprised at how easily you can accomplish these and other tasks.

---

Program 1.5.6 Bouncing ball

Click here to view code image

public class BouncingBall
{
   public static void main(String[] args)
   {  // Simulate the motion of a bouncing ball.
      StdDraw.setXscale(-1.0, 1.0);
      StdDraw.setYscale(-1.0, 1.0);
StdDraw.enableDoubleBuffering();
      double rx = 0.480, ry = 0.860;
      double vx = 0.015, vy = 0.023;
      double radius = 0.05;
      while(true)
      {  // Update ball position and draw it.
         if (Math.abs(rx + vx) + radius > 1.0) vx = -vx;
         if (Math.abs(ry + vy) + radius > 1.0) vy = -vy;
         rx += vx;
         ry += vy;
         StdDraw.clear();
         StdDraw.filledCircle(rx, ry, radius);
         StdDraw.show();
         StdDraw.pause(20);
      }
   }
}

---

rx, ry | position
vx, vy | velocity
  dt   | wait time
radius | ball radius

This program simulates the motion of a bouncing ball in the box with coordinates between –1 and +1. The ball bounces off the boundary according to the laws of inelastic collision. The 20-millisecond wait for StdDraw.pause() keeps the black image of the ball persistent on the screen, even though most of the ball’s pixels alternate between black and white. The images below, which show the track of the ball, are produced by a modified version of this code (see EXERCISE 1.5.34).

---

---

This API table summarizes the StdDraw methods that we have considered:

For example, suppose that you want to play concert A for 10 seconds. At 44,100 samples per second, you need a double array of length 441,001. To fill in the array, use a for loop that samples the function sin(2πt × 440) at t = 0/44,100, 1/44,100, 2/44,100, 3/44,100, ..., 441,000/44,100. Once we fill the array with these values, we are ready for StdAudio.play(), as in the following code:

Click here to view code image

int SAMPLING_RATE = 44100;       // samples per second
int hz = 440;                    // concert A
double duration = 10.0;          // ten seconds
int n = (int) (SAMPLING_RATE * duration);
double[] a = new double[n+1];
for (int i = 0; i <= n; i++)
   a[i] = Math.sin(2 * Math.PI * i * hz / SAMPLING_RATE);
StdAudio.play(a);

This code is the “Hello, World” of digital audio. Once you use it to get your computer to play this note, you can write code to play other notes and make music! The difference between creating sound and plotting an oscillating curve is nothing more than the output device. Indeed, it is instructive and entertaining to send the same numbers to both standard drawing and standard audio (see EXERCISE 1.5.27).

PlayThatTune (PROGRAM 1.5.7) is an example that shows how you can use StdAudio to turn your computer into a musical instrument. It takes notes from standard input, indexed on the chromatic scale from concert A, and plays them on standard audio. You can imagine all sorts of extensions on this basic scheme, some of which are addressed in the exercises.

We include standard audio in our basic arsenal of programming tools because sound processing is one important application of scientific computing that is certainly familiar to you. Not only has the commercial application of digital signal processing had a phenomenal impact on modern society, but the science and engineering behind it combine physics and computer science in interesting ways. We will study more components of digital signal processing in some detail later in the book. (For example, you will learn in SECTION 2.1 how to create sounds that are more musical than the pure sounds produced by PlayThatTune.)

---

Program 1.5.7 Digital signal processing

Click here to view code image

public class PlayThatTune
{
   public static void main(String[] args)
   {  // Read a tune from StdIn and play it.
      int SAMPLING_RATE = 44100;
      while (!StdIn.isEmpty())
      {  // Read and play one note.
         int pitch = StdIn.readInt();
         double duration = StdIn.readDouble();
         double hz = 440 * Math.pow(2, pitch / 12.0);
         int n = (int) (SAMPLING_RATE * duration);
         double[] a = new double[n+1];
         for (int i = 0; i <= n; i++)
            a[i] = Math.sin(2*Math.PI * i * hz / SAMPLING_RATE);
         StdAudio.play(a);
      }
   }
}

---

 pitch   | distance from A
duration | note play time
   hz    | frequency
   n     | number of samples
  a[]    | sampled sine wave

This data-driven program turns your computer into a musical instrument. It reads notes and durations from standard input and plays a pure tone corresponding to each note for the specified duration on standard audio. Each note is specified as a pitch (distance from concert A). After reading each note and duration, the program creates an array by sampling a sine wave of the specified frequency and duration at 44,100 samples per second, and plays it using StdAudio.play().

---

% more elise.txt
7 0.25
6 0.25
7 0.25
6 0.25
7 0.25
2 0.25
5 0.25
3 0.25
0 0.50

---

---

The API table below summarizes the methods in StdAudio:

A. If you followed the step-by-step instructions on the booksite for installing Java, these libraries should already be available to Java. Alternatively, you can copy the files StdIn.java, StdOut.java, StdDraw.java, and StdAudio.java from the booksite and put them in the same directory as the programs that use them.

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

A. The library StdIn is not available to Java.

Q. Why are we not using the standard Java libraries for input, graphics, and sound?

A. We are using them, but we prefer to work with simpler abstract models. The Java libraries behind StdIn, StdDraw, and StdAudio are built for production programming, and the libraries and their APIs are a bit unwieldy. To get an idea of what they are like, look at the code in StdIn.java, StdDraw.java, and StdAudio.java.

Q. So, let me get this straight. If I use the format %2.4f for a double value, I get two digits before the decimal point and four digits after, right?

A. No, that specifies 4 digits after the decimal point. The first value is the width of the whole field. You want to use the format %7.2f to specify 7 characters in total, 4 before the decimal point, the decimal point itself, and 2 digits after the decimal point.

Q. Which other conversion codes are there for printf()?

A. For integer values, there is o for octal and x for hexadecimal. There are also numerous formats for dates and times. See the booksite for more information.

Q. Can my program reread data from standard input?

A. No. You get only one shot at it, in the same way that you cannot undo a println() command.

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

A. You will get an error. StdIn.isEmpty() allows you to avoid such an error by checking whether there is more input available.

Q. Why does StdDraw.square(x, y, r) draw a square of width 2*r instead of r?

A. This makes it consistent with the function StdDraw.circle(x, y, r), in which the third argument is the radius of the circle, not the diameter. In this context, r is the radius of the biggest circle that can fit inside the square.

Q. My terminal window hangs at the end of a program using StdAudio. How can I avoid having to use <Ctrl-C> to get a command prompt?

A. Add a call to System.exit(0) as the last line in main(). Don’t ask why.

Q. Can I use negative integers to specify notes below concert A when making input files for PlayThatTune?

A. Yes. Actually, our choice to put concert A at 0 is arbitrary. A popular standard, known as the MIDI Tuning Standard, starts numbering at the C five octaves below concert A. By that convention, concert A is 69 and you do not need to use negative numbers.

Q. Why do I hear weird results on standard audio when I try to sonify a sine wave with a frequency of 30,000 hertz (or more)?

A. The Nyquist frequency, defined as one-half the sampling frequency, represents the highest frequency that can be reproduced. For standard audio, the sampling frequency is 44,100 hertz, so the Nyquist frequency is 22,050 hertz.

1.5.2 Modify your program from the previous exercise to insist that the integers must be positive (by prompting the user to enter positive integers whenever the value entered is not positive).

1.5.3 Write a program that takes an integer command-line argument n, reads n floating-point numbers from standard input, and prints their mean (average value) and sample standard deviation (square root of the sum of the squares of their differences from the average, divided by n-1).

1.5.4 Extend your program from the previous exercise to create a filter that reads n floating-point numbers from standard input, and prints those that are further than 1.5 standard deviations from the mean.

1.5.5 Write a program that reads in a sequence of integers and prints both the integer that appears in a longest consecutive run and the length of that run. For example, if the input is 1 2 2 1 5 1 1 7 7 7 7 1 1, then your program should print Longest run: 4 consecutive 7s.

1.5.6 Write a filter that reads in a sequence of integers and prints the integers, removing repeated values that appear consecutively. For example, if the input is 1 2 2 1 5 1 1 7 7 7 7 1 1 1 1 1 1 1 1 1, your program should print 1 2 1 5 1 7 1.

1.5.7 Write a program that takes an integer command-line argument n, reads in n-1 distinct integers between 1 and n, and determines the missing value.

1.5.8 Write a program that reads in positive floating-point numbers from standard input and prints their geometric and harmonic means. The geometric mean of n positive numbers x₁, x₂, ..., x_n is (x₁ × x₂ × ... × x_n)^1/n. The harmonic mean is n / (1/x₁ + 1/x₂ + ... + 1/x_n). Hint: For the geometric mean, consider taking logarithms to avoid overflow.

1.5.9 Suppose that the file input.txt contains the two strings F and F. What does the following command do (see EXERCISE 1.2.35)?

Click here to view code image

% java Dragon < input.txt | java Dragon | java Dragon

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

1.5.10 Write a filter TenPerLine that reads from standard input a sequence of integers between 0 and 99 and prints them back, 10 integers per line, with columns aligned. Then write a program RandomIntSeq that takes two integer command-line arguments m and n and prints n random integers between 0 and m-1. Test your programs with the command java RandomIntSeq 200 100 | java TenPerLine.

1.5.11 Write a program that reads in text from standard input and prints the number of words in the text. For the purpose of this exercise, a word is a sequence of non-whitespace characters that is surrounded by whitespace.

1.5.12 Write a program that reads in lines from standard input with each line containing a name and two integers and then uses printf() to print a table with a column of the names, the integers, and the result of dividing the first by the second, accurate to three decimal places. You could use a program like this to tabulate batting averages for baseball players or grades for students.

1.5.13 Write a program that prints a table of the monthly payments, remaining principal, and interest paid for a loan, taking three numbers as command-line arguments: the number of years, the principal, and the interest rate (see EXERCISE 1.2.24).

1.5.14 Which of the following require saving all the values from standard input (in an array, say), and which could be implemented as a filter using only a fixed number of variables? For each, the input comes from standard input and consists of n real numbers between 0 and 1.

• Print the maximum and minimum numbers.

• Print the sum of the squares of the n numbers.

• Print the average of the n numbers.

• Print the median of the n numbers.

• Print the percentage of numbers greater than the average.

• Print the n numbers in increasing order.

• Print the n numbers in random order.

1.5.15 Write a program that takes three double command-line arguments x, y, and z, reads from standard input a sequence of point coordinates (x_i, y_i, z_i), and prints the coordinates of 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)². For efficiency, do not use Math.sqrt().

1.5.16 Given the positions and masses of a sequence of objects, write a program to compute their center-of-mass, or centroid. The centroid is the average position of the n objects, weighted by mass. If the positions and masses are given by (x_i, y_i, m_i), then the centroid (x, y, m) is given by

m = m₁ + m₂ + ... + m_n
x = (m₁ x₁ + ... + m_n x_n) / m
y = (m₁ y₁ + ... + m_n y_n) / m

1.5.17 Write a program that reads in a sequence of real numbers between –1 and +1 and prints 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 average 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.

1.5.18 Write a program that takes an integer command-line argument n and plots an n-by-n checkerboard with red and black squares. Color the lower-left square red.

1.5.19 Write a program that takes as command-line arguments an integer n and a floating-point number p (between 0 and 1), plots n equally spaced points on the circumference of a circle, and then, with probability p for each pair of points, draws a gray line connecting them.

1.5.20 Write code to draw hearts, spades, clubs, and diamonds. To draw a heart, draw a filled diamond, then attach two filled semicircles to the upper left and upper right sides.

1.5.21 Write a program that takes an integer command-line argument n and plots a rose with n petals (if n is odd) or 2n petals (if n is even), by plotting the polar coordinates (r, θ) of the function r = sin(n θ) for θ ranging from 0 to 2π radians.

1.5.22 Write a program that takes a string command-line argument s and displays it in banner style on the screen, moving from left to right and wrapping back to the beginning of the string as the end is reached. Add a second command-line argument to control the speed.

1.5.23 Modify PlayThatTune to take additional command-line arguments that control the volume (multiply each sample value by the volume) and the tempo (multiply each note’s duration by the tempo).

1.5.24 Write a program that takes the name of a .wav file and a playback rate r as command-line arguments and plays the file at the given rate. First, use StdAudio.read() to read the file into an array a[]. If r = 1, play a[]; otherwise, create a new array b[] of approximate size r times the length of a[]. If r < 1, populate b[] by sampling from the original; if r > 1, populate b[] by interpolating from the original. Then play b[].

1.5.25 Write programs that uses StdDraw to create each of the following designs.

1.5.26 Write a program Circles that draws filled circles of random radii at random positions in the unit square, producing images like those below. Your program should take four command-line arguments: the number of circles, the probability that each circle is black, the minimum radius, and the maximum radius.

1.5.28 Statistical polling. When collecting statistical data for certain political polls, it is very important to obtain an unbiased sample of registered voters. Assume that you have a file with n registered voters, one per line. Write a filter that prints a uniformly random sample of size m (see PROGRAM 1.4.1).

1.5.29 Terrain analysis. Suppose that a terrain is represented by a two-dimensional grid of elevation values (in meters). A peak is a grid point whose four neighboring cells (left, right, up, and down) have strictly lower elevation values. Write a program Peaks that reads a terrain from standard input and then computes and prints the number of peaks in the terrain.

1.5.30 Histogram. Suppose that the standard input stream is a sequence of double values. Write a program that takes an integer n and two real numbers lo and hi as command-line arguments and uses StdDraw to plot a histogram of the count of the numbers in the standard input stream that fall in each of the n intervals defined by dividing (lo, hi) into n equal-sized intervals.

1.5.31 Spirographs. Write a program that takes three double command-line arguments R, r, and a and draws the resulting spirograph. A spirograph (technically, an epicycloid) is a curve formed by rolling a circle of radius r around a larger fixed circle of radius R. If the pen offset 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)t /r)
y(t) = (R + r) sin (t) – (r + a) sin ((R + r)t /r)

Such curves were popularized by a best-selling toy that contains discs with gear teeth on the edges and small holes that you could put a pen in to trace spirographs.

1.5.32 Clock. Write a program 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.

1.5.33 Oscilloscope. Write a program that simulates the output of an oscilloscope and produces Lissajous patterns. These patterns 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 inputs are sinusoidal, so that the following parametric equations describe the curve:

x(t) = A_x sin (w_x t + θ_x)
y(t) = A _y sin (w_y t + θ_y)

Take the six arguments A_x,_, w_x,_, θ_x, A_y,_, w_y, and θ_y from the command line.

1.5.34 Bouncing ball with tracks. Modify BouncingBall to produce images like the ones shown in the text, which show the track of the ball on a gray background.

1.5.35 Bouncing ball with gravity. Modify BouncingBall to incorporate gravity in the vertical direction. Add calls to StdAudio.play() to add a sound effect when the ball hits a wall and a different sound effect when it hits the floor.

1.5.36 Random tunes. Write a program that uses StdAudio to play random tunes. Experiment with keeping in key, assigning high probabilities to whole steps, repetition, and other rules to produce reasonable melodies.

1.5.37 Tile patterns. Using your solution to EXERCISE 1.5.25, write a program TilePattern that takes an integer command-line argument n and draws an n-by-n pattern, using the tile of your choice. Add a second command-line argument that adds a checkerboard option. Add a third command-line argument for color selection. Using the patterns on the facing page as a starting point, design a tile floor. Be creative! Note: These are all designs from antiquity that you can find in many ancient (and modern) buildings.

The model is known as the random surfer model, and is simple to describe. We consider the web to be a fixed set of web pages, with each page containing a fixed set of hyperlinks, and each link a reference to some other page. (For brevity, we use the terms pages and links.) We study what happens to a web surfer who randomly moves from page to page, either by typing a page name into the address bar or by clicking a link on the current page.

The mathematical model that underlies the link structure of the web is known as the graph, which we will consider in detail at the end of the book (in SECTION 4.5). We defer discussion about processing graphs until then. Instead, we concentrate on calculations associated with a natural and well-studied probabilistic model that accurately describes the behavior of the random surfer.

The first step in studying the random surfer model is to formulate it more precisely. The crux of the matter is to specify what it means to randomly move from page to page. The following intuitive 90–10 rule captures both methods of moving to a new page: Assume that 90% of the time the random surfer clicks a random link on the current page (each link chosen with equal probability) and that 10% of the time the random surfer goes directly to a random page (all pages on the web chosen with equal probability).

You can immediately see that this model has flaws, because you know from your own experience that the behavior of a real web surfer is not quite so simple:

• No one chooses links or pages with equal probability.

• There is no real potential to surf directly to each page on the web.

• The 90–10 (or any fixed) breakdown is just a guess.

• It does not take the back button or bookmarks into account.

Despite these flaws, the model is sufficiently rich that computer scientists have learned a great deal about properties of the web by studying it. To appreciate the model, consider the small example on the previous page. Which page do you think the random surfer is most likely to visit?

Each person using the web behaves a bit like the random surfer, so understanding the fate of the random surfer is of intense interest to people building web infrastructure and web applications. The model is a tool for understanding the experience of each of the billions of web users. In this section, you will use the basic programming tools from this chapter to study the model and its implications.

Later in the book, you will learn how to read web pages in Java programs (SECTION 3.1) and to convert from names to numbers (SECTION 4.4) as well as other techniques for efficient graph processing. For now, we assume that there are n web pages, numbered from 0 to n-1, and we represent links with ordered pairs of such numbers, the first specifying the page containing the link and the second specifying the page to which it refers. Given these conventions, a straightforward input format for the random surfer problem is an input stream consisting of an integer (the value of n) followed by a sequence of pairs of integers (the representations of all the links). StdIn treats all sequences of whitespace characters as a single delimiter, so we are free to either put one link per line or arrange them several to a line.

• Read n, and then create arrays counts[][] and outDegrees[].

• Read the links and accumulate counts so that counts[i][j] counts the links from i to j and outDegrees[i] counts the links from i to anywhere.

• Use the 90–10 rule to compute the probabilities.

The first two steps are elementary, and the third is not much more difficult: multiply counts[i][j] by 0.90/outDegree[i] if there is a link from i to j (take a random link with probability 0.9), and then add 0.10/n to each element (go to a random page with probability 0.1). Transition (PROGRAM 1.6.1) performs this calculation: it is a filter that reads a graph from standard input and prints the associated transition matrix to standard output.

The transition matrix is significant because each row represents a discrete probability distribution—the elements fully specify the behavior of the random surfer’s next move, giving the probability of surfing to each page. Note in particular that the elements sum to 1 (the surfer always goes somewhere).

The output of Transition defines another file format, one for matrices: the numbers of rows and columns followed by the values of the matrix elements, in row-major order. Now, we can write programs that read and process transition matrices.

public class Transition
{
   public static void main(String[] args)
   {
      int n = StdIn.readInt();
      int[][] counts = new int[n][n];
      int[] outDegrees = new int[n];
      while (!StdIn.isEmpty())
      {  // Accumulate link counts.
         int i = StdIn.readInt();
         int j = StdIn.readInt();
         outDegrees[i]++;
         counts[i][j]++;
      }

      StdOut.println(n + " " + n);
      for (int i = 0; i < n; i++)
      {  // Print probability distribution for row i.
         for (int j = 0; j < n; j++)
         {  // Print probability for row i and column j.
            double p = 0.9*counts[i][j]/outDegrees[i] + 0.1/n;
            StdOut.printf("%8.5f", p);
         }
         StdOut.println();
      }
   }
}

      n       | number of pages
 counts[i][j] | count of links from page i to page j
outDegrees[i] | count of links from page i to anywhere
      p       | transition probability

% more tinyG.txt
5
0 1
1 2  1 2
1 3  1 3  1 4
2 3
3 0
4 0  4 2

% java Transition < tinyG.txt
5 5
 0.02000 0.92000 0.02000 0.02000 0.02000
 0.02000 0.02000 0.38000 0.38000 0.20000
 0.02000 0.02000 0.02000 0.92000 0.02000
 0.92000 0.02000 0.02000 0.02000 0.02000
 0.47000 0.02000 0.47000 0.02000 0.02000

Click here to view code image

double sum = 0.0;
for (int j = 0; j < n; j++)
{  // Find interval containing r.
   sum += p[page][j];
   if (r < sum) { page = j; break; }
}

The variable sum tracks the endpoints of the intervals defined in row page, and the for loop finds the interval containing the random value r. For example, suppose that the surfer is at page 4 in our example. The transition probabilities are 0.47, 0.02, 0.47, 0.02, and 0.02, and sum takes on the values 0.0, 0.47, 0.49, 0.96, 0.98, and 1.0. These values indicate that the probabilities define the five intervals (0, 0.47), (0.47, 0.49), (0.49, 0.96), (0.96, 0.98), and (0.98, 1), one for each page. Now, suppose that Math.random() returns the value 0.71. We increment j from 0 to 1 to 2 and stop there, which indicates that 0.71 is in the interval (0.49, 0.96), so we send the surfer to page 2. Then, we perform the same computation start at page 2, and the random surfer is off and surfing. For large n, we can use binary search to substantially speed up this computation (see EXERCISE 4.2.38). Typically, we are interested in speeding up the search in this situation because we are likely to need a huge number of random moves, as you will see.

public class RandomSurfer
{
   public static void main(String[] args)
   {  // Simulate random surfer.
      int trials = Integer.parseInt(args[0]);
      int n = StdIn.readInt();
      StdIn.readInt();

      // Read transition matrix.
      double[][] p = new double[n][n];
      for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
            p[i][j] = StdIn.readDouble();

      int page = 0;
      int[] freq = new int[n];
      for (int t = 0; t < trials; t++)
      {  // Make one random move to next page.
         double r = Math.random();
         double sum = 0.0;
         for (int j = 0; j < n; j++)
         {  // Find interval containing r.
            sum += p[page][j];
            if (r < sum) { page = j; break; }
         }
         freq[page]++;
      }

      for (int i = 0; i < n; i++)     // Print page ranks.
         StdOut.printf("%8.5f", (double) freq[i] / trials);
      StdOut.println();
    }
}

 trials | number of moves
   n    | number of pages
  page  | current page
p[i][j] | probability that the surfer moves from page i to page j
freq[i] | number of times the surfer hits page i

% java Transition < tinyG.txt | java RandomSurfer 100
 0.24000 0.23000 0.16000 0.25000 0.12000
% java Transition < tinyG.txt | java RandomSurfer 1000000
0.27324 0.26568 0.14581 0.24737 0.06790

Accurate page rank estimates for the web are valuable in practice for many reasons. First, using them to put in order the pages that match the search criteria for web searches proved to be vastly more in line with people’s expectations than previous methods. Next, this measure of confidence and reliability led to the investment of huge amounts of money in web advertising based on page ranks. Even in our tiny example, page ranks might be used to convince advertisers to pay up to four times as much to place an ad on page 0 as on page 4. Computing page ranks is mathematically sound, an interesting computer science problem, and big business, all rolled into one.

Click here to view code image

StdDraw.clear();
for (int i = 0; i < n; i++)
   StdDraw.filledRectangle(i, freq[i]/2.0, 0.25, freq[i]/2.0);
StdDraw.show();
StdDraw.pause(10);

to the random move loop; and run RandomSurfer for a large number of trials, then you will see a drawing of the frequency histogram that eventually stabilizes to the page ranks. After you have used this tool once, you are likely to find yourself using it every time you want to study a new model (perhaps with some minor adjustments to handle larger models).

Directly simulating the behavior of a random surfer to understand the structure of the web is appealing, but it has limitations. Think about the following question: could you use it to compute page ranks for a web graph with millions (or billions!) of web pages and links? The quick answer to this question is no, because you cannot even afford to store the transition matrix for such a large number of pages. A matrix for millions of pages would have trillions of elements. Do you have that much space on your computer? Could you use RandomSurfer to find page ranks for a smaller graph with, say, thousands of pages? To answer this question, you might run multiple simulations, record the results for a large number of trials, and then interpret those experimental results. We do use this approach for many scientific problems (the gambler’s ruin problem is one example; SECTION 2.4 is devoted to another), but it can be very time-consuming, as a huge number of trials may be necessary to get the desired accuracy. Even for our tiny example, we saw that it takes millions of iterations to get the page ranks accurate to three or four decimal places. For larger graphs, the required number of iterations to obtain accurate estimates becomes truly huge.

[1.0 0.0 0.0 0.0 0.0 ]

which specifies that the random surfer starts on page 0. Multiplying this vector by the transition matrix gives the vector

[.02 .92 .02 .02 .02 ]

which is the probabilities that the surfer winds up on each of the pages after one step. Now, multiplying this vector by the transition matrix gives the vector

[.05 .04 .36 .37 .19 ]

which contains the probabilities that the surfer winds up on each of the pages after two steps. For example, the probability of moving from 0 to 2 in two moves is the probability of moving from 0 to 0 to 2 (0.02 × 0.02), plus the probability of moving from 0 to 1 to 2 (0.92 × 0.38), plus the probability of moving from 0 to 2 to 2 (0.02 × 0.02), plus the probability of moving from 0 to 3 to 2 (0.02 × 0.02), plus the probability of moving from 0 to 4 to 2 (0.02 × 0.47), which adds up to a grand total of 0.36. From these initial calculations, the pattern is clear: the vector giving the probabilities that the random surfer is at each page after t steps is precisely the product of the corresponding vector for t –1 steps and the transition matrix. By the basic limit theorem for Markov chains, this process converges to the same vector no matter where we start; in other words, after a sufficient number of moves, the probability that the surfer ends up on any given page is independent of the starting point. Markov (PROGRAM 1.6.3) is an implementation that you can use to check convergence for our example. For instance, it gets the same results (the page ranks accurate to two decimal places) as RandomSurfer, but with just 20 matrix–vector multiplications instead of the tens of thousands of iterations needed by RandomSurfer. Another 20 multiplications gives the results accurate to three decimal places, as compared with millions of iterations for RandomSurfer, and just a few more give the results to full precision (see EXERCISE 1.6.6).

public class Markov
{  //  Compute page ranks after trials moves.
   public static void main(String[] args)
   {
      int trials = Integer.parseInt(args[0]);
      int n = StdIn.readInt();
      StdIn.readInt();

      // Read transition matrix.
      double[][] p = new double[n][n];
      for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
            p[i][j] = StdIn.readDouble();

      // Use the power method to compute page ranks.
      double[] ranks = new double[n];
      ranks[0] = 1.0;
      for (int t = 0; t < trials; t++)
      {  // Compute effect of next move on page ranks.
         double[] newRanks = new double[n];
         for (int j = 0; j < n; j++)
         {  //  New rank of page j is dot product
            //  of old ranks and column j of p[][].
            for (int k = 0; k < n; k++)
               newRanks[j] += ranks[k]*p[k][j];
         }

         for (int j = 0; j < n; j++)  // Update ranks[].
            ranks[j] = newRanks[j];
      }

      for (int i = 0; i < n; i++)     // Print page ranks.
         StdOut.printf("%8.5f", ranks[i]);
      StdOut.println();
   }
}

   trials  | number of moves
     n     | number of pages
   p[][]   | transition matrix
  ranks[]  | page ranks
newRanks[] | new page ranks

% java Transition < tinyG.txt | java Markov 20
 0.27245 0.26515 0.14669 0.24764 0.06806
% java Transition < tinyG.txt | java Markov 40
 0.27303 0.26573 0.14618 0.24723 0.06783

Markov chains are well studied, but their impact on the web was not truly felt until 1998, when two graduate students—Sergey Brin and Lawrence Page—had the audacity to build a Markov chain and compute the probabilities that a random surfer hits each page for the whole web. Their work revolutionized web search and is the basis for the page ranking method used by Google, the highly successful web search company that they founded. Specifically, their idea was to present to the user a list of web pages related to their search query in decreasing order of page rank. Page ranks (and related techniques) now predominate because they provide users with more relevant web pages for typical searches than earlier techniques (such as ordering pages by the number of incoming links). Computing page ranks is an enormously time-consuming task, due to the huge number of pages on the web, but the result has turned out to be enormously profitable and well worth the expense.

Perhaps the most important lesson to learn from writing programs for complicated problems like the example in this section is that debugging is difficult. The polished programs in the book mask that lesson, but you can rest assured that each one is the product of a long bout of testing, fixing bugs, and running the programs on numerous inputs. Generally we avoid describing bugs and the process of fixing them in the text because that makes for a boring account and overly focuses attention on bad code, but you can find some examples and descriptions in the exercises and on the booksite.

1.6.2 Modify Transition to ignore the effect of multiple links. That is, if there are multiple links from one page to another, count them as one link. Create a small example that shows how this modification can change the order of page ranks.

1.6.3 Modify Transition to handle pages with no outgoing links, by filling rows corresponding to such pages with the value 1/n, where n is the number of columns.

1.6.4 The code fragment in RandomSurfer that generates the random move fails if the probabilities in the row p[page] do not add up to 1. Explain what happens in that case, and suggest a way to fix the problem.

1.6.5 Determine, to within a factor of 10, the number of iterations required by RandomSurfer to compute page ranks accurate to 4 decimal places and to 5 decimal places for tiny.txt.

1.6.6 Determine the number of iterations required by Markov to compute page ranks accurate to 3 decimal places, to 4 decimal places, and to ten 10 places for tiny.txt.

1.6.7 Download the file medium.txt from the booksite (which reflects the 50-page example depicted in this section) and add to it links from page 23 to every other page. Observe the effect on the page ranks, and discuss the result.

1.6.8 Add to medium.txt (see the previous exercise) links to page 23 from every other page, observe the effect on the page ranks, and discuss the result.

1.6.9 Suppose that your page is page 23 in medium.txt. Is there a link that you could add from your page to some other page that would raise the rank of your page?

1.6.10 Suppose that your page is page 23 in medium.txt. Is there a link that you could add from your page to some other page that would lower the rank of that page?

1.6.11 Use Transition and RandomSurfer to determine the page ranks for the eight-page graph shown below.

1.6.12 Use Transition and Markov to determine the page ranks for the eight-page graph shown below.

1.6.14 Random web. Write a generator for Transition that takes as command-line arguments a page count n and a link count m and prints to standard output n followed by m random pairs of integers from 0 to n-1. (See SECTION 4.5 for a discussion of more realistic web models.)

1.6.15 Hubs and authorities. Add to your generator from the previous exercise a fixed number of hubs, which have links pointing to them from 10% of the pages, chosen at random, and authorities, which have links pointing from them to 10% of the pages. Compute page ranks. Which rank higher, hubs or authorities?

1.6.16 Page ranks. Design a graph in which the highest-ranking page has fewer links pointing to it than some other page.

1.6.17 Hitting time. The hitting time for a page is the expected number of moves between times the random surfer visits the page. Run experiments to estimate the hitting times for tiny.txt, compare hitting times with page ranks, formulate a hypothesis about the relationship, and test your hypothesis on medium.txt.

1.6.18 Cover time. Write a program that estimates the time required for the random surfer to visit every page at least once, starting from a random page.

1.6.19 Graphical simulation. Create a graphical simulation where the size of the dot representing each page is proportional to its page rank. To make your program data driven, design a file format that includes coordinates specifying where each page should be drawn. Test your program on medium.txt.