Percolation Threshold

Grading

This class spans over two weeks. There are 12 exercise in total, after a warm-up if you need to get used to Java. Reaching question 6 after one week is good. The grading is:

• A : exercises 1-12 (ie. everything)
• B : exercises 1-9
• C : exercises 1-7

Introduction

This class starts with a short introduction to the working environment and to the use of Java through some simple programs in Java.

Then, the objective of the class, which will take place over two weeks, is to determine whether or not there is percolation through a grid of the plane paved with black and white cells, i.e. whether or not there is a path of black cells going from the top to the bottom of such a grid. Then, we estimate the proportion of black cells necessary for percolation to occur. This proportion is called the percolation threshold.

To do this, you will have to create a program, divided into small elementary functions, which you will then optimize step by step, guided by the subject. Don’t forget to test the functions you write whenever possible, and as you go along!

Here you will manipulate the classic Java functions and control structures, and make extensive use of arrays (integers and booleans) and fundamental control statements. In particular, you will program a data structure called Union-Find that allows you to efficiently represent equivalence classes using their canonical representatives. It allows for optimizing the solution of some problems in various domains, for example in graph theory or automatic proof.

Starting with exercise 3, you will have to submit your solutions via the form at the end of each exercise. It is possible to submit several files. It is also possible to resubmit a solution if you have made changes to it, and it is not a problem if the file contains more functions than requested, for example because you have already done the next question. The site will give you automatic feedback on your submissions, in the form of a traffic light at the top left of the screen. Click on it to learn more. The green banner Last submission: date only means that you have submitted a file, it does not say anything about the tests. It is important to understand that a positive feedback does not guarantee that your code is good. The tests only detect some simple errors. So if you have a problem with a question, you should also consider the possibility that it was caused by code from a previous question, even if the tests did not detect anything in that question.

Using Java

The version of Java best fitted for the classes is 1.8. You can write your programs using Eclipse, VScode, or some other editor. Come back to us if you have questions or problems.

Warm-up

The following is to check that you master the three steps necessary to execute a program. One does not need to understand Java for that, just follow the instructions.

1. Starting.

   Once Eclipse or your other environment launched, create a new project you will call warmup by clicking on File > new > Java project. If Java project is not suggested, first chose Project, and the option Java Project should appear in the next window. Select as JRE runtime environment JavaSE-1.8, this will reduce the risk of problems when submitting files. If you see a module-info.java file that was automatically generated, it is better to delete it.

   This project now appears in the Package explorer on the left side of your Eclipse window (if Eclipse is back to the home screen, you can click on the workbench arrow at the top right). It contains the standard Java library (JRE System Library but the name may vary depending on your installation) and an empty src directory. It is the latter that will contain the Java source files for your project.

   We advise you to create one project per class topic (but not per question).

2. Empty Program

   In Eclipse, create a Java class that you will name Empty. To do this, right-click on the src directory and select New > Class. In the opened dialog box, besides indicating the class name, remove warmup from the Package line and check the public static void main(String[] args) box to automatically create the main function of your program that will be called at the beginning of its execution.

   Eclipse has automatically generated the Empty.java file in the src directory while adding an indication (default package) (we will not need packages for this course). This file contains the following program:

   public class Empty {
       public static void main(String[] args) {
           // TODO Auto-generated method stub
       }
   }

   The exact meaning of the different lines of the program and, in particular, of the keywords public, class and static, will be introduced in the coming weeks when the concepts of object-oriented programming are taught to you. Until their mysteries are unveiled, consider them as mandatory syntactic conventions.

   In particular, the main function of your program must have the prototype public static void main(String[] args) to be recognized as such by the Java compiler.

   The string array args passed as an argument to this function corresponds to the arguments communicated to the program by the user via the command line.

3. Compiling and running the Empty.java file

   The compilation and execution phases, theoretically distinct, are combined in Eclipse by clicking on the Run button. The results of the execution appear at the bottom of the window, in the Console tab. However, since this program does nothing (the body of the main function is empty except for a comment line), no result appears here.

   To make sure that your program has been compiled and executed correctly, modify it to introduce an error, for example by removing the static keyword. If you try to compile and run this program again, you should get the following error in the console:

   Error: Main method not found in class Empty, please define the main method as:
   public static void main(String[] args)

   Correct this error by putting back the previously removed keyword and verify that the error has disappeared.

4. Program Hello.

   We now propose to modify this program to display the message “Hello”. For this, we will create a new class Hello in the same project. You can create it as before or copy the empty class.

   After opening the Hello.java file by double-clicking on it, insert the following statement between the braces of its main function:

   System.out.println("Hello");

   We should immediately get into the habit of putting only one instruction per line, avoiding lines that are too long, and indenting properly our programs. Eclipse helps you with the latter.

   Compile and execute this program, then verify that the welcome message appears in the console.

5. Case of a program that does not terminate.

   If we insert:

   while (true)

   before

   System.out.println("Hello");

   we obtain a program that displays Hello endlessly. To interrupt it, you need to click on the red square on the right side of the console. ## Basic exercises

   The following exercises aim to point out a number of common errors (or misunderstandings). Their purpose is to help you avoid them in the future.

   For these exercises, continue to use the warmup project by adding new classes to it.

Exercise 1: primitive types

1. Calculate and display 20!, using a variable i of type int and then a variable n of type long. Can you explain the difference in behavior?

2. What is the result of the following instructions placed in a main function:

   double d = 0;
   d = 1 + 1/2 + 1/3;
   System.out.println(d);

   What can you do to obtain a result that is more consistent with intuition?

3. Write a program that calculates and displays the quantities:

   \[\begin{gather} 2 + 2 \\ e + \pi \end{gather}\]

   The mathematical constants involved here are static fields of the java.lang.Math class, whose documentation is provided. For example, to use the constant \(\pi\), simply write Math.PI in your program.

Exercise 2: debugging a program

One rarely programs without making mistakes. It is therefore important to be able to detect errors in a program and correct them quickly. To do this, the programmer has several tools at their disposal that make the task considerably easier:

• errors indicated on the fly by Eclipse, via red crosses in the margin when you edit your program;

• compiler error messages to be looked at in the order of issuance: they are relatively explicit in Java; in particular, the line number where the first error is detected is often relevant;

• runtime error messages;

• displaying intermediate values when the program does not produce the correct result;

• using a debugger such as the one integrated into Eclipse, although we will not delve into this in INF371.

It is very important to check for the absence of red crosses and to compile and test your program very regularly, for example after writing each function.

To practice debugging quickly, you are provided with several erroneous versions of the same program supposed to calculate the value of n!, where n is an integer entered by the user from the keyboard.

To do this, download the zip archive Bug.zip. It contains eight Java files named from Bug1.java to Bug8.java. To add them to your warmup project, you can right-click on src, then select Import. In the dialog box, choose General then Archive File, click Next, then Browse on the first line and select the downloaded file Bug.zip. Finally, click Finish.

The objective of this exercise is to find the error in each of these eight programs using the different error messages returned by the compiler or at runtime.

For the future, you can find a summary of common errors here, also accessible directly from the course page.

Percolation Threshold

We will compute an approximate value of the percolation threshold of a path from top to bottom in a matrix containing black and white cells. To do this, we will randomly blacken cells and, after each step, we will detect if there is a path made of black cells going from any top cell (first row) to any cell at the bottom (last row) of the matrix (without diagonal jumps). If so, the percolation will be reached. The percolation threshold is the proportion of black cells that it is probabilistically necessary to blacken to reach the percolation. This threshold is the same for any matrix that is not too small.

To represent a square matrix M of size N, we will use a one-dimensional array T of size NxN : the cell in the row i and column j in M (with i and j between 0 and N-1) will correspond to the element of index i.N + j in T. For example, here is the encoding of a matrix of size 3 by a one-dimensional array of size 9 (each cell of the array contains here the index (row, column) of the cell of the matrix that it encodes).

Exercise 3 : defining the class In a new project, define a Percolation

class containing the constants size, initially equal to 10, and corresponding to the size of a matrix, and length, of value size * size. This class will also contain a static array of booleans grid of size length corresponding to the matrix: a box containing true (resp. false) will be black (resp. white).

Exercise 4 : function init

Define a function void init() with no arguments initializing the matrix with only white cells. This function will also be used to reset the matrix between two percolation experiments.

Exercise 5 : function print

Define an void print() function with no arguments that displays the matrix on the standard output. White cells will be represented by the character '-' (dash) and black cells by '*' (star). Make sure that the rows correspond to the first dimension of the matrix and the columns to the second dimension of the matrix.

For example, the table

(encoding a 3x3 matrix) will be displayed like this:

*--
**-
-*-

To test your two functions, add a main function initializing the matrix with only white cells except for the cell in row 2 and column 4, then displaying it. Do the same for initializing the whole row 2, then the whole column 4 with white cells.

Exercise 6 : percolation

1. Define a function int randomShadow() that randomly darkens one of the white cells of the matrix (assuming that there is one) and returning the corresponding index. To do this, you use the function Math.random that returns a floating point number between 0.0 (included) and 1.0 (excluded).

   Algorithmic note: We can assume that the array is not too full, contains at least around 40% of white cells and that we will therefore find a white cell after a few draws. This is the simplest solution. Another solution that guarantees a low computation time even in the worst case is the following: first determine a random order of the squares, then blacken them in this order. If you want to do this, you can use the Fisher-Yates shuffle algorithm to find a random permutation. Experience shows that this does not provide much practical gain.

2. Define a function boolean isNaivePercolation(int n) returning the Boolean true if and only if there is a black path in the matrix, between one of its cells in row 0 (the top of the matrix) and one of its cells in the row size-1 (the bottom of the matrix), and passing through n.

   For this, it is possible to proceed in two similar steps:

   • detecting a (half)path between the n cell and the top of the matrix; and
   • detecting a (half)path between this same cell and the bottom of the matrix.

   Nevertheless, one must be careful not to visit twice the same cell on the same half-path and to factorize the code for the detection of the two (half)paths. To do this, you can define and use an auxiliary recursive function boolean detectPath(boolean[] seen, int n, boolean up) detecting a (half)path from the cell of index n to the top (resp. bottom) of the matrix if up is true (resp. false), considering the array seen of the cells already visited for this (half)path.

3. Add a function boolean isPercolation(int n) that just calls isNaivePercolation. This will be used to easily test different versions of isPercolation without having to modify your whole program.

4. Define a function double percolation() that blackens cells of the matrix at random, as long as its percolation has not taken place (the name of the function is just percolation, and double is the return type). Once percolation has been reached, this function will return the proportion of blackened cells.

   Submit your files here.

   Upload form is only available when connected

Exercise 7 : Monte-Carlo method

1. Define a function double monteCarlo(int n) computing an estimate (between 0 and 1) of the percolation threshold by performing n percolation simulations. Performing such an approximate calculation by successive simulations is called the Monte-Carlo method (hence the name of the function). It is used to solve efficiently many practical problems for which an exact calculation is impossible or too expensive.

2. Modify the function main so as to display the percolation threshold of a white matrix after n simulations, n being provided by the user via the Arguments tab of the dialog box accessible from Run > Run Configurations. You can use Integer.parseInt to read an integer from a string. Using the System.currentTimeMillis() function, also display the execution time required to reach the percolation threshold.

3. Try your program with different matrix sizes and different numbers of simulations.

Union-Find

The previous solution is not satisfactory because the percolation test is too inefficient. We are going to use a data structure called Union-Find to optimize our search. It efficiently computes an equivalence relation via the canonical representative of each equivalence class. Here, two indices of the matrix are equivalent if they are on the same black path, so that detecting percolation is like detecting the fact that a top element is equivalent to a bottom element of the matrix.

Exercise 8 : defining Union-Find

We will first program a first version of the Union-Find structure, simple but not very efficient (quick-find).

1. In a new UnionFind.java file, create a UnionFind class containing an equiv array and a void init(int len) function initializing this array with size len and associating i to each index i (initially i is its own representative in its singleton equivalence class).

2. Add to this new class a function int naiveFind(int x) returning the canonical representative associated to x.

3. Add to this new class a function int naiveUnion(int x, int y) realizing the union of the equivalence classes of x and y : the members of the equivalence class of x will have as new canonical representative that of y. This new representative will be in fine returned by the function. The size of an array t is available in the t.length variable.

4. Add functions int find(int x) and int union(int x, int y) that simply call naiveFind and naiveUnion respectively. They will be used to easily test the different versions of find and union without having to modify your whole program.

Exercise 9 : using Union-Find

We will now use our Union-Find structure to optimize our percolation detection program.

1. Modify the init function of the Percolation class to also initialize the UnionFind structure (via a call to UnionFind.init).

2. Define a function void propagateUnion(int x) merging the class of the x cell (assumed to be black) with all its black neighbors. At the end of the execution of this function, all the black neighbors and x must belong to the same equivalence class.

3. Modify the randomShadow function to call the propagateUnion function appropriately.

4. Write a function boolean isFastPercolation(int n) with a behavior similar to isNaivePercolation but more efficient due to the use of the the Union-Find structure.

5. Modify the boolean isPercolation(int n) function so that it uses isFastPercolation.

   Submit your files here.

   Upload form is only available when connected

Optimizations

Exercise 10 : lazy Union-Find

The previous solution is still not efficient because the union operation is too expensive: its complexity is linear in the number of elements. We will perform a first optimization at the cost of a degradation of the complexity of the find function (from constant to logarithmic time). The overall efficiency will already be much better.

Exercise 11 : logarithmic complexity

1. In the case of a union union(x, y), another optimization is possible. Indeed, for the moment, we have arbitrarily chosen to modify the equivalence class of x so that its canonical representative is the one of y. To limit the height of the trees, we can choose to keep as canonical representative the one whose height of the tree corresponding to its equivalence class is the largest by integrating a strictly smaller tree at its root. Its height will not change. This optimization allows for limiting the height of each tree by the logarithm of the number of its elements (see poly). The time complexity of each step is then also logarithmic.

   Code this modification in a new function logUnion by adding an array of integers height of the same length as equiv to the UnionFind class. The index element i of this array will contain the height of the tree with i as root. This array will be initialized in UnionFind.init.

2. Another optimization, called path compression, consists in bringing closer to the root the elements encountered during a search. This way, the trees will be less high. We can implement this optimization the following way: each time we encounter an element during a search, we make it point to its grandfather in the tree (rather than to its father, as before, or to the root, for the unsimplified path compression).

   Code path compression into a logFind function and compare the efficiency of this implementation with that of other versions by modifying find and union.

   When we compress the paths, it can change the height of the trees (that’s the point!). Calculating the exact height of the trees for the optimized version of union would be very expensive. The usual strategy is to ignore the problem and keep the same function for calculating heights as without compression (we will then talk about rank rather than height, but for simplicity we will keep the name height in the code): it has been proven that the quantity thus calculated brings the same advantages as the real height.

Exercise 12 : optimizing the number of searches

Now that the union function is logarithmic, it becomes advantageous to reduce the number of searches, even if it means increasing the number of unions. To do this, we will add two distinguished elements to our Union-Find structure (calling UnionFind.init with the length of the matrix + 2) to represent the whole of the top and bottom edges. Thus, it becomes possible to perform the percolation test by simply comparing the equivalence classes of these two distinguished elements with a single test, without even knowing the last blackened cell.

Note that the definition of the equivalence classes is slightly modified for the first and the last rows: an equivalence class does not group only the cells on the same black path, but contains the whole first (resp. last) row and the corresponding distinguished element as soon as a cell is on this path.

Nevertheless, it becomes necessary to modify the propagateUnion function to propagate the equivalence classes to these special elements as soon as a cell of the top or bottom row is blacked out.

Code this last optimization into a boolean isLogPercolation() function, also modifying the propagateUnion function appropriately.