Thursday, October 16, 2008

Pujo 2008 Pictures

Some of the pictures taken during the 2008 Durga Puja in Kolkata.

 

All the pictures have been uploaded to Picasa, you may download the entire album from there. Link to Pujo 2008 Picasa Web Album.

Please note that the pictures are licensed under the Creative Commons International licensing. All pictures are licensed under the terms "Attribution + Noncommercial + NoDerivs (by-nc-nd)", as mentioned in Creative Commons licenses.

Monday, October 13, 2008

Fedora 9, Sulphur

After using Open Solaris for more than a year, I have switched back to Fedora once again. I was using Solaris, as it was compatible with the version of Solaris that we used in University of Calcutta. However, after my second year was over, I had no good reasons to stick to it. In any case, I did not use Solaris's USP features of D-Trace and ZFS in day to day work. So I finally decided to switch back to Fedora.

Although I did not use it, I had Fedora 8 installed on my machine. I installed the latest Fedora release, Fedora 9 Sulphur in that place. I know its pretty late talking about Fedora 9, as its sibling Fedora 10 is about to launch in another two months, but having used Fedora 7 Moonshine last, I was in for a few surprises.

Network Manager

If I remember correctly, Network manager was there in Fedora 5 or Fedora 6, but was not activated by default. In later releases it was dropped altogether. However, it has resurfaced in Sulphur. Placed in the top left corner of the Gnome panel, it is a very effective piece of software which let me use my ADSL connection right out of the box. One of the most daunting tasks with Linux, was to get my ADSL connection to work with it. This was a pleasant surprise. I am sure it will continue to retain its place in future releases too.

Security Enhanced Linux

It was customary in the first boot of Fedora to be confronted with a SELinux screen, which most users disabled without a second thought. This time, this screen has been removed and I think is one of the smartest move in Fedora's part.

GCC v4.3

Fedora 9 ships with GCC 4.3. This causes some applications which were compiled with an older GCC to fail. So make sure you have the compatibility libraries. Just type "yum -y install compat-libstdc++-33 compat-libstdc++-296" in a terminal, when logged in as root.

Flash Plugin in x86_64

If you are using the 64 bit version of Sulphur like me, then installing the flash plugin for your browser is a bit complicated. Here are the detailed step by step instructions for it. Ensure that you are logged in as root (do not sudo) and can connect to internet. Type the following in the terminal:

  1. rpm -ivh http://linuxdownload.adobe.com/adobe-release/adobe-release-i386-1.0-1.noarch.rpm
  2. rpm --import /etc/pki/rpm-gpg/RPM-GPG-KEY-adobe-linux
  3. mkdir -p /usr/lib/mozilla/plugins
  4. yum install nspluginwrapper.{i386,x86_64}
  5. yum install pulseaudio-libs.i386
  6. yum install libflashsupport.i386
  7. yum install flash-plugin
  8. mozilla-plugin-config -i -g -v

It took me quite sometime to figure this out. I hope this will be fixed in Fedora 10 Cambridge. But for now, you have to undergo this tedious process. If anyone knows a shorter process, please post a comment.

Further Softwares

On top of the usual packages that came through DVD, I also installed the following:

  • Adobe Acrobat 8 for reading PDF, as the default PDF reader lacks many features
  • VLC Media Player
  • mPlayer
  • MP3 plugins from the Livna repository
  • Firefox (updated the beta version) and a few plugins
  • Azureus
  • Applied all the recommended security patches

I also installed the following which are required for programming purposes:

  • Anjuta
  • gProlog

What's next?

I do not think I need to do any further major tweaking to Sulphur. I am looking forward to the release of Fedora 10 Cambridge at the end of November this year. Presently the beta version of Cambridge is available for download and I recommend everybody to try it out using the live media so that the installation can be avoided.

Friday, October 10, 2008

Subho Bijoya

Subho Bijoya 08

Subho Bijoya and best wishes to everybody. Pronam & Regards to my elders. E-kola-kuli to all my friends.

Monday, October 06, 2008

KND's game of 15

Kashi Nath Dey (KND) is a professor of University of Calcutta in the Department of Computer Science and Engineering. He teaches Artificial Intelligence (AI) to us. In his last class before the Puja Vacations, he showed us the following interesting game that he has invented. The game has no formal name, so I took the liberty of calling it "KND's game of 15".

The Game

This is a 2 person finite game with the following simple rules:

  1. 2 players take alternate turns in selecting a number from the set 1 to 9
  2. A number once selected, is not available for further selection
  3. If any 3 numbers from each player's selected number sets have a summation of 15 then that player is declared as winner
  4. Play continues, till any one of the player wins OR the number set is exhausted, in which case the game is declared to be a draw

As with any new game, we tried our hands at it in no time. Here are a few games that we played:

KND 2 6 8 1 W
Class 9 7 5    

 

 

 

KND won the game as 6+8+1 = 15. If you notice carefully, its very easy to see a pattern in KND's game. He started with 2 and then for every move made by class, he just put 15 minus the number. However, this is just a coincidence as we will see in the next game:

KND 8 2 4 9 W
Class 6 5 3    

 

 

 

This time too, KND won the game as 2+9+4 = 15. What is more important to note is that our last strategy was not what he had followed in this game. By this time our class mate Sumeet was convinced that whoever plays first would win, so in the next game, KND took the second move:

Class 5 8 7 9 D
KND 6 2 3 1 D

 

 

 

The game was a draw. So the player playing first does not always win. Somehow, I was feeling that there might be a strategy that allows the first player to win every time he plays.

My Analysis

The game is no doubt, very interesting. A careful study of it would soon reveal many facts which would help a lot in the gameplay. The first task in analyzing would be to jot down all such 3 number combinations which total in 15:

1 6 8
1 5 9
2 4 9
2 6 7
2 5 8
3 4 8
3 5 7
4 5 6

 

 

 

 

 

 

 

 

 

Next we do a simple frequency analysis and get the following result:

Number Frequency
1 2
2 3
3 2
4 3
5 4
6 3
7 2
8 3
9 2

 

 

 

 

 

 

 

 

 

 



I did both of these steps in class and arrived at the conclusion that 5 is the most frequently occurring number, so the player who chooses it first has a distinct advantage over the other. Next in priority were the set {2,4,6,8,} all of which have frequency of 3. Last comes the set {1,3,7,9}, all of which have the frequency of 2.

My Strategy

So I deduced a strategy that try and capture the numbers in that order, and then from the 2nd number onwards try to block your opponent's chance of winning by capturing the number that would get him a total of 15, and simultaneously look out for numbers that would get me a total of 15.

KND's Explanation

I used my newly formulated strategy to get a draw in the last match and was feeling quite happy with myself. Then, KND offered an alternate and much simpler explanation of the game. He first drew a 3x3 magic square:

8 1 6
3 5 7
4 9 2

 

 

 

 

As with any magic square this one also has a constant summation over rows, columns and major diagonals. In this case, the summation happens to be 15. Now what KND has done in this game is to merge it with popular children's game of Tic-Tac-Toe. So selecting a number implies putting a 0 or X in that position in this 3x3 board. What follows is a simple game of Tic-Tac-Toe.

Conclusion

The explanation is very elegant and simple. I liked it very much, both the game and the explanation behind it. It just shows how some apparently very different problems can be mapped in to one another. Interestingly, I knew all of the things that he required to explain the logic behind the game:

  • Magic Squares, and how to generate them. I even knew the 3x3 square by heart and managed to remembered that the constant was 15 !!
  • Tic-Tac-Toe

The key to arriving at the correct explanation is to think harder for simpler explanation. In fact looking back, it was easy to guess that there was some simple strategy as KND did not take much time to make his moves, which he would require if he followed my type of complicated strategy.

For the last few days I have showed this to some of my friends. With the same result, all of them tried to think of a complicated strategy. Sometimes I introduced a minor variation of showing the same thing with 9 playing cards, which makes it a card game.

Thursday, October 02, 2008

Primality of a Number is NP problem

Primality testing of a number is the method of finding out whether a number is prime or not. I have known this is a non-polynomial problem. In fact most of the recent cryptographic techniques rely on this and the factoring problem of numbers to create secure systems.

But it was never clear to me why. So when this question was put forward to me by Sukanta, I kept thinking. Of course I knew the answer, but did not know the reason for this problem to be NP. Sukanta explained that:

For a number N, the usual prime number testing strategies, iterate for N/2 times, which can be further optimized to N^0.5. So the number of division operations required was a polynomial function of N. At this point, it is very easy to say that this is polynomial solvable.

But the thing that I missed here, is that N was the number itself, not the size of the input set on which the complexity of a program is computed. So if we take the input size as the number of digits of N, then the size of input set is log N. So the complexity of the program is exponential, and not polynomial, as I mistook in last step.

Well, there is never any shortage of new things to learn. I thank Sukanta, who explained it in such a nice way. However, what astonished me was that I had believed the result without even asking for the explanation of the same. So I made a mental note to watch out for similar pitfalls in future.

MS Ads with Jerry Seinfeld

Here are two Microsoft Advertisements that featured American comedian Jerry Seinfeld, whom Microsoft hired and caused a lot of speculation. However, he has been recently axed from the campaign, leaving everybody wondering, what the Microsoft Advertisements guys are really upto.

 

 

I personally both of them, specially the way that they are showing Gates.