Showing posts with label Algorithms. Show all posts
Showing posts with label Algorithms. Show all posts
Friday, March 31, 2017
Interesting Talk: "Solving Problems Declaratively"
I've just watched this great talk by Mark Engelberg
Saturday, September 21, 2013
MOOCs: Solved 8 Puzzle assignment
I've just solved the fourth assignment from Princeton's Algorithms I course in Coursera.
This time we had to write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
Although I didn't understand well the problem description the first time I read it, in the end, this has been the easiest assignment so far.
I used TDD to code the Board class but only tested afterwards the Solver class.
These were the assessment tests result:
This time we had to write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm.
Although I didn't understand well the problem description the first time I read it, in the end, this has been the easiest assignment so far.
I used TDD to code the Board class but only tested afterwards the Solver class.
These were the assessment tests result:
Compilation: PASSED Style: FAILED Findbugs: No potential bugs found. API: PASSED Correctness: 24/24 tests passed Memory: 8/8 tests passed Timing: 17/17 tests passed Raw score: 100.00% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]I was a bit tired so I decided not to fix the style.
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:
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:
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.
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 completionSince 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.
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:
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.
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.
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:
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:
I'm enjoying this course very much!
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!
Saturday, November 19, 2011
Dictionary of Algorithms and Data Structures
I've just found "a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions":
Since one of the courses I'm taking at the UOC is about Data Structures I think this place will prove really useful.
Since one of the courses I'm taking at the UOC is about Data Structures I think this place will prove really useful.
Sunday, June 19, 2011
Revisiting Introduction to Algorithms
I'd like to add some information to my recent post about MIT Introduction to Algorithms course.
Peteris Krumins followed this course online some time ago and posted his personal notes for every lecture in his interesting blog: Good coders code, great reuse.
Peteris Krumins followed this course online some time ago and posted his personal notes for every lecture in his interesting blog: Good coders code, great reuse.
Monday, June 13, 2011
Introduction to Algorithms
I've started to watch the videolectures from the course:
MIT 6.046J/18.410J Introduction to Algorithms (SMA 5503), Fall 2005.
You can find them on youtube or download them from the course site in the MIT OCW.
I hope to learn a bit about data structures, algorithms and complexity.
MIT 6.046J/18.410J Introduction to Algorithms (SMA 5503), Fall 2005.
You can find them on youtube or download them from the course site in the MIT OCW.
I hope to learn a bit about data structures, algorithms and complexity.
Subscribe to:
Comments (Atom)