Question

For this assignment, you will experimentally verify the percolation constant. You will need to answer the following question: You are given a square grid of cells, of which a proportion p are vacant cells. Can you find a continuous path from top to bottom, visiting only vacant cells? For example, here is a 40x40 grid of cells: the black ones are filled, while the gray and white ones are vacant. Notice that there is continuous path of vacant cells from top to bottom. We say that this grid "percolates", because fluid poured at the top will find its way to the bottom. The detailed question is, given a vacancy proportion p, what is the probability that the grid will percolate? Look at the experimental graph above. Notice that the probability of percolation rises sharply near p=0.6. Approach Run the following simulation, many times: 1. create an n×n grid of cells, initially all occupied. 2. nvacant = 0 3. repeat: 4. randomly make one more cell vacant 5. nvacant++ 6. until the grid percolates 7. write down p= nvacant/(n×n), the proportion of vacancies at which the grid percolated If you run the simulation many times, you will obtain a robust estimate for the probability that the grid percolates, for each value of p. Sub-problem 1: Randomizing an array One problem you will run into is this: how do you pick a random cell, in order to make it vacant? You could generate two random numbers from 0 to n-1 (assuming that random(n) returns a number from 0 to n-1):  x = random(n)  y = random(n) and set grid[x,y] = vacant. However, that cell may already be vacant. If the grid already contains many vacant cells, you will probably not change the grid. There is a better way. First, generate the [x,y] coordinates for all cells in the grid, and put them in an array. Then, shuffle the array to randomize its order. Finally, visit the array from first to last, and you'll be visiting the cells in random order, without visiting any cell twice. How do you shuffle an array? Try the Fisher-Yates shuffle for (i = n-1; i >= 1; i--) { j = random number from 0 to i; swap(a[i], a[j]); } Sub-problem 2: Detecting percolation Implement the union-find algorithm, as described in the textbook, and in the online lecture slides. Then, every time you make one cell vacant, add connections to its four neighbors, and check if the top row and the bottom row now belong the same connected component. If so, the grid percolates. Thus detecting percolation requires you to test whether one of the n cells in the top row  is vacant, and  belongs to the same component as a vacant cell among the n cells in the bottom row. This test costs O(n2) time. You can reduce the cost by adding two ficticious "plates" to your grid, one on top, and one on the bottom. Each cell in the top row is connected to the top plate, and each cell one in the bottom row is connected to the bottom plate (both plates are vacant). Then detecting percolation just requires testing whether the two plates are in the same component. Reporting Requirements Submit the programs you used to calculate percolation, and a brief report which contains the numbers you obtained, and a graph of the percolation probability versus the occupancy fraction p. Your report is to be one page in length. It must follow the following format. All reports are to be submitted in Times New Roman font, point size 12. All papers must be checked and corrected for spelling errors before submission. There are to be three sections, Purpose, Summary, and Conclusions. Each section is marked with a section header, centered on the page, in bold. The purpose section is one sentence in length, and states why you are doing this project. The graph would be on a following page, and properly labeled. The summary section is the longest section of the report, and it will include your reasons for selecting the programming language and tools that you used. Details of any class structures must be included, along with a description of your matrix structure. The conclusions section is approximately one page in length. What did you learn from doing this assignment? Synthesize your learning. All reports must include the student's name on the page. Students will also submit their commented code.

Answer 1

In this assignment, the goal is to experimentally verify the percolation constant by simulating the percolation process in a square grid. The percolation probability is determined by incrementally making cells vacant and recording the proportion of vacancies at which the grid percolates. This involves implementing a simulation with a randomized approach to making cells vacant and utilizing the union-find algorithm to detect percolation.

Step-by-step explanation:

The approach involves creating an n×n grid, initially occupied, and iteratively making random cells vacant until the grid percolates. The proportion of vacancies at which percolation occurs is recorded.

Randomizing the array of cell coordinates is crucial for avoiding bias in making cells vacant. The Fisher-Yates shuffle algorithm is employed to achieve this, ensuring a uniform and unbiased selection of cells to make vacant.

To detect percolation, the union-find algorithm is implemented. Connections between vacant cells and their neighbors are established, and percolation is identified by checking if the top and bottom rows belong to the same connected component.

The addition of fictitious "plates" connected to the top and bottom rows reduces the percolation detection cost from O(n²) to a more efficient operation. The reporting requirements include submitting the program used for percolation calculations, a brief report with obtained numbers, and a graph illustrating the percolation probability against the occupancy fraction.

In conclusion, this assignment involves a systematic simulation to experimentally determine the percolation constant. Utilizing randomized cell selection and efficient percolation detection algorithms ensures accurate and unbiased results, contributing to a better understanding of percolation in square grids.