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.