% -*- compile-command: "rubber -d hw.5.tex" -*-
\documentclass[11pt]{tufte-handout}
\usepackage{times,graphicx,epstopdf,fancyhdr,amsfonts,amsthm,amsmath,url,xspace,algorithm,algorithmic,hyperref}

\usepackage{qrcode}

\pagestyle{fancy}

\theoremstyle{definition}
\newtheorem{question}{Question}

\begin{document}

\lhead{CSCI 280: Algorithms -- Spring 2017}
\chead{}
\rhead{Brent Yorgey}
\lfoot{Homework 5}
\cfoot{\thepage}
\rfoot{Due: 4:00pm, Friday, March 3}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\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
an open path from some cell in the top row all the way to some 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[-4in]{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[-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.  Your program should 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}