% -*- compile-command: "rubber -d --unsafe hw-05-percolation.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage[num=5,date=October\ 7,topic=Percolation]{algorithms-hw}
\begin{document}
\coversheet
\begin{verbatim}
Percolating on 25x25 grid...
. . . X . . . . . . .
. . . . X . . . . . .
. . . . . X X . . . . . . .
. . X X . . . . .
. . . . . . X . . . . . .
. . . . X . . . . . . . . . .
. . . . . . X . . . . . .
. . . . . X . . . . .
. . . . . . X X X . . . X X X . .
. . . . . . . . . . X . X X . X . . .
. . . . . . . X X . . X . . X . .
. . . . . . . . . X X X X . X . .
. . . . . . . . . X
. . . . . . . . . . . . X X .
. . . . . . . . . . . . . X
. . . . . . . X
. . . . . . . . X X .
. . . . . . . . . . X X X X .
. . . . X . . .
. . . . . . . . . . X . .
. . . . . . X . . . .
. . . . . . . . . X . . . . .
. . . . . . . . . X X . .
. . . . . . . . . X . .
. . . . . . . X .
Percolation achieved with 352 cells opened (56.32%)
Shortest path length = 48
\end{verbatim}
Imagine an $n \times n$ square grid, where each cell is connected to
its four neighbors to the north, east, south, and west. Each cell can
be either ``open'' or ``blocked''. Paths through the grid can only
travel through open cells. We say the grid \emph{percolates} if there
is a path from some open cell in the top row all the way to some open
cell in the bottom row.
Now, carry out the following process: the cells all start out blocked;
at each iteration, randomly pick a blocked cell and open it. Keep
iterating until the grid percolates.\marginnote[-6in]{It is a curious
fact that on average, the grid will percolate after 59.2\% of the
cells are opened---no matter what size the grid is. (The larger the
grid, the more precise the percentage will be.) Moreover, this
percentage is a sort of ``phase transition'': if you take a large
grid and randomly open \emph{fewer} than 59.2\% of its cells, then
it probably will not percolate; open any \emph{more} than 59.2\%,
and it probably will.} \marginnote[-4in]{Note that in the given
sample output shown to the left, open cells are displayed as a space, blocked
cells as a dot, and open cells through which the shortest
percolating path passes as an \texttt{X}. Alternate columns are
left blank just to make the grid look relatively square. Your
output does not have to look exactly like this.}
\marginnote[-2in]{\qrcode{You'll\ need\ to\ implement\ your\ own\
union-find\ data\ structure.}} \marginnote[-1in]{\qrcode{Get\ it\
to\ percolate\ first;\ then\ worry\ about\ finding\ the\ shortest\
path.}} \marginnote{\qrcode{The\ idea\ for\ this\ homework\ came\
from\ Robert\ Sedgewick's\ Coursera\ course\ on\ Algorithms;\ see\
http://bit.ly/2lbATcb\ for\ more\ ideas\ and\ hints.}} You should
write a program (using a language of your choice) which will explore
this percolation model, producing output like the above. That is,
your program should carry out the above random cell-opening procedure
until the grid percolates, and then display the resulting grid along
with the shortest percolating path. For full credit, your program must
be able to complete relatively quickly (within a few seconds) for a
$500 \times 500$ grid.
% \url{https://www.coursera.org/learn/algorithms-part1/lecture/OLXM8/union-find-applications}
\end{document}