Coursera - Algorithms I - Assignment 1

See the Assessment Guide for information on how to interpret this report.

Assessment Summary

Compilation: PASSED Checkstyle: PASSED Findbugs: PASSED API: PASSED

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

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

Assessment Details

5.2K Dec 31 22:30 Percolation.java 2.3K Dec 31 22:30 PercolationStats.java 2.4K Dec 31 22:30 studentSubmission.zip

• COMPILING *

% javac Percolation.java *-----------------------------------------------------------

% javac PercolationStats.java *-----------------------------------------------------------

================================================================

% checkstyle *.java *-----------------------------------------------------------

================================================================

% findbugs *.class *-----------------------------------------------------------

================================================================

Testing the APIs of your programs. *----------------------------------------------------------- Percolation:

PercolationStats:

================================================================

• TESTING CORRECTNESS

Testing correctness of Percolation *----------------------------------------------------------- Running 15 total tests.

Tests 1 through 8 create a Percolation object using your code, then repeatedly open sites by calling open(). After each call to open(), we check the return values of isOpen(i, j) for every (i, j), the return value of percolates(), and the return value of isFull(i, j) for every (i, j), in that order.

Except as noted, a site is opened at most once.

Test 1: Open predetermined list of sites using file inputs

• filename = input6.txt
• filename = input8.txt
• filename = input8-no.txt
• filename = input10-no.txt
• filename = greeting57.txt
• filename = heart25.txt ==> passed

Test 2: Open random sites until just before system percolates

• n = 3
• n = 5
• n = 10
• n = 10
• n = 20
• n = 20
• n = 50
• n = 50 ==> passed

Test 3: Opens predetermined sites for n = 1 and n = 2 (corner case test)

• filename = input1.txt
• filename = input1-no.txt
• filename = input2.txt
• filename = input2-no.txt ==> passed

Test 4: Check for backwash with predetermined sites

• filename = input20.txt
• filename = input10.txt
• filename = input50.txt
• filename = jerry47.txt ==> passed

Test 5: Check for backwash with predetermined sites that have multiple percolating paths

• filename = input3.txt
• filename = input4.txt
• filename = input7.txt ==> passed

Test 6: Predetermined sites with long percolating path

• filename = snake13.txt
• filename = snake101.txt ==> passed

Test 7: Opens every site

• filename = input5.txt ==> passed

Test 8: Open random sites until just before system percolates, allowing open() to be called on a site more than once

• n = 3
• n = 5
• n = 10
• n = 10
• n = 20
• n = 20
• n = 50
• n = 50 ==> passed

Test 9: Check that IndexOutOfBoundsException is thrown if (i, j) is out of bounds

• n = 10, (i, j) = (0, 6)
• n = 10, (i, j) = (12, 6)
• n = 10, (i, j) = (11, 6)
• n = 10, (i, j) = (6, 0)
• n = 10, (i, j) = (6, 12)
• n = 10, (i, j) = (6, 11) ==> passed

Test 10: Check that IllegalArgumentException is thrown if N <= 0 in constructor

• n = -10
• n = -1
• n = 0 ==> passed

Test 11: Create multiple Percolation objects at the same time (to make sure you didn't store data in static variables) ==> passed

Test 12: Open predetermined list of sites using file inputs, but change the order in which methods are called

• filename = input8.txt; order = isFull(), isOpen(), percolates()
• filename = input8.txt; order = isFull(), percolates(), isOpen()
• filename = input8.txt; order = isOpen(), isFull(), percolates()
• filename = input8.txt; order = isOpen(), percolates(), isFull()
• filename = input8.txt; order = percolates(), isOpen(), isFull()
• filename = input8.txt; order = percolates(), isFull(), isOpen() ==> passed

Test 13: Call all methods in random order until just before system percolates

• n = 3
• n = 5
• n = 7
• n = 10
• n = 20
• n = 50 ==> passed

Test 14: Call all methods in random order until almost all sites are open, but with inputs not prone to backwash

• n = 3
• n = 5
• n = 7
• n = 10
• n = 20
• n = 50 ==> passed

Test 15: Call all methods in random order until all sites are open, allowing open() to be called on a site more than once (these inputs are prone to backwash)

• n = 3
• n = 5
• n = 7
• n = 10
• n = 20
• n = 50 ==> passed

Total: 15/15 tests passed!

================================================================

• TESTING CORRECTNESS (substituting reference Percolation)

Testing correctness of PercolationStats *----------------------------------------------------------- Running 11 total tests.

Test 1: Test that PercolationStats creates trials Percolation objects, each of size n-by-n

• n = 20, trials = 10
• n = 50, trials = 20
• n = 100, trials = 50
• n = 64, trials = 150 ==> passed

Test 2: Test that PercolationStats calls open() until system percolates

• n = 20, trials = 10
• n = 50, trials = 20
• n = 100, trials = 50
• n = 64, trials = 150 ==> passed

Test 3: Test that PercolationStats does not call open() after system percolates

• n = 20, trials = 10
• n = 50, trials = 20
• n = 100, trials = 50
• n = 64, trials = 150 ==> passed

Test 4: Test that mean() is consistent with the number of intercepted calls to open() on blocked sites

• n = 20, trials = 10
• n = 50, trials = 20
• n = 100, trials = 50
• n = 64, trials = 150 ==> passed

Test 5: Test that stddev() is consistent with the number of intercepted calls to open() on blocked sites

• n = 20, trials = 10
• n = 50, trials = 20
• n = 100, trials = 50
• n = 64, trials = 150 ==> passed

Test 6: Test that confidenceLo() and confidenceHigh() are consistent with mean() and stddev()

• n = 20, trials = 10
• n = 50, trials = 20
• n = 100, trials = 50
• n = 64, trials = 150 ==> passed

Test 7: Check whether exception is thrown if either n or trials is out of bounds

• n = -23, trials = 42
• n = 23, trials = 0
• n = -42, trials = 0
• n = 42, trials = -1 ==> passed

Test 8: Create two PercolationStats objects at the same time and check mean() (to make sure you didn't store data in static variables)

• n1 = 50, trials1 = 10, n2 = 50, trials2 = 5
• n1 = 50, trials1 = 5, n2 = 50, trials2 = 10
• n1 = 50, trials1 = 10, n2 = 25, trials2 = 10
• n1 = 25, trials1 = 10, n2 = 50, trials2 = 10
• n1 = 50, trials1 = 10, n2 = 15, trials2 = 100
• n1 = 15, trials1 = 100, n2 = 50, trials2 = 10 ==> passed

Test 9: Check that the methods return the same value, regardless of the order in which they are called

• n = 20, trials = 10
• n = 50, trials = 20
• n = 100, trials = 50
• n = 64, trials = 150 ==> passed

Test 10: Check for any calls to StdRandom.setSeed()

• n = 20, trials = 10
• n = 20, trials = 10
• n = 40, trials = 10
• n = 80, trials = 10 ==> passed

Test 11: Check distribution of number of sites opened until percolation

• n = 2, trials = 100000
• n = 3, trials = 100000
• n = 4, trials = 100000 ==> passed

Total: 11/11 tests passed!

================================================================

• MEMORY (substituting reference Percolation)

Computing memory of PercolationStats *----------------------------------------------------------- Running 4 total tests.

Test 1a-1d: Memory usage as a function of trials for n = 100 (max allowed: 8*trials + 128 bytes)

        trials        bytes

=> passed 16 184
=> passed 32 312
=> passed 64 568
=> passed 128 1080
==> 4/4 tests passed

Estimated student memory = 8.00 T + 56.00 (R^2 = 1.000)

Total: 4/4 tests passed!

================================================================

• MEMORY

Computing memory of Percolation *----------------------------------------------------------- Running 4 total tests.

Test 1a-1d: Check that total memory <= 17 n^2 + 128 n + 1024 bytes

             n        bytes

=> passed 64 71976
=> passed 256 1122600
=> passed 512 4473128
=> passed 1024 17858856
==> 4/4 tests passed

Estimated student memory = 17.00 n^2 + 32.00 n + 296.00 (R^2 = 1.000)

Test 2 (bonus): Check that total memory <= 11 n^2 + 128 n + 1024 bytes

• failed memory test for n = 64 ==> FAILED

Total: 4/4 tests passed!

================================================================

• TIMING

Timing Percolation *----------------------------------------------------------- Running 9 total tests.

=> passed 8 0.00 124 250 2
=> passed 32 0.00 1501 3092 2
=> passed 128 0.01 22515 48006 2
=> passed 512 0.06 370380 785726 2
=> passed 1024 0.15 1457240 3100964 2
==> 5/5 tests passed

Running time in seconds depends on the machine on which the script runs, and varies each time that you submit. If one of the values in the table violates the performance limits, the factor by which you failed the test appears in parentheses. For example, (9.6x) in the union() column indicates that it uses 9.6x too many calls.

Tests 2a-2d: Check whether number of calls to union(), connected(), and find() is a constant per call to open(), isFull(), and percolates(). The table shows the maximum number of union(), connected(), and find() calls made during a single call to open(), isFull(), and percolates().

             n     per open()      per isOpen()    per isFull()    per percolates() 

=> passed 32 8 0 1 1
=> passed 128 8 0 1 1
=> passed 512 8 0 1 1
=> passed 1024 8 0 1 1
==> 4/4 tests passed

Total: 9/9 tests passed!

================================================================