Saturday, September 7, 2013

MOOCs: Solved Randomized Queues and Deques assignment

I finished this afternoon the second assignment from Princeton's Algorithms I course in Coursera.
This time we had to develop two generic data types: a Randomized Queue and a Deque.

These were the assesment tests results:
Compilation:  PASSED
Style:        PASSED
Findbugs:     No potential bugs found.
API:          PASSED

Correctness:  32/32 tests passed
Memory:       47/47 tests passed
Timing:       24/24 tests passed

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

As in every assignment of this course, the APIs were already fixed by the professors and there were several memory and time constraints for each operation of both generic data types.

I'm using TDD to get to my solutions and, even though, having the APIs predefined kills the fun in the programming by intention part of TDD, I've still found this technique very useful.

Developing the Deque with TDD was very smooth.
I started driving my code with just the pre-defined idea of using a linked list to meet the memory and time requirements. For me, it was nice to see how far the tests could take without even have to create a linked list inside the Deque. Later on I got to a test that drove me to realize that I needed a double-linked list instead.
Having said that, I must admit that I wasn't able to find a way to put that double-linked list in place using baby steps. So I just cheated and did a big change to make the new test pass while keeping the previous tests in green.

A couple of days later, I started developing the Randomized Queue and, in this case, TDD wasn't smooth at all.
I think that the culprit was the fact that we were forced to use a static method of the provided stdlib library to generate random numbers. The fixed APIs plus the static random numbers generation made it very difficult to test the Randomized Queue.
My way around was feeding the queue with integers in ascending order, then using the random number generation function with a given seed to know which of them will be dequeued, and finally resetting the random number generation function with the same seed before calling dequeue several times. This is hardly TDD and the resulting tests were very ugly.

Another thing that I didn't TDD was the resizing of the array implemented inside the Randomized Queue. I just put it there and used the tests to know eveything was still working. Now, I realized that I could have made the array public for a while in order to develop that feature using TDD, and deleted the test once it was working and made the array private again. Well, I'll try this approach next time.

That's all. I'm still enjoying the course and I'm looking forward to start the new assignment: Collinear Points.


  1. any chance you can send me the code so I can study it?

    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