I just finished installing and configuring Ubuntu 10.10 on my netbook (ASUS Eee PC 1215n). It's running amazingly fast!
I had some trouble getting my touchpad to work correctly, it totally freaked out when I touched it with two fingers... And two-finger scrolling is a must-have feature. So after an hour searching the internet, and trying all kinds of fixes I finally found the correct one.
It seems Ubuntu doesn't recognize it as a multi-touch enabled Synaptics Touchpad, so all the two-finger scrolling options are disabled. Besides that, the pressure values were far from correct for this touchpad, which explains the eratic behaviour when touched with two fingers.
So, correcting the pressure values and enabling two-finger scrolling via the terminal fixed all issues.
There was just one other issue: the changes aren't permanent... So after a reboot, the touchpad is back to being eratic when touched with two fingers.
So I made myself a script, and configured that to run on startup.
The only thing now is Nvidia Optimus support for Linux. But it seems a lot will have to be changed for it to work as nice as on Windows 7.
Wednesday, October 27, 2010
Friday, October 15, 2010
Subsequences in Prolog
Today, I was again programming in Prolog. And I found some really nice way of generating all subsequences of a given list.
At first, I didn't have the faintest idea how to do this in a logical programming language. I was again thinking way to procedural. The effect: my solutions didn't work, and I wasted about 3 hours figuring out why.
But I had a break-through! I finally looked at the problem in the correct way, the declarative way, and decided to write down what was true about a subsequence.
First of all, the basic case: a subsequence of an empty list. That's not hard, because it's empty too.
So: subsequence([],[]).
But then, what if the list wasn't empty?
Then the idea just popped into my mind, I can use one of the characteristics of a subsequence; it's order! I defined a subsequence of a list like this:
subsequence([H|T],[H|T2]) :- subsequence(T,T2).
subsequence([H|T],[H2|T2]) :- subsequence(T,[H2|T2]).
subsequence([],[]).
So this will try to match both lists' heads, and if so, then the subsequence of the tail of the first list, T, should be the tail of the second list T2.
If not, then the sublist of the tail of the first list, was still the same sublist as the one for the complete first list.
It turned out that my first try was very close to being perfect but I was missing some results.
The problem was in my last statement: subsequence([],[]).
This forced the last element of the subsequence of a list, to be the same as the last element of the original list. So I found out that it didn't matter how large the original list was, I already found a valid subsequence if I encountered an empty subsequence. Because an empty list is always a subsequence of any list.
So changing my last statement to: subsequence(_,[]). Fixed all my problems!
Wednesday, October 13, 2010
Prolog, logic programming
Today, I'm programming in Prolog. Prolog is a logic programming language designed to be very declarative instead of procedural. Basically it's programming in First Order Logic.
So today I've just finished building a predicate (function) which will display the sum of a list of numbers.
It works like this:
The predicate is defined as sumOf(List, Sum). The parameter Sum is for output only. Seeing this is a declarative language, let's start by defining a simple case: the sum of an empty list. You can see this will always turn out to be zero.
Let's integrate this in Prolog: sumOf([],0). Easy right?
Now let's define all the other cases. We've got to find some definition for expressing the sum of a given list.
In my case, I ended up like this:
sumOf([Head|Tail],Sum) :- sumOf(Tail,S2), Sum is Head + S2.
So, in english, this translates to: the Sum of a list, with a Head and a Tail, implies that we must have the sum, S2, of the Tail, and then the Sum must be the Head plus S2.
If you've ever done any functional or logical programming you'll probably see these 2 lines of code combined will recursively take the first element of the list until an empty list is encountered, then the sum will be zero. This will give the algorithm a starting point for the total sum, as now the algorithm will add all the list heads to this zero, eventually giving you the sum of the list.
The idea behind this declarative programming style is quite nice, and it's awesome that you can solve such a problem with just 2 lines of code. The problem is that I worked on those 2 lines for about 3 hours. I could easily solve this program using Java in about 5 minutes, writing 10-20 lines of code.
And that's the problem when programming in a functional or logical language; it takes loads of time.
So today I've just finished building a predicate (function) which will display the sum of a list of numbers.
It works like this:
The predicate is defined as sumOf(List, Sum). The parameter Sum is for output only. Seeing this is a declarative language, let's start by defining a simple case: the sum of an empty list. You can see this will always turn out to be zero.
Let's integrate this in Prolog: sumOf([],0). Easy right?
Now let's define all the other cases. We've got to find some definition for expressing the sum of a given list.
In my case, I ended up like this:
sumOf([Head|Tail],Sum) :- sumOf(Tail,S2), Sum is Head + S2.
So, in english, this translates to: the Sum of a list, with a Head and a Tail, implies that we must have the sum, S2, of the Tail, and then the Sum must be the Head plus S2.
If you've ever done any functional or logical programming you'll probably see these 2 lines of code combined will recursively take the first element of the list until an empty list is encountered, then the sum will be zero. This will give the algorithm a starting point for the total sum, as now the algorithm will add all the list heads to this zero, eventually giving you the sum of the list.
The idea behind this declarative programming style is quite nice, and it's awesome that you can solve such a problem with just 2 lines of code. The problem is that I worked on those 2 lines for about 3 hours. I could easily solve this program using Java in about 5 minutes, writing 10-20 lines of code.
And that's the problem when programming in a functional or logical language; it takes loads of time.
First Post, the Edit Distance problem
Welcome on this blog about my life as an allround programmer. I will be discussing most of the programming related subjects I encounter.
So, let's start right away! I can warn you, it's not the easiest of subjects, but it's what I did today.
I've built an efficient algorithm for solving the Edit Distance problem.
Basically the Edit Distance represents the "distance" between two words. Most of the time it's the number of operations required to get from one word to the other.
It seems like a simple problem, but the difficulty rests in finding an optimal solution. In this case, the minimal Edit Distance.
When you've got some experience designing algorithms for complicated problems you might already see that this problem will have a high complexity.
But, the complexity can be heavily reduced by using a technique called Dynamic Programming.
In essence it's a technique which stores results of subproblems to later combine these and form the final result for the complete problem.
This requires the problem to have a so called Optimal Substructure. In short this means the main problem can be divided in smaller, overlapping subproblems, which can be combined to calculate the main problems solution.
This is done by recursively solving all the subproblems, and storing their results in for example an array.
So you've got to build a recurrent algorithm for solving the subproblems.
In the case of the Edit Distance problem we can say that the distance between words w1 and w2 can be expressed as the distance between w1' and w2 + the costs of doing the operation w1 -> w1'.
Common operations are:
When the Edit Distances of all the possible stages in the algorithm are calculated, we can easily walk through our array of results and find the shortest Edit Distance, and the list of operations it's using.
Interesting stuff eh?
Be sure to Google it for more specific information and examples.
So, let's start right away! I can warn you, it's not the easiest of subjects, but it's what I did today.
I've built an efficient algorithm for solving the Edit Distance problem.
Basically the Edit Distance represents the "distance" between two words. Most of the time it's the number of operations required to get from one word to the other.
It seems like a simple problem, but the difficulty rests in finding an optimal solution. In this case, the minimal Edit Distance.
When you've got some experience designing algorithms for complicated problems you might already see that this problem will have a high complexity.
But, the complexity can be heavily reduced by using a technique called Dynamic Programming.
In essence it's a technique which stores results of subproblems to later combine these and form the final result for the complete problem.
This requires the problem to have a so called Optimal Substructure. In short this means the main problem can be divided in smaller, overlapping subproblems, which can be combined to calculate the main problems solution.
This is done by recursively solving all the subproblems, and storing their results in for example an array.
So you've got to build a recurrent algorithm for solving the subproblems.
In the case of the Edit Distance problem we can say that the distance between words w1 and w2 can be expressed as the distance between w1' and w2 + the costs of doing the operation w1 -> w1'.
Common operations are:
- Copy, which can only be applied when the characters at a given position in w1 and w2 are the same.
- Replace, which replaces the character in w1 by the character in w2.
- Delete, which deletes a character
- Insert, which inserts a character
When the Edit Distances of all the possible stages in the algorithm are calculated, we can easily walk through our array of results and find the shortest Edit Distance, and the list of operations it's using.
Interesting stuff eh?
Be sure to Google it for more specific information and examples.
Published with Blogger-droid v1.6.3
Subscribe to:
Posts (Atom)