COSC 1010 Introduction to Software Problem Solving

Fall 2010

Homework Assignment #8

"Good To The Last Byte"
Due: Tuesday, Nov 23rd, 11:00am CST
Submit: Turn in all both of your Java source files using D2L dropbox:
Work may be completed in teams of two. The names of both partners must appear in a comment block at the top of your files for credit to be given.


Physics, Chemistry, Geology, and Material Science, among other fields, all can include the study of Percolation Theory. Put simply, percolation concerns the movement and filtering of fluids through porous materials. (Thank you, Wikipedia.) Other applications of percolation modeling can examine movement of electricity or fire, but the idea is the same.

Given a grid consisting of open squares and closed squares, (think of the game "Minesweeper",) a simple percolation model checks whether there is a path through the open squares from the top of the grid to the bottom, without passing through closed squares or moving diagonally.

To make things more interesting, the selection of which blocks are closed is typically generated using some random probability distribution. This technique belongs to a much larger class of computational algorithms called Monte Carlo methods, widely used to simulate complex physical and mathematical systems that cannot otherwise be well understood.


Create a class RandomGrid that generates a randomized grid of size n. Your class should take two command-line parameters: a positive integer grid size, "n", and a probability threshhold, "p", in the range 0.0 - 1.0, inclusive. Use Java's exception handling mechanisms to make your program robust against all kinds of input errors.

Once you have valid values for n and p, create an n x n grid of integers. Use the class java.util.Random to generate a random value between 0.0 and 1.0 for each element in the grid; if the random number is less than or equal to the threshhold p, close that grid square off.

Please declare the following methods for the RandomGrid class. I may replace your RandomGrid class with my own, non-random version during testing, so it is important that you conform to this API.

  • public static int[][] makeGrid(int n, double p). Contructs a randomized grid of size n x n, filled with probability threshhold p. Open squares contain a 0, blocked squares contain a 1. Other values can be used to note percolation.
  • public static void printGrid(int[][] grid). Prints a grid. See the reference implementation for details.
  • public static void main(String[] args). A main method to test your RandomGrid class.
  • Percolate

    Create a Percolate class that uses the RandomGrid class to run a percolation simulation on a random grid. Percolation starts with any open squares in the top row of the grid, and continues to all adjacent squares that can be reached vertically and horizontally without passing though a blocked square.

    A recursive exploration of the grid will be more elegant than an iterative algorithm.

    Print out the final grid with percolation noted, and a final judgement at the bottom showing whether flow is possible from the top row through to the bottom row.


  • Test both of your classes with a wide variety of grid sizes and probability threshholds. Next week's project will build a more complex simulation on top of this one.
  • The Professor has provided a reference implementation for you to compare against. Change to directory ~brylow/cosc1010/Project8/ on Morbius, and run java RandomGrid or java Percolate. Note that as grids are randomized, answers will differ.

  • Back
    [Revised 2010 Nov 15 11:50 DWB]