1.4 Arrays
In this section, we consider a fundamental construct known as the array. An array stores a sequence of values that are all of the same type. We want not just to store values but also to be able to quickly access each individual value. The method that we use to refer to individual values in an array is to number and then index them—if we have N values, we think of them as being numbered from 0 to N1.
Typical arrayprocessing code.
Given two vectors of the same length, their dot product is the sum of the products of their corresponding components. If we represent the two vectors as onedimensional arrays x[] and y[] that are each of length N and of type double, their dot product is easy to compute:For example, following trace shows the computation of the dot product of two vectors of length 3.
double sum = 0.0; for (int i = 0; i < N; i++) sum += x[i]*y[i];
Arrays.java contains typical examples of using arrays in Java.
Programming with arrays.
Before considering more examples, we consider a number of important characteristics of programming with arrays. Zerobased indexing. We always refer to the first element of an array a[] as a[0], the second as a[1], and so forth. It might seem more natural to you to refer to the first element as a[1], the second value as a[2], and so forth, but starting the indexing with 0 has some advantages and has emerged as the convention used in most modern programming languages.
 Array length. Once we create an array, its size is fixed. You can refer to the length of an a[] in your program with the code a.length.
 Memory representation. When you use new to create an array, Java reserves space in memory for it (and initializes the values). This process is called memory allocation.
 Bounds checking. When programming with arrays, you must be careful. It is your responsibility to use legal indices when accessing an array element.
 Setting array values at compile time.
When we have a small number of literal values
that we want to keep in array, we can initialize it by listing the values between
curly braces, separated by a comma. For example, we might use the
following code in a program that processes playing cards.
String[] suit = { "Clubs", "Diamonds", "Hearts", "Spades" }; String[] rank = { "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace" }
int i = (int) (Math.random() * rank.length); int j = (int) (Math.random() * suit.length); System.out.println(rank[i] + " of " + suit[j]);
 Setting array values at run time.
A more typical situation is when we wish to compute
the values to be stored in an array
For example, we might use the following
code to initialize an array of size 52 that represents a deck of playing cards,
using the arrays rank[] and suit[] just defined.
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] = rank[i] + " of " + suit[j]; System.out.println(rank[i] + " of " + suit[j]);
Shuffling and sampling.
Now we describe some useful algorithms for rearranging the elements in an array. Exchange.
Frequently, we wish to exchange two values in an array. Continuing
our example with playing cards, the following code exchanges the
card at position i and the card at position j:
String t = deck[i]; deck[i] = deck[j]; deck[j] = t;
 Shuffling.
The following code shuffles our deck of cards:
int N = deck.length; for (int i = 0; i < N; i++) { int r = i + (int) (Math.random() * (Ni)); String t = deck[r]; deck[r] = deck[i]; deck[i] = t; }
 Hardwired constants. It is a bad idea to hardwire magic values like 4 and 13 and 52 into your program. Such magic values tend to get sprinkled throughout your program, making your program significantly harder to maintain. Instead, create a variable for each constant, give it a meaningful name, and use it consistently. Program Deck.java contains the full program from the previous example, avoiding magic constants.
 Sampling without replacement. In many situations, we want to draw a random sample from a set such that each member of the set appears at most once in the sample. Sample.java takes two commandline arguments M and N, and creates a permutation of size N whose first M entries comprise a random sample. See the textbook for details.
Cleaning up repetitive code.
Another simple application of arrays is to shorten and simplify repetitive code. As an example, consider the following code fragment which prints out the name of a month given its number (1 for January, 2 for February, and so forth).
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 a String array consisting of the names of each month:
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.
Precomputed values.
One simple application of arrays is to save values that you have computed, for later use. As an example, suppose that you are writing a program that performs calculations using small values of the harmonic numbers. One easy way to accomplish such a task is to save the values in an array with the following codeand then simply use the code H[i] to refer to any of the values. Precomputing values in this way in an example of a spacetime 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 a huge number of values for small N.
double[] H = new double[N]; for (int i = 1; i < N; i++) H[i] = H[i1] + 1.0/i;
Coupon collector.
Suppose that you have a shuffled deck of cards and you turn them face up, one by one. How many cards do you need to turn up before you have seen one of each suit? This is an example of the famous coupon collector problem. In general, suppose that a trading card company issues trading cards with N different possible cards: how many do you have to collect before you have all N possibilities, assuming that each possibility is equally likely for each card that you collect?Program CouponCollector.java is an example program that simulates this process. See the textbook for details.
Sieve of Eratosthenes.
The prime counting function π(N) is the number of primes less than or equal to N. For example &pi(17) = 7 since the first seven primes are 2, 3, 5, 7, 11, 13, and 17. Program PrimeSieve.java takes a command line integer N and computes π(N) using the Sieve of Eratosthenes. See the textbook for details.Twodimensional arrays.
In many applications, a natural way to organize information is to use a table of numbers organized in a rectangle and to refer to rows and columns in the table. The mathematical abstraction corresponding to such tables is a matrix; the corresponding Java construct is a twodimensional array. Twodimensional arrays in Java.
To refer to the element in row i
and column j of a twodimensional array a[][],
we use the notation a[i][j]; to declare a twodimensional
array, we add another pair of brackets; to create the array, we
specify the number of rows followed by the number of columns after the
type name (both within brackets), as follows:
double[][] a = new double[M][N];
 Initialization.
Default initialization of twodimensional arrays is useful
because it masks more code than for onedimensional arrays. To access
each of the elements in a twodimensional array, we need nested loops:
double[][] a; a = new double[M][N]; for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) a[i][j] = 0;
 Memory representation. Java represents a twodimensional array as an array of arrays. A matrix with M rows and N columns is actually an array of length M, each entry of which is an array of length N. In a twodimensional Java array, we can use the code a[i] to refer to the ith row (which is a onedimensional array). Enables ragged arrays.
 Setting values at compile time.
The following code initializes the array a[][] to our sample values.
int[][] a = { { 99, 85, 98 }, { 98, 57, 78 }, { 92, 77, 76 }, { 94, 32, 11 }, { 99, 34, 22 }, { 90, 46, 54 }, { 76, 59, 88 }, { 92, 66, 89 }, { 97, 71, 24 }, { 89, 29, 38 } };
 Ragged arrays.
There is no requirement that all rows in a twodimensional array have
the same length—an array with rows of nonuniform length is known
as a ragged array. The possibility of ragged arrays creates the need for more
care in crafting arrayprocessing code. For example, this code prints the
contents of a ragged array:
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(); }
 Multidimensional arrays.
The same notation extends to arrays that have any number of dimensions.
For instance, we can declare and initialize a threedimensional array with the code
double[][][] a = new double[N][N][N];
Matrix operations.
Typical applications in science and engineering involve implementing variouls mathematical operations with matrix operands. For example, we can add two NbyN matrices as follows:
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, we can multiply two matrices. Each entry 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[].
double[][] c = new double[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { c[i][j] += a[i][k]*b[k][j]; } } }
Selfavoiding walk.
An application of twodimensional arrays to chemistry. See textbook for details. SelfAvoiding.java.
Q + A
Q. Some Java programmers use int a[] instead of int[] a to declare arrays. What's the difference?
A. In Java, both are legal and 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 machinelanguage 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. Here's Edsger Dijkstra's explanation.
Q. What happens if I use a negative number to index an array?
A. The same thing as when you use an index that is too big. Whenever a program attempts to index an array with an index that is not between zero and the array length minus one, Java will issue an ArrayIndexOutOfBoundsException and terminate the program.
Q. What other pitfalls should I watch out for when using arrays?
A. It is very important to remember that Java always initializes arrays when you create them, so that creating an array takes time proportional to the size of the array.
Q. What happens when a random walk does not avoid itself?
A. This case is wellunderstood. It is a twodimensional version of the gambler's ruin problem. See Exercise 1.3.35.
Q. If a[] is an array, why does System.out.println(a) print out a hexadecimal integer, like @f62373, instead of the elements of the array?
A. Good question. It is printing out the memory address of the array, which, unfortunately, is rarely what you want.
Exercises
 Write a program that declares and initializes an array a[] of size 1000 and accesses a[1000]. Does your program compile? What happens when you run it?

Describe and explain what happens when you try to compile a program
HugeArray.java with the following statement:
int N = 1000; int[] a = new int[N*N*N*N];
 Given two vectors of length N that are represented with onedimensional 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 entries).

Write a code fragment that reverses the order of a onedimensional
array a[] of double values.
Do not create another array to hold the
result. Hint: Use the code in the text for exchanging
two elements.
Solution.
int N = a.length; for (int i = 0; i < N/2; i++) { double temp = a[Ni1]; a[Ni1] = a[i]; a[i] = temp; }

What is wrong with the following code fragment?
int[] a; for (int i = 0; i < 10; i++) a[i] = i * i;
Solution: It does not allocate memory for a[] with new. The code results in a variable might not have been initialized compiletime error.
 Write a code fragment that prints the contents of a twodimensional boolean array, using * to represent true and a space to represent false. Include row and column numbers.

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]);

What values does the following code put in the array a[]?
int N = 10; int[] a = new int[N]; a[0] = 0; a[1] = 1; for (int i = 2; i < N; i++) a[i] = a[i1] + a[i2];

What does the following code fragment print?
int[] a = { 1, 2, 3 }; int[] b = { 1, 2, 3 }; System.out.println(a == b);
 Write a program Deal.java that takes an commandline argument N and prints N poker hands (five cards each) from a shuffled deck, separated by blank lines.

Write code fragments to create a twodimensional array b[][] that is a
copy of an existing twodimensional array a[][],
under each of the following assumptions:
 a[][] is square
 a[][] is rectangular
 a[][] may be ragged

Write a code fragment to print the transposition (rows and columns
changed) of a square twodimensional array. For the example spreadsheet array in
the text, you code would print the following:
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
 Write a code fragment Transpose.java to transpose a square twodimensional array in place without creating a second array.
 Write a program that takes an integer N from the command line and creates an NbyN 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.
 Write a program that computes the product of two square matrices of boolean values, using the or operation instead of + and the and operation instead of *.

Modify the spreadsheet code fragment in the text to compute a weighted
average of the rows, where the weights of each test score are in a onedimensional
array weights[].
For example, to assign the last of the three tests in our example to
be twice the weight of the others, you would use
double[] weights = { .25, .25, .50 };
 Write a code fragment to multiply two rectangular matrices that are not necessarily square. Note: For the dot product to be welldefined, 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.
 Modify SelfAvoidingWalk.java to calculate and print the average length of the paths as well as the deadend probability. Keep separate the average lengths of escape paths and deadend paths.
 Modify SelfAvoidingWalk.java to calculate and print the average area of the smallest axisoriented rectangle that encloses the path. Keep separate statistics for escape paths and deadend paths.
Creative Exercises
 Dice simulation.
The following code computes the exact probability distribution for the sum of two dice:
double[] dist = new double[13]; for (int i = 1; i <= 6; i++) for (int j = 1; j <= 6; j++) dist[i+j] += 1.0; for (int k = 1; k <= 12; k++) dist[k] /= 36.0;
 Longest plateau. Given an array of integers, find the length and location of the longest contiguous sequence of equal values where the values of the elements just before and just after this sequence are smaller.
 Empirical shuffle check. Run computational experiments to check that our shuffling code works as advertised. Write a program ShuffleTest that takes commandline arguments M and N, does N shuffles of an array of size M that is initialized with a[i] = i before each shuffle, and prints an MbyM table such that row i gives the number of times i wound up in position j for all j. All entries in the array should be close to N/M.
 Bad shuffling.
Suppose that you choose a random integer between 0 and
N1 in our shuffling code instead of one between i and N1. 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.
Partial solution: when N = 3, all 3! = 6 outcomes are possible, but some are more likely:
ABC ACB BAC BCA CAB CBA 4/27 5/27 6/27 4/27 5/27 3/27  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).
 Inverse permutation. Write a program InversePermutation.java that reads in a permutation of the integers 0 to N1 from N commandline 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.
 Hadamard matrix.
The NbyN Hadamard H(N) matrix is a boolean matrix with the remarkable
property that any two rows differ in exactly N/2 bits.
(This property makes it useful for designing errorcorrecting codes.)
H(1) is a 1by1 matrix with the single entry 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 entries in the lower right NbyN copy, as shown in the
following examples (with T representing true and F representing false, as usual).
H(1) H(2) H(4)  T T T T T T T T 0 T 0 T 0 T T 0 0 T 0 0 T
 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 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.
 Find a duplicate. Given an array of N elements with each element between 1 and N, write an algorithm to determine whether there are any duplicates. You do not need to preserve the contents of the given array, but do not use an extra array.
 Counting primes. Compare PrimeSieve.java 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 timespace tradeoff: PrimeSieve is fast, but requires a boolean array of size 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 PrimeSieve 1000000.
 Minesweeper.
Write a program Minesweeper.java
that takes 3 commandline arguments M, N, and p and produces an MbyN boolean
array where each entry 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, replace each safe square with the number of neighboring bombs
(above, below, left, right, or diagonal) and print out the solution.
* * . . . * * 1 0 0 . . . . . 3 3 2 0 0 . * . . . 1 * 1 0 0
Try to 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.
 Selfavoiding walk length. Suppose that there is no limit on the size of the grid. Run experiments to estimate the average walk length.
 Threedimensional selfavoiding walks. Run experiments to verify that the deadend probability is 0 for a threedimensional selfavoiding walk and to compute the average walk length for various values of N.
 Random walkers. Suppose that N random walkers, starting in the center of an NbyN grid, move one step at a time, choosing to go left, right, up, or down with equal probability at each step. Write a program RandomWalkers.java to help formulate and test a hypothesis about the number of steps taken before all cells are touched.
 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, 5332, 4432, or 4333?
 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? Write a program Birthday.java to simulate one experiment. Write a program Birthdays.java to repeat the experiment many times and estimate the average value. Assume birthdays to be uniform random integers between 0 and 364.
 Coupon collector. Run experiments to validate the classical mathematical result that the expected number of coupons needed to collect N values is about N * H_N = N * (1 + 1/2 + 1/3 + ... + 1/N). 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 about 235 cards are dealt, on average, before seeing every card value.
 Binomial coefficients. Write a program
BinomialDistribution.java
that builds and prints a twodimensional
ragged array a such that a[N][k] contains the probability that you get exactly
k heads when you toss a coin N times. Take a commandline argument to specify the
maximum value of N. These numbers are known as the binomial distribution: if you
multiply each entry in row i by 2^N, you get the binomial coefficients (the coefficients
of x^k in (x+1)^N) arranged in Pascal's triangle. To compute them, start with
a[N][0] = 0 for all N and a[1][1] = 1,
then compute values in successive rows, left to right,
with a[N][k] = (a[N1][k] + a[N1][k1]) / 2.
Pascal's triangle Binomial distribution 1 1 1 1 1/2 1/2 1 2 1 1/4 1/2 1/4 1 3 3 1 1/8 3/8 3/8 1/8 1 4 6 4 1 1/16 1/4 3/8 1/4 1/16
Web Exercises
 Write a program HowMany.java that takes a variable number of commandline arguments and prints out how many there are.
 Discrete distribution. Write a program DiscreteDistribution.java that takes a variable number of integer commandline arguments and outputs the integer i with probability proportional to the ith commandline argument.
 Birthday problem. Modify Birthday.java so that it compute the probability that two people have a birthday within a day of each other.
 Above average. 90% of incoming college students rate themselves as above average. Write a program AboveAverage.java that takes a commandline argument N, reads in N integers from standard input, and prints out the fraction of values that are strictly above the average value.
 Random permutation.
Write a program Permutation.java
so that it takes a commandline argument N and prints a
random permutation of the integers 0 through N1.
Also print out a checkerboard visualization
of the permutation. As an example, the permutation
{ 4, 1, 3, 0, 2 } corresponds to:
4 1 3 0 2 * * * Q * * Q * * * * * * * Q * * Q * * Q * * * *
 8 queens checker.
A permutation of the integer 0 to N1 corresponds to a placement of
queens on an NbyN chessboard so that no two queens are in the same row
or column. Write a program
QueensChecker.java that determines
whether or not a permutation corresponds to a placement of
queens so that no two are in the same row, column, or diagonal.
As an example, the permutation { 4, 1, 3, 0, 2 } is a legal
placement:
* * * Q * * Q * * * * * * * Q * * Q * * Q * * * *
Try to do it without using any extra arrays besides the length N input permutation q. Hint: to determine whether setting q[i] conflicts with q[j] for i < j.
 if q[i] equals q[j]: two queens are placed in the same column
 if q[i]  q[j] equals j  i: two queens are on same major diagonal
 if q[j]  q[i] equals j  i: two queens are on same minor diagonal
 Finding your beer. A large number of college students are attending a party. Each guest is drinking a can of beer (or soda of they are under 21). An emergency causes the lights to go out and the fire alarm to go off. The guests calmly put down their beer and exit the building. When the alarm goes off, they reenter and try to retrieve their beer. However, the lights are still off, so each student randomly grabs a bottle of beer. What are the chances that at least one student gets his or her original beer? Write a program MyBeer.java that takes a commandline argument N and runs 1,000 simulations this event, assuming their are N guests. Print out the fraction of times that at least one guest gets their original beer. As N gets large, does this fraction approach 0 or 1 or something in between?
 Linear feedback shift register. Rewrite linear feedback shift register from Chapter 1 by using an array to streamline it and makes it more extensible, e.g., if the number of cells in the shift register increases. Program LFSR.java uses a boolean Hint: use the ^ operator to take the exclusive or of two boolean values.
 Lockers. Your are in a locker room with 100 open lockers, numbered 1 to 100. Toggle all of the lockers that are even. By toggle, we mean close if it is open, and open if it is closed. Now toggle all of the lockers that are multiples of three. Repeat with multiples of 4, 5, up to 100. How many lockers are open? Answer: lockers 1, 4, 9, 16, 25, ..., 100 will be open. Guess you don't need an array once you see the pattern.
 Scheduling with deadline. Suppose that you have N tasks to schedule. Each task takes 1 unit of time and has a deadline by which time it is expected to finish. If a task is not completed by its deadline, you pay a $1,000 fine. Find a schedule that minimizes the penalty. Hint: schedule the tasks in order of their deadline, but don't bother with any task that won't finish by its deadline.
 Calendar. Repeat Exercise 1.33 to produce a calendar for a given month and year. Use arrays to store the names of the days of the week, the names of the months, and the number of days in a month.
 Connect Four. Given an NbyN grid with each cell either occupied by an 'X', an 'O', or empty, write a program to find the longest sequence of consecutive 'X's either horizontal, vertically, or diagonally. To test your program, you can create a random grid where each cell contains an 'X' or 'O' with probability 1/3.
 Thai kickboxing. Write a program
KickBoxer.java that takes
an integer weight w as a command line input and prints out the
corresponding kickboxing weightclass according to the table below.
weight class from to  Fly Weight 0 112 Super Fly Weight 112 115 Bantam Weight", 115 118 Super Bantam Weight 118 122 Feather Weight 122 126 Super Feather Weight 126 130 Light Weight 130 135 Super Light Weight 135 140 Welter Weight 140 147 Super Welter Weight 147 154 Middle Weight 154 160 Super Middle Weight 160 167 Light Heavy Weight 167 174 Super Light Heavy Weight 174 183 Cruiser Weight 183 189 Super Cruiser Weight 189 198 Heavy Weight 198 209 Super Heavy Weight 209
 Nary counter. Write a program that counts in base N from 0 to N^{20}  1. Use an array of 20 elements.
 Terrain analysis. Given an NbyN grid of elevation values (in meters), a peak is a grid point for which all four neighboring cells are strictly lower. Write a code fragment that counts the number of peaks in a given NbyN grid.
 Magic squares.
Write a program MagicSquare.java
that reads in an odd integer N from the command line and prints
out an NbyN magic square. The square contains each of the integers between
1 and N^2 exactly once, such that all row sums, column sums, and diagonal
sums are equal.
4 9 2 11 18 25 2 9 3 5 7 10 12 19 21 3 8 1 6 4 6 13 20 22 23 5 7 14 16 17 24 1 8 15
One simple algorithm is to assign the integers 1 to N^2 in ascending order, starting at the bottom, middle cell. Repeatedly assign the next integer to the cell adjacent diagonally to the right and down. If this cell has already been assigned another integer, instead use the cell adjacently above. Use wraparound to handle border cases.
 Banner.
Write a program Banner.java that takes a string as a command
line argument and prints out the string in large letters as below.
% java Banner "Kevin" # # ###### # # # # # # # # # # # ## # #### ##### # # # # # # # # # # # # # # # # # # # # # # ## # # ###### ## # # #
 Voting and social choice theory. Plurality (US presidential election), runoff elections, sequential runoff elections (Australia, Ireland, Princeton faculty committees), Condorcet. Kemeny rank aggregation. Arrow's impossibility theorem. Same ideas for sports, google, metasearch, machine learning
 Borda count. In 1781, Borda proposed a positional method for determining the outcome of a political election with K voters and N candidates. Each voter ranks the candidates in increasing order of preference (from 1 to N). Borda's method assigns a score to each candidate equal to the sum of their rankings. The candidate with the highest sum wins. This is used in Major League Baseball to determine the MVP.
 Kendall's tau distance. Given two permutations, Kendall's tau distance is the number of pairs out of position. "Bubblesort metric." Useful in topk lists. Optimal Kemeny rank aggregation in voting theory minimizes Kendall tau distance. Also useful for ranking genes using several expression profiles, ranking search engine results, etc.
 Spearman's footrule distance.
Given two permutations, Spearman's footrule distance is the L1
distance between the permutations as vectors.
Useful in topk lists.
int footrule = 0; for (int i = 0; i < N; i++) footrule = footrule + Math.abs(p[i]  q[i]);
 US postal barcodes.
The POSTNET
barcode is used by the US Postal System to route mail.
Each decimal digit in the zip code is encoded using
a sequence of 5 short and long lines for use by scanners as follows:
VALUE ENCODING 0 ╷╷╷
1 ╷╷╷
2 ╷╷╷
3 ╷╷╷
4 ╷╷╷
5 ╷╷╷
6 ╷╷╷
7 ╷╷╷
8 ╷╷╷
9 ╷╷╷
A sixth checksum digit is appended: it is computed by summing up the original five digits mod 10. In addition, a long line is added to the beginning and appended to the end. Write a program ZipBarCoder.java that reads in a five digit zip code as the command line parameter and prints out the corresponding postal barcode. Print out the code vertically instead of horizontally, e.g, the following encodes 08540 (with the check digit of 7).
***** ***** ***** ** ** ** ***** ** ** ***** ** ** ***** ** ***** ** ** ***** ** ** ***** ***** ***** ** ** ** ***** ** ** ** ***** *****
 US postal barcodes. Repeat the previous exercise, but plot the output using Turtle graphics.
 Gaps with no primes. Find the longest consecutive sequence of integers with no primes. Write a program PrimeGap.java that takes a command line parameter N and prints out the largest block of integers between 2 and N with no primes.
 Goldbach conjecture. In 1742, Christian Goldbach conjectured that every even number greater than 2 could be written as the sum of two primes. For example, 16 = 3 + 13. Write a program Goldbach.java that takes one command line parameter N and expresses N as the sum of two primes. Goldbach's conjecture is still unresolved, but it is known to be true for all N < 10^{14}.
 Minima in permutations. Write a program that takes an integer N from the command line, generates a random permutation, prints the permutation, and prints the number of lefttoright minima in the permutation (the number of times an element is the smallest seen so far). Then write a program that takes integers M and N from the command line, generates M random permutations of size N, and prints the average number of lefttoright minima in the permutations generated. Extra credit: Formulate a hypothesis about the number of lefttoright minima in a permutation of size N, as a function of N.
 Inplace inverse permutation. Redo Exercise 1.4.25, but compute the permutation inplace, i.e., do not allocate a second array for the inverse permutation. Caveat: this is hard.
 Most likely roll. Alice and Bob are in a heated argument about whether if they repeatedly roll a die until the sum is more than 12, is 13 the most likely sum? Write a program to simulate the process a million times and produce a table of the fraction of times the sum is 13, 14, 15, 16, 17, and 18.
 Spiraling 2D array.
Given a 2D array, write a program Spiral.java
to print it out in spiral order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
 Sudoko verifier.
Given a 9by9 array of integers between 1 and 9, check
if it is a valid solution to a Sudoku puzzle: each row,
column, and block should contain the 9 integers exactly
once.
5 3 4  6 7 8  9 1 2 6 7 2  1 9 5  3 4 8 1 9 8  3 4 2  5 6 7 ++ 8 5 9  7 6 1  4 2 3 4 2 6  8 5 3  7 9 1 7 1 3  9 2 4  8 5 6 ++ 9 6 1  5 3 7  2 8 4 2 8 7  4 1 9  6 3 5 3 4 5  2 8 6  1 7 9
 Sum of powers conjecture. Redo Exercise 1.3.x, but precompute the 5th powers of all relevant integers. Evaluate how much time this saves. The program Euler.java searches for integral solutions to a^{5} + b^{5} + c^{5} + d^{5}= e^{5}.
 Haar wavelet transform.
Given, an array a[] of size 2^n, its
1D Haar transform is obtained as follows:
Compute the average and difference of a[2i] and a[2i+1],
and compute the array of the same length containing the
averages, followed by the differences.
Then apply the same technique to the averages (the first 2^n1 entries)
and so on.
An example with 2^3 entries is shown below.
448 768 704 640 1280 1408 1600 1600 (original) 608 672 1344 1600 160 32 64 0 (step 1) 640 1472 32 128 160 32 64 0 (step 2) 1056 416 32 128 160 32 64 0 (step 3)

What happens when you try to compile a program with the following statement?
int[] a = new int[17];
 Blackjack.
Write a program Blackjack.java that
takes three command line integers x, y, and z representing your two
blackjack cards x and y, and the dealer's faceup card z, and prints out
the "standard strategy" for a 6 card deck in Atlantic city. Assume that
x, y, and z are integers between 1 and 10, representing an ace
through a face card. Report whether the player should hit, stand,
or split according to these
strategy tables. Encode the strategy tables using three
2D boolean arrays.
Modify Blackjack.java to allow doubling.
 Boltzmann distribution. Here's a simple model to approximate the Boltzmann distribution from statistical physics: generate 100 random integers between 1 and 10. If the sum is exactly 200 keep this trial. Repeat this process until you get 1,000 trials that meet the criterion. Now plot a histogram of the number of times each of the 10 integers occurs.
 Doubly stochastic. Write a program to read in an NbyN matrix of real numbers and print true if the matrix is doubly stochastic, and false otherwise. A matrix is stochastic if all of the row and column sums are 1. Since you are dealing with floating point numbers, allow the sums to be between 1  ε and 1 + ε where ε= 0.000000001.

Suppose that b[] is an array of 100 elements, with
all entries initialized to 0, and that a[] is an array
of N elements, each of which is an integer between 0 and
99. What is the effect of the following loop?
for (j = 0; j < N; j++) b[a[j]]++;
 Modify RandomStudent.java so that it stores a parallel array of type boolean named isFemale, where element i is true if student i is female and false otherwise. Now, print out one male student at random and one female student at random. Hint: use a dowhile loop to generate random integers until you get one that indexes a male student.

Which of the following require using arrays. For each, the input
comes from standard input and consists of N real numbers between
0.0 and 1.0.
 Print the maximum element.
 Print the maximum and minimum elements.
 Print the median element.
 Print the element that occurs most frequently.
 Print the sum of the squares of the elements.
 Print the average of the N elements.
 Print the element closest to 0.
 Print all the numbers greater than the average.
 Print the N elements in increasing order.
 Print the N elements in random order.
 Print histogram (with, say 10 bins of size 0.1).
 Write a program Yahtzee.java that simulates the rolling of five dice and prints "Yahtzee" if all five dice are the same; otherwise it should print "Try again."
 Modify Day.java so that it reads in a date and print out what day of the week that date falls on. Your program should take three command line arguments, M (month), D (day), and Y (year). Do not use any ifelse statements; instead use a string array consisting of the names of the 7 days of the week.
 Write a program Pascal.java to compute Pascal's triangle using a ragged array.