2.5. ARRAYS

This section is under construction.

In Section 2.4 we discovered how to process huge quantities of input data. In this section, our goal is to store and manipulate huge quantities of data.

Arrays. An array is a fundamental data structure that enables us to store and manipulate potentially huge quantities of data. An array stores an ordered sequence of homogeneous values. Homogeneity means that all the values are of the same type, e.g., 180 integer exam scores, 512 real-valued color gradations, 5 million characters of a book, or 34 billion nucleotides of a DNA strand. The order of the values is also preserved, i.e., the integer array { 1, 2, 3, 4 } is different from { 1, 4, 3, 2 }.

Arrays in Java.

In Java, we declare an array by specifying its type followed by square braces, and then its name. This does not actually allocate any memory in which to store the elements of the array. To do this, we must use the keyword new and specify the size of the array. Once we specify the size of the array, it is fixed. To access an array element, we use the array name followed by an index enclosed in square braces.

The following code fragment initializes an array of 1,000 integers, and sets element i equal to the value i².

int N = 1000;                 // size of array
int[] a;                      // declare an array
a = new int[N];               // N elements, each initialized to 0
for (int i = 0; i

The obvious advantage of arrays is to avoid explicitly naming each variable individually. Naming dozens of individual variables is cumbersome, naming millions is untenable.

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

Caveats. When programming with arrays, you must be careful. In Java, array indices start at 0. Thus, a[0] is the value of the first element and a[N-1] is the value of the Nth element. To avoid confusion we will refer to these as elements 0 through N-1. It is your responsibility to use legal indices when accessing an array element. It is also your responsibility to use new to allocate memory for any array before accessing any element. If you fail to adhere to these rules in Java, you will encounter a runtime exception when you execute your program. An ArrayOutOfBounds error occurs when you access an illegal element of an array; a NullPointerException occurs when you access an element before initializing the array. In many programming languages, such buffer overflow errors are not checked by the system. These "ghastly errors" can and do lead to debugging nightmares. If such errors remain in finished programs, malicious hackers can exploit it to break into your system, spread viruses, or worse.

Random student. Program RandomStudent.java stores a list of names and prints out a random one. We first initialize an array of strings called names, storing one string for each student. Since we are initializing the array with specific values when we declare it, we do not use the new keyword or specify its size. Instead, we list the elements between curly braces, separated by a comma.

String[] names = { "Anand Dharan", "Ashley Evans", "Alica Meyers" };

Now, we can use names.length to access the number of elements N in the array. Next, we generate a pseudo-random integer between 0 and N-1. Finally we use this as an index to select one of the strings in the list and print it out.

int N = names.length;
int r = (int) (Math.random() * N);
System.out.println(names[r]);

Student database. The file students.txt contains a list of students enrolled in an introductory computer science class at Princeton. The first line contains an integer N that specifies the number of students in the database. Each of the next N lines consists of four pieces of information, separated by whitespace: first name, last name, email address, and section number. The program Students.java reads in the integer N and then N lines of data of standard input, stores the data in four parallel arrays (an integer array for the section number and string arrays for the other fields). Then, the program prints out a list of students in section 4 and 5.

Shuffling.135 official candidates. To avoid the natural prejudice against candidates whose names appear at the end of the alphabet (Jon W. Zellhoefer), California election officials sought to order the candidates in random order. We will write a Java program that does exactly this. Our shuffling routine is equally useful when shuffling playing cards, selecting a random sample for a statistical poll, or shuffling songs in an iPod Shuffle.

Program Shuffle.java takes a command line parameter N and reads in a list of N strings from standard input and prints them back out in shuffled order. First, we initialize an array of strings of size N. Then, we read in strings from standard input and store them in the array. The file california-gov.txt is the same as the original file except that we have replaced the spaces in the candidates names with the '_' character so that we can read each string with StdIn.readString. (Change to readLine to fix this hack.) Shuffling the N elements in the array is the most interesting part. We iterate N times. In step i, we generate a random integer r between 0 and i and swap the contents of a[i] with a[r]. Under the idealistic assumption that Math.random() outputs uniformly random real numbers between 0.0 and 1.0, this algorithm maintains the invariant that after step i, array elements a[0] to a[i] contain a uniformly random permutation of the integers 0 to i.

Although our shuffling program is very short, many programmers, instructors, and textbooks get the algorithm wrong. Shuffling N items means that each of the N! possible orderings is equally likely. If we generate random integers between 0 and N-1 in the algorithm above (instead of between 0 and i), then each ordering is possible, but some are more likely than others. Since each ordering is possible, it might not be apparent from a cursory inspection that the modified algorithm is broken. (See Exercises XYZ and XYZ.) Another strategy that fails is to choose two cards at random and swap them, and repeat a "sufficiently large" number of times. Another poor strategy is to simulate how humans shuffle playing cards by cutting the deck into two equal piles and interleaving the cards from each pile. The strategy can fail spectacularly because eight perfect shuffles in a deck of 52 cards yields the cards in their original order (See exercise XYZ in linked lists). In fact, the California election officials got it wrong. They decided to randomize the alphabet instead of shuffling the candidates. Using this strategy, not all N! possible outcomes are equally likely or even possible! For example, two candidates with very similar last names will always end up next to each other.

Coin flipping. Program Flip.java uses an array to simulate a version of the Gambler's ruin experiment we considered in Section 2.3. In each trial, the program flips N fair coins and counts the number of times i of the N coins are heads. The program performs 100,000 trials and records in array element count[i]the number of times you get exactly i heads. Finally, the program animates the histogram using Turtle graphics. According to the Central Limit Theorem, the resulting histogram is approximately normally distributed with mean N/2 and variance N/4. Below are sample outputs when N = 16, 32, and 64.

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? Assume birthdays are uniform random integers between 0 and 364. The program Birthday.java calculates this probability by simulation. This phenomenon plays a crucial role in a data structure known as hashing. (See Chapter XYZ).

Linear feedback shift register.

We are now in a position to rewrite the linear feedback shift register from Chapter 1 program using arrays. This streamlines the program and makes it more extensible, e.g., if the number of cells in the shift register increases. Program LFSR.java uses a boolean array of size 11 to represent the 11 cells in the shift register. We use the ^ operator to take the exclusive or of two boolean values.

Sieve of Eratosthenes.

The prime counting function π(x) is the number of primes less than or equal to x. For example &pi(17) = 7 since the first seven primes are 2, 3, 5, 7, 11, 13, and 17. This function plays a central role in number theory. Program PrimeSieve.java takes a command line integer N and computes π(N) using the Sieve of Eratosthenes. The program uses a boolean array to record which integers are prime. The goal is to set isPrime[i] to true if i is prime and to false otherwise. The sieve works as follows. Initially, set all array elements to true, indicating that no integer is known to be non-prime. Then repeat the following loop

Find the smallest element i that is not known to be nonprime.
Declare this integer i to be prime.
Declare all multiples of i to be nonprime.

Finally, count the number of primes less than or equal to N. This program runs dramatically faster than the brute force solution PrimeCounter.java described in Section 2.3. However, it requires a boolean array of size N, whereas PrimeCounter.java uses only two integer variables. This is a classic example of a time-space tradeoff.

Growable array. Sometimes we need to store a large quantity of values in an array, but we don't know how many ahead of time. The problem is that once we allocate memory for an array, its size is fixed. We overcome this obstacle with the following classic strategy. Initially we set the array to have enough memory to store one element. If the array is not big enough to hold the next element, we allocate a new array of double the size and copy the old elements into the new array. We use the doubling strategy as a tradeoff between the work involved copying the old elements and the space wasted in the array. The following code fragment doubles the size of the array data by creating an auxiliary array temp of the right size and copying the elements of data to temp.

double[] temp = new double[2*N];
for (int i = 0; i

Program Reverse.java uses this strategy to read in an unknown number of real values from standard input into an array. After storing all of the data, it prints them out in reverse order.

The memory that was used to store the original array data will be automatically reclaimed by the system by a process known as garbage collection. In many languages, you must reclaim the memory manually, but in Java the programmer does not typically have to worry about such low-level details.

Insertion sort. The goal of InsertionSort.java is to sort a sequence of real values in ascending order. It sorts the data in N steps. At the beginning of step i, a[0] through a[i-1] are already in sorted order. The goal of step i is to put a[i] in sorted order. Insertion sort accomplishes this by repeatedly swapping element a[i] with its neighbor to the left until it is greater than or equal to all of the elements that precede it.

Benford's law. Benford's law is an amazing statistical law that governs certain types of random numbers. The American astronomer Simon Newcomb observed a bizarre quirk in a book that compiled logarithm tables: the beginning pages were much grubbier than the ending pages. He suspected that scientists performed more computations with numbers starting with 1 than with 8 or 9, and postulated the first digit law which says that under general circumstances, the leading digit of numbers appearing in newspapers, scientific journals, and baseball statistics is much more likely to be 1 (roughly 30%) than the digit 9 (less than 4%). This amazing phenomenon is now regularly used by the IRS forensic accountants to discover tax fraud. Program Benford.java reads in a sequence of integers and tabulates the number of times each of the digits 1-9 is the leading digit. The file princeton-files.txt is a list of file sizes on a public Unix machine at Princeton.

Memory representation. The elements of an array are stored consecutively in memory. It is convenient to think of the name of the array, say a, as storing the memory location of the first element of the array a[0]. When we specify the index a[i], the compiler accesses the desired element by adding the appropriate offset to the memory location of array. For this reason, accessing element i of an array is an efficient operation.

Command line arguments.

All of our programs have include the mysterious line

public static void main(String[] args)

We are now in a position to understand the String[] args part. When the user executes the program CommandLine.java from the command line

% java CommandLine this is a test

they can enter any number of command line arguments. In this case, the user is supplying four arguments "this", "is", "a", and "test". The system automatically creates a String array of size 4 and populates it with the 4 command line inputs. By convention, we name the array args. We can manipulate its contents just like any other array. For example, the following code fragment prints out each argument on a separate line. Note that specifying the name of the array, followed by .length tells us how many elements the array as.

for (int i = 0; i

Sometimes we want to read in an integer value from the command line. In Java, command line inputs are always received as strings. Thus, we must convert from the String representation to an int. The Java library method Integer.parseInt is designed especially for this purpose. It need not be used with arrays, but often is, and we have become accustomed to using this technique of parsing command line inputs.

int a = Integer.parseInt(args[0]);

Cleaning up repetitive code. Another useful application of arrays is to shorten repetitive code. As a simple example, consider the following code fragment which prints out the name of a month given its number (1 = January, 2 = February, and so forth).

if      (m ==  1) System.out.println("January");
else if (m ==  2) System.out.println("February");
else if (m ==  3) System.out.println("March");
else if (m ==  4) System.out.println("April");
else if (m ==  5) System.out.println("May");
else if (m ==  6) System.out.println("June");
else if (m ==  7) System.out.println("July");
else if (m ==  8) System.out.println("August");
else if (m ==  9) System.out.println("September");
else if (m == 10) System.out.println("October");
else if (m == 11) System.out.println("November");
else if (m == 12) System.out.println("December");

An alternative is to create a string array consisting of the names of each month as follows.

String[] months = { "", "January", "February", "March", "April",
                    "May", "June", "July", "August", "September",
                    "October", "November", "December" };
...
System.out.println(months[m]);

This is especially useful if you need 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). This is a small price to pay to make index 1 correspond to January, and index 12 to December.

Multi-dimensional arrays. So far, our arrays have been one dimensional. To access element i of the array a, we use a[i]. A two-dimensional array models a table or matrix. To access the element of the array a in row i and column j, we use the notation a[i][j].

The following code fragment initializes a 4-by-10 matrix of integers.

int[][] a = new int[4][10];          0  0  0  0  0  0  0  0  0  0
for (int i = 0; i <4; i++) 0 1 2 3 4 5 6 7 8 9 for (int j=0; j < 10; j++) 0 2 4 6 8 10 12 14 16 18 a[i][j]=i * j; 0 3 6 9 12 15 18 21 24 27

Examples: Matrix multiplication, grades, statistics?

Pre-computation. Another use of arrays is to store a pre-computed table of values to avoid having to compute the value from scratch more than once. In ancient times (as recently as the 1970s), scientists used reference books that stored nothing but a table of logs of various numbers. Nowadays, it is almost always easier to compute the value from scratch. But if your program is slow because of recomputing some values over and over, you may wish to precompute them, store them in an array, and access the array as needed. As a simpler example, the program Euler.java searches for integral solutions to a⁵ + b⁵ + c⁵ + d⁵= e⁵. By pre-computing the fifth powers of all relevant integers ahead of time, we reduce the running time (when N = 150) from roughly 3 minutes to 50 seconds.

We strongly discourage programmers from employing this trick unless the program is too slow to be useful and one of the main bottleneck operation is recomputing values. Unless both of these conditions are satisfied, it is a waste of effort, and, more importantly, can obfuscate the code. Dynamic programming is one important place where such optimizations play a critical role. We describe this algorithmic design paradigm in Chapter 10.

Q + A

Q. Why does array indexing start at 0 instead of 1?

A. Tradition.

Q. How can I exit gracefully if the user does not enter the correct number of command line arguments?

A. Try something like the following if the user was supposed to enter four arguments:

if (args.length != 4) {
    throw new RuntimeException("4 command line parameters required");
}

Q. What is the difference between declaring int[] a and int a[] ?

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

Q. Is it possible to have a 2D array where each row contains a different number of elements?

A. Yes. In Java a 2D array is an array of arrays. Each array can be a different size. Such arrays are referred to as ragged.

Lessons

Use arrays to manipulate huge quantities of data.
Use arrays to eliminate repetitive code.
Specify the length of the array when you create it. Once created, its length does not change. Use a.length to retrieve the number of elements in array a.
Initialize large arrays using the keyword new. Individual array elements are automatically initialized to default values (0 for integers, 0.0 for floating point numbers, false for booleans, and the special value null for strings). As a shorthand, you can initialize small arrays by enumerating the values of the elements in curly braces.
Don't forget that array indices start at 0, not 1.
Use only legal array indices to access array elements - it is a run-time error to access array out-of-bounds.

Exercises

Write a program that declares an array a of size 1,000 and accesses a[1000]. Does your program compile? What happens when you run it?
What happens when you try to compile a program with the following statement?
int N = 1000; int[] a = new int[N*N*N*N];
What is wrong with the following code fragment?
int[] a; for (int i = 0; i <10; i++) a[i]=i * i;
Answer: forgot to allocate memory for a with new. Results in a NullPointerException.

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(i);

Why does the following code fragment give an array out-of-bounds error?

int i, N = 10;
int[] a = new int[N];
a[0] = 0;
a[1] = 1;
for (i = 0; i

After fixing the error, what is a[9] after executing code fragment in the previous exercise?
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

Consider the following program.

public class Mystery { public static void main(String[] args) { int N = Integer.parseInt(args[0]); int[] a = new int[M]; while(!StdIn.isEmpty()) { int num = StdIn.readInt(); a[num]++; } for (int i = 0; i

Suppose the file input.txt contains the following integers:

8 8 3 5 1 7 0 9 2 6 9 7 4 0 5 3 9 3 7 6

What is the contents of the array a after running the following command

java Mystery 10

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 do-while loop to generate random integers until you get one that indexes a male student.
Write a program Cards.java that prints out the 52 playing cards in order. Use two arrays, one for 4 suits and one for the 13 ranks.
Deuce of Clubs Three of Clubs Four of Clubs ... Ace of Spades
Modify Flip.java so that the probability of heads is 0.6.
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.
1. Print the maximum element.
2. Print the maximum and minimum elements.
3. Print the median element.
4. Print the average of the N elements.
5. Print the N elements in increasing order.
6. Print the N elements in random order.
7. 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 if-else statements; instead use a string array consisting of the names of the 7 days of the week.
Write a code fragment to create and initialize a 1D array b[] of type double from a 1D array a[] of type int.
double[] b = new double[a.length]; for (int i = 0; i
Write a code fragment makes a 1D row packed copy of a 2D array. That is, given a 2D array a[][] with M rows and N columns, create and initialize a new array b[] with the M * N entries inserted in row order.
Write a program to read in an N-by-N matrix of real numbers and print true if the matrix is 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.

Creative Exercises

Birthday problem. Modify Birthday.java so that it takes two command line parameter M and N and runs the birthday experiment N times and prints out the average, where the number of days is M. Verify that when N = 365, the average number of people that need to enter the room is between 24 and 25. Name your program Birthdays.java.
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 command line parameter N, reads in N integers from standard input, and prints out the fraction of values that are strictly above the average value.
Random walkers. Write a program RandomWalkers.java that takes a command line parameter N and simulates the behavior of N independent random walkers who all start in the center of an N-by-N grid of cells and walk until all N*N cells have been visited by at least one random walker. Print out how many steps it takes.
Dealing a deck of cards. Modify Shuffle.java to deal 52 playing cards among 4 players. For simplicity, assume the cards are named 0 to 51.
Dealing a deck of cards. Repeat the previous exercise, but this time prints out the names of the cards instead of integers between 0 and 51. Hint: add an array of strings suits[] that lists the suits and an array of strings ranks[] that lists the card values.
String[] suits = { "Clubs", "Diamonds", "Hearts", "Spades" }; String[] ranks = { "Deuce", "Three", . . . , "King", "Ace" };
High-low. Shuffle a deck of cards, and deal one to the player. The player must guess whether the next card is higher or lower than the current card. Repeat until player guesses it wrong. Game show: ???? used this.
Longest plateau. Given an array of integers, find the length and location of the longest contiguous sequence of equal values.
Random permutation. Write a program Permutation.java so that it takes a command line input N and prints a random permutation of the integers 0 through N-1. 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 * * * *
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 re-enter and try to retrieve their beer. However, the lights are still off, so each student randomly picks up a can 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 command line parameter N and runs 1,000 simulations this event, assuming their are N guests. Print out the fraction of times that at least one guest get their original beer. As N gets large, does this fraction approach 0 or 1 or something in between?
CD shuffling. You set your CD player to shuffle mode. It plays each of the N songs before repeating any. What is the likelihood that you will not hear any sequential pair of songs (i.e., song 3 does not follow song 2, song 10 does not follow song 9, and so on)? Write a program to estimate this probability.
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 list of N registered voters. Compute and print out M distinct voters at random. Hint: modify Shuffle.java so that it shuffles all N elements and then prints out only the first M of them.
Empirically checking our shuffling algorithm. Run computational experiments to check that Shuffle.java works as advertised and that each of the N! outcomes are equally likely for small N, say N = 5. Modify Shuffle.java to repeatedly shuffle the integers from 1 to 5 and print them to standard output as 5 digit integers, e.g., 41325 51324 21534. Then write another program that reads in sequences of 5 digit integers and prints out each 5 digit integer along with the fraction of times that it occurs. Do not print out integers that never appear, e.g., 12234 or 65312.
Bad shuffling. Suppose that you choose a random integer between 0 and N-1 in Shuffle.java instead of between 0 and i. Show that the resulting order is not equally likely to be one of the N! possibilities, even when N = 3. Assuming the elements are named A, B, and C, verify that all 6 outcomes are possible, but that they occur with the following biased probabilities.

ABC ACB BAC BCA CAB CBA

4/27 5/27 6/27 4/27 5/27 3/27
Find a duplicate. Given an array of N elements in which each element is between 1 and N, write an algorithm to determine if there are any duplicates. You may destroy the array, but no extra arrays allowed. Hint: you can do it without sorting.
8 queens checker. A permutation of the integer 0 to N-1 corresponds to a placement of queens on an N-by-N 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 using at most two arrays of size 2N each, i.e., don't explicitly create the N-by-N array. In Exercise XXX, you will write a program to automatically find a legal placement of queens if one exists.
Rumors. Alice is throwing a party with 25 other guests, including her brother 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. However, if a person hears the rumor for a second time (including Bob), they 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. Also calculate the expected number of people to hear the rumor before it stops propagating.
Answer..
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.
Smith's rule. The following problem arises in supply chain management. You have a bunch of jobs to schedule on a single machine. (Give example.) Job j requires p[j] units of processing time. Job j has a positive weight w[j] which represents its relative importance - think of it as the inventory cost of storing the raw materials for job j for 1 unit of time. If job j finishes being processed at time t, then it costs t * w[j] dollars. The goal is to sequence the jobs so as to minimize the sum of the weighted completion times of each job. Write a program SmithsRule.java that reads in a command line parameter N and a list of N jobs specified by their processing time p[j] and their weight w[j], and output an optimal sequence in which to process their jobs. Hint: Use Smith's rule: schedule the jobs in order of their ratio of processing time to weight. This greedy rule turns out to be optimal.
Calendar. Repeat Exercise 2.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.
Coupon collector. Dilbert wants to collect N = 365 distinct Pokemon trading cards. He doesn't get to view a card until after he's bought it. He wants to know how many total cards (on average) he will have to buy before he has accumulated at least one card of each type. Assume that each time Dilbert buys a card, it is equally likely to be any of the N possible types (and is independent of previous purchases). Write a program CouponCollector.java that takes two command line inputs M and N and performs the simulation M times and prints out the average number of cards purchased.
Connect Four. Given an N-by-N 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 weight-class according to this table. Use an integer array to store the weight limits and a string array to store the weight categories (ranging from Flyweight to Super Heavyweight).
N-ary counter. Write a program that counts in base N from 0 to N²⁰ - 1. Use an array of 20 elements.
Terrain analysis. Given an N-by-N 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 N-by-N grid.
Magic squares. Write a program MagicSquare.java that reads in an odd integer N from the command line and prints out an N-by-N 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 wrap-around to handle border cases.
Elastic collisions. Write a program CollidingBalls.java that takes a command line input N and plots the trajectories of N bouncing balls that bounce of the walls and each other according to the laws of elastic collisions. Assume all the balls have the same mass.
Elastic collisions with obstacles. Each ball should have its own mass. Put a large ball in the center with zero initial velocity. Brownian motion.
Voting and social choice theory. Plurality (US presidential election), run-off elections, sequential run-off elections (Australia, Ireland, Princeton faculty committees), Condorcet. Kemeny rank aggregation. Arrow's impossibility theorem. Same ideas for sports, google, meta-search, 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 top-k 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 top-k lists.
int footrule = 0; for (int i = 0; i
Voting power. John F. Banzhaf III proposed a ranking system for each coalition in a block voting system. Suppose party i control w[i] votes. A strict majority of the votes is needed to accept or reject a proposal. The voting power of party i is the number of minority coalitions it can join and turn it into a winning majority coalition. Write a program VotingPower.java that takes in a list of coalition weights as command line parameters and prints out the voting power of each coalition. Assume that there are at most 20 coalitions and use brute force to enumerate all possible minority coalitions that party i can join and swing to a majority.
US postal barcodes. The barcode for zip codes in the United States converts each decimal digit to a sequence of 5 short and long lines as follows: A sixth checksum digit is appended: it is computed by summing up the original five digits mod 10. 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 08.
****** ****** ** ** ** ****** ** ** ****** **
US postal barcodes. Repeat the previous exercise, but plot the output using Turtle graphics.
Hadamard matrix. The N-by-N 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 error-correcting codes. Here are the first few Hadamard matrices.
H(1) H(2) H(4) ------------------- 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1
In general H(2N) is obtained by aligning 4 copies of H(N) in the form of a large square, and then inverting all of the entries in the lower right N-by-N copy. Write a program Hadamard.java that takes one command line parameter N and prints H(N). Assume N is a power of 2.
Hadamard plot. Modify the previous exercise so that instead of printing 0s and 1s to the screen, it plots the Hadamard matrix with Turtle graphics, using black squares instead of the 1s and white squares instead of the 0s. Name your program HadamardPlot.java. Below are the desired plots for N = 2, 4, 8, and 16.
Minesweeper. Write a program Minesweeper.java that takes 3 command line parameters M, N, and p and produces an M-by-N grid of cells where cell (i, j) contains a bomb with probability p. Print out the bombs using an asterisk and safe cells using a period. Then, replace each safe square with the number of neighboring bombs (above, below, left, right, or 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.
Computing primes. Compare the running time of Primes.java with PrimeSieve.java.
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 ¹⁴.
Sum of four primes. Given an input parameter N, express N as the sum of four primes (not necessarily distinct). or report that it is impossible to do so. To make your algorithm fast for large N, do the following steps:
1. Compute all primes less than N using the Sieve of Eratosthenes.
2. Tabulate a list of sums of two primes.
3. Sort the list.
4. Check if there are two numbers in the list that sum to N. If so, print out the corresponding four primes.
Inverse permutation. Write a program InversePermutation.java that reads in a permutation of the integer 0 to N-1 from N command line parameters and prints out the inverse permutation. Be sure to check that the input is a valid permutation.
In-place inverse permutation. Redo the previous exercise, but compute the permutation in-place, i.e., do not allocate a second array for the inverse permutation. Caveat: this is hard.
Binomial coefficients. Write a program BinomialTheorem.java that prints out the coefficients of (x+y)^N, e.g.,
(x+y)⁵ = x⁵ + 5 x⁴ y + 10 x³ y² + 10 x² y³ + 5 x y⁴ + y⁵.
Use the Binomial Theorem and Pascal's Triangle which says that you can obtain the coefficients by considering the following automata:
- Initialize an integer array a[] of size N+1 with a[0] = 1 and a[i] = 0
- Repeat N times: For i = 1 to N, update a[i] = a[i-1] + a[i] using the old values of a[i-1] and a[i]
Upon termination, a[i] contains the coefficient for the x^N-i yⁱ term.
Histogram. Write a program that reads in integers between 0 and 100 and plots a histogram of the results using turtle graphics in a 512-by-512 window.
Statistical outliers. Modify Average.java to print out all the values that are larger than 1.5 standard deviations from the mean. You will need an array to store the values.
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 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 2-D array. Given a 2-D array, write a code fragment to print it out in spiral order.

A B C D E     M L G H I N S R Q P K F A B C D E J O T Y X W V U
F G H I J
K L M N O
P Q R S T
U V W X Y

Web Exercises or Under Construction

Neural networks. Use neural networks to solve some problem.
Paint by numbers. Write a program PaintByNumbers.java that takes two command line parameter N and p and produces an N-by-N grid of cells where cell (i, j) is black with probability p and white otherwise. Print out the black cells using an asterisk and white cells using a period. Now, modify your program to produce the corresponding input rows and columns to the Paint By Numbers logic puzzle. This logic puzzle also goes by the name nonogram.
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 face-up card z, and prints out the "standard strategy" for a 6 card deck in Atlantic city. Assume that x, y, and z are integers between 1 and 10, representing an ace through a face card. Report whether the player should hit, stand, or split according to these strategy tables. Encode the strategy tables using three 2-D boolean arrays.
Blackjack with doubling. Modify the previous exercise to allow doubling.

ABC	ACB	BAC	BCA	CAB	CBA
4/27	5/27	6/27	4/27	5/27	3/27