This chapter is from the book
This chapter is from the book
This chapter is from the book
Creative Exercises
2.4.12 Vertical percolation. Show that a system with site vacancy probability p vertically percolates with probability 1 – (1 – pn)n, and use PercolationProbability to validate your analysis for various values of n.
2.4.13 Rectangular percolation systems. Modify the code in this section to allow you to study percolation in rectangular systems. Compare the percolation probability plots of systems whose ratio of width to height is 2 to 1 with those whose ratio is 1 to 2.
2.4.14 Adaptive plotting. Modify PercolationPlot to take its control parameters (gap tolerance, error tolerance, and number of trials) as command-line arguments. Experiment with various values of the parameters to learn their effect on the quality of the curve and the cost of computing it. Briefly describe your findings.
2.4.15 Nonrecursive directed percolation. Write a nonrecursive program that tests for directed percolation by moving from top to bottom as in our vertical percolation code. Base your solution on the following computation: if any site in a contiguous subrow of open sites in the current row is connected to some full site on the previous row, then all of the sites in the subrow become full.
2.4.16 Fast percolation test. Modify the recursive flow() method in PROGRAM 2.4.5 so that it returns as soon as it finds a site on the bottom row (and fills no more sites). Hint: Use an argument done that is true if the bottom has been hit, false otherwise. Give a rough estimate of the performance improvement factor for this change when running PercolationPlot. Use values of n for which the programs run at least a few seconds but not more than a few minutes. Note that the improvement is ineffective unless the first recursive call in flow() is for the site below the current site.
2.4.17 Bond percolation. Write a modular program for studying percolation under the assumption that the edges of the grid provide connectivity. That is, an edge can be either empty or full, and a system percolates if there is a path consisting of full edges that goes from top to bottom. Note: This problem has been solved analytically, so your simulations should validate the hypothesis that the bond percolation threshold approaches 1/2 as n gets large.
2.4.18 Percolation in three dimensions. Implement a class Percolation3D and a class BooleanMatrix3D (for I/O and random generation) to study percolation in three-dimensional cubes, generalizing the two-dimensional case studied in this section. A percolation system is an n-by-n-by-n cube of sites that are unit cubes, each open with probability p and blocked with probability 1–p. Paths can connect an open cube with any open cube that shares a common face (one of six neighbors, except on the boundary). The system percolates if there exists a path connecting any open site on the bottom plane to any open site on the top plane. Use a recursive version of flow() like PROGRAM 2.4.5, but with eight recursive calls instead of four. Plot the percolation probability versus site vacancy probability p for as large a value of n as you can. Be sure to develop your solution incrementally, as emphasized throughout this section.
2.4.19 Bond percolation on a triangular grid. Write a modular program for studying bond percolation on a triangular grid, where the system is composed of 2n2 equilateral triangles packed together in an n-by-n grid of rhombus shapes. Each interior point has six bonds; each point on the edge has four; and each corner point has two.
2.4.20 Game of Life. Implement a class GameOfLife that simulates Conway’s Game of Life. Consider a boolean matrix corresponding to a system of cells that we refer to as being either live or dead. The game consists of checking and perhaps updating the value of each cell, depending on the values of its neighbors (the adjacent cells in every direction, including diagonals). Live cells remain live and dead cells remain dead, with the following exceptions:
A dead cell with exactly three live neighbors becomes live.
A live cell with exactly one live neighbor becomes dead.
A live cell with more than three live neighbors becomes dead.
Initialize with a random boolean matrix, or use one of the starting patterns on the booksite. This game has been heavily studied, and relates to foundations of computer science (see the booksite for more information).
)
)