Tuesday, September 17, 2013

MOOCs: Solved Collinear Points assignment

Last Sunday I finished the third assignment from Princeton's Algorithms I course in Coursera.

The problem consisted in drawing every (maximal) line segment that connected a subset of 4 or more of the points given a set of N distinct points in a plane.

First, we had to write a brute force algorithm with order of growth N4 in the worst case that used space proportional to N. And then, we had to write a faster algorithm with order of growth N2log(N) using also space proportional to N.

This time I used TDD only for the Point class. For the Fast and Brute algorithms I wrote some unit tests afterwards that compared the program results for given inputs provided in the course site with the expected outputs.

When I submitted my solution, I started having a very frustrating problem in the Fast tests.
Although my solution seemed to be working with the provided inout files, (even with the rs1423.txt example that I'll show you later), the assessment tests were crashing after a test with random segments. This crash aborted the tests so I was getting a message saying that:
Total: 0/18 tests passed: 
Test aborted. Ran out of time or crashed before completion
Since the inputs that were making it fail were random, I couldn't get them to debug my program. I checked the code many times but I couldn't find any bug that could be causing that problem.

After asking in the course forums, I found out that it was a failure in the grading system which was overloaded by thousands of people submitting their assignments on Sunday night.

After a couple of hours, I submitted my solution again and these were the assesment tests results:
Compilation:  PASSED
Style:        PASSED
Findbugs:     No potential bugs found.
API:          PASSED

Correctness:  36/36 tests passed
Memory:       1/1 tests passed
Timing:       17/17 tests passed

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

I had spent a lot of time chasing a ghost bug but, in the end, at least it was over.
I made a mental note to myself: "don't try to submit when the grading system is too busy".

To finish, I'd like to show the picture that my program produces when it's fed with the rs1423.txt file:

It's Robert Sedgewick, the course professor.

1 comment:

  1. if you are able to send us code please do it I would like to study it, if you are able to please send me on lord_of-the_rings@hotmail.com