Sunday, September 1, 2013

MOOCs: Solved "backwash" problem in Percolation assignment

I've just finished the first assignment from Princeton's Algorithms I course in Coursera.

This first assignment was to write a program to estimate the value of the percolation threshold via Monte Carlo simulation.

I thought that the solution I coded last weekend was fine because it was correctly computing the percolation thresholds for many different grid sizes.
However, when I tested it today using the provided PercolationVisualizer class, I realized that it was suffering from the "backwash" problem.


The problem was also detected by the automatic assessment tests:
Compilation:  PASSED
Style:        PASSED
Findbugs:     No potential bugs found.
API:          PASSED

Correctness:  16/20 tests passed
Memory:       8/8 tests passed
Timing:       9/9 tests passed

Raw score: 87.00% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]
There were four tests checking the backwash problem.

It took me a couple of hours but, in the end, I managed to fix it by using two WeightedQuickUnionUF objects instead of one.

This was the final result of the automatic assessment tests:
Assessment Summary
Compilation:  PASSED
Style:        PASSED
Findbugs:     No potential bugs found.
API:          PASSED

Correctness:  20/20 tests passed
Memory:       8/8 tests passed
Timing:       9/9 tests passed

Raw score: 100.00% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]

I'm enjoying this course very much!

9 comments:

  1. Hi classmate,

    I am also working on this problem.
    Using two WeightedQuickUnionUF objects works for backwash, but the memory for Percolation exceeded the requirement for a little bit.

    Mine: 20.00 N^2 + 20.00 N + 192.00 bytes
    Max allowed: 17 N^2 + 128 N + 1024 bytes

    Could you educate me how you fix that?

    Thanks a lot!

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  2. Hi

    This is the memory my program is using:

    In Percolation class:
    1. An array of size N^2 + 2 to store a boolean for each site to know if the site is open or not (N^2 real sites + two virtual ones).
    2. A WeightedQuickUnionUF object with N^2 real sites + two virtual sites.
    3. A WeightedQuickUnionUF object with N^2 real sites + one virtual site.
    4. Three ints to store sizes and important indexes.

    In PercolationStats:
    1. An array of size T to store the result of each experiment
    2. Four doubles to store the statistics results and two ints to store the grid size and number of experiments.

    I hope this helps you.

    Best regards,
    M

    ReplyDelete
  3. How you use second union-find object to avoid backwash problem?

    ReplyDelete
  4. Hi

    Think about why the backwash problem happens and its connection with a site being full.

    Best regards,
    M

    ReplyDelete
  5. Hi,

    I fixed the backwash by using two weighted union-find objects, but am now facing a memory problem, meaning all the 4 memory tests are now failing. Could you please give me a clue of what could be different in my case from your case? Thanks a lot, D.

    ReplyDelete
  6. Hi

    I don't know what could be different in your case but I described my memory usage in a previous comment. Try to compare yours with it.

    I hope that helps.

    Best regards,
    M

    ReplyDelete
    Replies
    1. I was the cookies monster before :)

      Delete
    2. I made the same mistake because I use int instead of boolean to store the open status of the cells. When I switched to boolean, the problem was solved.

      Hope it helps

      Delete