How to handle the backwash problem in percolation without creating an extra WUF object or using a method with complexity >= O(n)?

Question

I am taking the Algorithms, Part I course on coursera and am stuck on a bonus question of the first assignment. I have already submitted my solution and got my marks. This is just for curiosity.

Backwash is appearance of the crossed sites as full (blue) in this image. This happens because I am using virtual top and bottom nodes and connecting the rows below/above them to meet the complexity requirements; so, connecting the top to the bottom makes all the nodes connected to the bottom get connected to the top. This description might appear incomplete so I strongly suggest reading the specs link.

A solution to overcoming this is to use another WeightedQuickUnion object and duplicate the grid in it without including the bottom virtual node. Now, this solution doesn't meet the memory requirements of the grader for the bonus question (check that total memory <= 11 n^2 + 128 n + 1024 bytes). I have thought of some workarounds (like using an array/stack to store the open sites of the bottom row) but all of them use an extra method that has complexity O(n) whereas the assignment doesn't permit that. As per the assignment specs, other than constructor all methods should have a constant time + constant number of calls to union() and find().

Answer 1

You can get rid of the virtual sites altogether.

Maintain a byte array where the i^th element stores data of the i^th node/site in the WeightedQuickUnionUF object.

Each element of the array will store 3 bits.

• One representing if the site is open.
• Another representing if the subtree rooted at i is connected to the top through open sites.
• Another representing if the subtree rooted at i is connected to the bottom through open sites.

Bit manipulation will come handy in utilising this array.

Set the bits appropriately when opening a previously blocked site. Update the data of the new root with the OR of the data of the previous roots, when performing the union() of two sites.

The isFull() and percolates() status of a connected component is conveyed by the data of the canonical element or the root of that component.

In the open() method, after opening a previously blocked site check if the updated connected component causes the system to percolate and store the result. Return this stored value in the percolates() method.

You'll find this pdf useful. Search for "backwash" in the document.

ps: I have received the bonus points using this solution.

Cheers!

Answer 2

I used an int[] cast to bytes to track the status of each site:

• 000 designates a closed site,
• 100 an open site,
• 110 an open site connected to top (so located on the top row i==1) and
• 101 for a site connected to the bottom row (i==n).

On every call to open() I retrieved the canonical element of the site (rootPrevious), of its adjacent (rootAdjacent), before calling wquf.union(adjacent,site).

Then I retrieved the newRoot of site wquf.find(site) again (as It may have changed post the WeightedQuickUnionFind balancing).

Finally I used the inclusive bitwise OR combinator | to combine the status of all the sites into a resulting status, which I used to update the status of all the involved sites. That's a cheap constant time operation which saves heaps for the isFull() and percolation(). You can see it as a "contamination / spread" of status among all the involved sites.

Then before leaving open() I queried the status of site to check if It was equal to 111 (an open site that is both connected to top and bottom) and store this boolean in a doesPercolate field that is the returned by percolation() as p7x indicated.

et voila!

Aggregate score: 101.25% Estimated student memory = 9.00 n^2 + 0.00 n + 192.00 (R^2 = 1.000)

The rest is exactly as per p7x suggestions above. PS: Smelly code cast int[] instead of a byte[] agreed, but saved me bitwise arithmetics for now anyway.

Answer 3

Okay,for those who are still confused with the above answers, here's a bit more explanation to what others have already detailed.

• Instead of keeping track of just whether a site is open or blocked. We are keeping track of three states: open/closed, connected to top or not, connected to bottom or not.

  Here's how I did it:

  

  Note the integer values of the binary states. Doing bit-wise OR | of these integers can give us the appropriate status when opening a site and doing status updates. (To save memory, you can use byte[], instead of int[] to store the status for each site.)

• When opening a site, use a variable, say status and set it to 4 (equals (100)₂) initially. Find its adjacent sites that are open and union with those sites. But before making the union, retrieve the status of their roots and do a bit-wise OR with our status variable.

  Thus, after making all the unions, you will get the actual status to be updated, for the entire connected component. Set this status to the new root of the site we opened. We can also set the same status to the actual index location of the site we opened.

  Whenever we get status = 7, it means the system has percolated.

  However, note that since we are NOT updating status of all elements in a connected component, we can use status of the actual index location of a site only to check whether it is open or not, (status != 0).

  So, if we want to get the complete status of an element (e.g. isFull()), we have to retrieve the status from its root.

  (Another thing to be noted is that, we have to initialize status to 6 (not 4) if we're opening an element in the top row, and to 5 if we're opening an element in the bottom row. A corner case is when n = 1, i.e top and bottom row is the same.)

  With this approach there will be 5 find() calls and at most 4 union() calls in open(), and 1 find() call in isFull(). Except open(). It passes all memory and timing tests.

  (I got Estimated student memory = 9.00 n^2 + 0.00 n + 168.00 (R^2 = 1.000), and Aggregate score: 101.25%)