Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

My Photo
Name:
Location: Toronto, Ontario, Canada

Ask Google.

Contact info
Google
Hacker Emblem Become a Friend of GNOME I Power Blogger
follow me on Twitter
Archives
July 2003
August 2003
October 2003
November 2003
December 2003
March 2004
April 2004
May 2004
July 2004
August 2004
September 2004
November 2004
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008
May 2008
June 2008
July 2008
August 2008
October 2008
November 2008
December 2008
January 2009
March 2009
April 2009
May 2009
June 2009
July 2009
August 2009
November 2009
December 2009
March 2010
April 2010
May 2010
June 2010
July 2010
October 2010
November 2010
April 2011
May 2011
August 2011
September 2011
October 2011
November 2011
November 2012
June 2013
January 2014
May 2015
Current Posts
McEs, A Hacker Life
Friday, June 29, 2007
 Congrats on Releases

Congrats to the FSF for releasing GPLv3.

Congrats to Greg Wilon and Andy Oram for their new book Beautiful Code : Leading Programmers Explain How They Think. Looking forward to read it. Greg, thanks for the party yesterday!

I blogged about Greg's previous book Data Crunching. Andy's interesting article The desktop I'd like to see.

Labels: , , , , , ,

 Thanks p.g.o

I enjoyed reading p.g.o last night at 6am when I had problem sleeping. Thank you all.

Luis's GPLv3 FAQ series was intense but a very good read.

Iago's first post on p.g.o made me discover Igalia's GNOME Build Bot which is amazingly useful. It performs code coverage analysis for the test suite on all GNOME modules. Ashamed by Pango's lack of any test suite, but cairo's doing pretty good. Thanks Iago.

Clare, good point about mail boxes. And "Planet GNOME-rs" are called Pigeons.

Jamin, good job. I wish I could sing Cash.

Heading to Ottawa/Montreal tomorrow morning for Canada Day and Montreal Jazz Festival. Hope to see the OLS crowd too.

Labels: , , ,

Wednesday, June 27, 2007
 UK

My UK visa arrived this morning at 9. I sent the package out to Ottawa the day before yesterday, in the afternoon! Very, very, nice of them.

So I'm going from my deferred schedule to original schedule. all things going as planned (and not much is left), I'll be at Text Layout 2007 / aKademy, LUG Radio Live!, and last but not least, GUADEC.

Interviews:

Interview with Hans Reiser in prison. Quite touching, particularly the closing.

Mehdi, an Iranian Free Software evangelist interviewed me a few weeks ago, it's up on Hezardastan (Persian).

Labels: , , , , , ,

Wednesday, June 20, 2007
 Debian Patch Review

Thanks everyone for comments on JDS patch review yesterday. Thanks to lool for the link, I reviewed Debian's pango and vte patches this morning on the way to office.All in all, seems like someone's been doing their homework. Nice!

Who's next? It could be you!

Labels: , ,

Tuesday, June 19, 2007
 JDS Patch Review

(Note: After receiving two comments and rereading my previous post, I removed it in accordance to CoC which I have volunteerly signed. Well, we're cool now.)

Seeing people commenting on JDS patches for their packages, I couldn't help but checking pango, cairo, and vte patches they ship. Having reviewed them, I thought I should provide some feedback :). I'm posting here, hoping that other GNOME hackers pick this up too. Later we can move on to collectively review other vendors' patches too, and help the over-busy maintainers push the right patches upstream and drop/fix the wrong ones. Not every project has a sebuild, right? ;) Brian Cameron has been doing a great job doing that for opensolaris already, but there's more room.
All in all, very good for cairo, but can do better for vte and pango.

Labels: , , ,

 Tomato Paste

Nice photo of Iranian woman making tomato paste, by Amin Nazari here.

(Update: the embedded image was not working; linked now.)

Labels: ,

 Skydiving

Skydiving: Arch!

Labels: ,

Tuesday, June 12, 2007
 Unicode 5.0 PDFs

Are now available on the Unicode website. Enjoy!

(and check the Acknowledgements!)

Labels: ,

Sunday, June 03, 2007
 12 or 13 Cairo Demo

Speaking of puzzles, remember the 12 or 13 puzzle? (solution).

Back then I wrote some PyCairo code to illustrate it. Finally pushed it into cairo-demo CVS repo. Browse here. It helps understanding exactly how the puzzle works, and you can design your own ones. Just missing animated-GIF support in cairo to save the result...

Saturday, June 02, 2007
 PUZZLE SOLUTION: Group Strategy

This is the solution to the puzzle Group Strategy that I posted a few weeks ago. Make sure you give it a try before reading further.

Intro:

There are multiple ways one can approach the solution. Some need more combinatorial background than the others. One intuitive way that Carl Worth suggested was: what should the strategy look like if we want to make sure that the identity permutation always leads to success? Easy, each man should make sure to look into the box numbered as himself. Now what if the permutation is not identity, but identity plus one swap? Continue...

Another approach is probabilistic. Any strategy that has each man's rate of success in finding his number be probabilistically independent of the others is destined to fail with a total success rate of at most 2^-2k. So, in any winning strategy, the success rate of the men are not independent. A corollary is that no man should know which boxes he's going to open until after he entered the room. Think about it (and no, don't think about random strategies).

Strategy:

So here is the winning strategy: Each man enters the room, opens the box numbered as himself and reads the paper inside; while not found, he then opens the box with the number written on piece of paper in the last box he opened.

Of course, every man still has the exact same rate of individual success: 1/2, but what the algorithm does is to kinda "align" their success runs together so as a group they succeed with a surprisingly huge probability: more than 30%!

Proof:

The algorithm becomes a lot more intuitive if one imagines the graph representation of the permutation that the boxes represent. The graph representation of our permutation has 2k nodes, and node i has an edge towards node j if number j is in box i. This is a directed graph.

Permutation graphs are always a set of (possibly size 1) cycles because each node has in and out degrees of exactly one. The man numbered i wants to find the node that has an outgoing edge to i. Well, looking at the problem this way, the strategy is trivial: start from node i and follow the cycle, until you get back to i. That's all everyone has got to do!

The success probability of the group is equal to the probability that the permutation graph has no cycle longer than k. And since there are only 2k nodes and each node is in exactly one cycle, there can exist at most one cycle longer than k. The question is: what is the probability that a cycle longer than k exists. This is the failure probability.

Getting this far you can claim having solved the puzzle! Now to get a tight bound: I used straight counting. Failure probability is the sum of probability that a cycle of size c exists, for c from k+1 to 2k. The probability that such a cycle exists is the number of permutations with such a cycle divided by total number of permutations (2k!). Finally lets count how many such permutations exist: Choose c members for the cycle and divide by c because the order is not important: 2k! / ((2k-c)! * c). Finally permute the remaining members: (2k-c)!. It simplifies drastically and at the end, failure probability becomes exactly H(2k) - H(k), where H(n) is the n'th Harmonic number. A tight upper bound to this failure probability is ln(2k) - ln(k), which is ln(2). So, success probability is not less than 1 - ln(2), which is a bit over 30%.

The math set using my embedded TeX engine (click for other sizes):

Group Strategy


Update:

Proof that the bound is tight: While failure probability is not more than ln(2k) - ln(k), using the same idea, it's not less than ln(2k+1) - ln(k+1). So, success probability is between 1 - ln(2) and 1 - ln(2 - 1/(k+1)).

Labels: ,

Friday, June 01, 2007
 I'm a Coffee Fool!

It all started when I decided to drink dark and bitter. I soon realized that only coffee from the best coffee shops can be consumed that way without stinking.

Then in the microwave bug Karl Lattimer pointed out the humorous Coffee Making Howto, which then led to me finding and carefully reading the Coffee FAQ. And soon after I hit the Coffee Fool page that accurately describes my syndrome.

Since then coffee has become one of my main interests. At this time I'm still experimenting and trying to find out which machine suits me best.

Labels: ,

 Enjoyable Sharpness of Being

After losing my last pair of glasses during camping two weeks ago I finally got my new shiny ones today. Enjoying all the sharness and all, be it the girl walking in subway or the cup of coffee. Love this feeling every time.

(Also means I don't have to stare at the monitor anymore, not unless it's really late at night)

Labels: