Lately, I have been reading famous "Sherlock Holmes" stories. What a nice piece of literature it is! Sir Arthur Conan Doyle is truly a master of creating writings that hold the reader till the end. It really takes a true genius to create such a timeless character like Sherlock Holmes.
Though, some of the inferences employed by Sherlock Holmes in unleashing the truth seems to be unrealistic, I especially admire the literature for the flair with which the author wrote it. The description of a scene creates enough impact on your mind to force it to weave a virtual world around as if you are witnessing the entire series of events. Author has put to use his vocabulary so perfectly that it does not drive away a reader with average vocabulary and yet maintaining enough variations to make it far from banal. I wish I could attain at least 1/20th of author's writing skill.
Now I know, why Sir Arthur Conan Doyle was awarded knighthood. :-)
Thursday, March 08, 2007
Monday, February 12, 2007
Bitwise fiasco
Yesterday was one of the worst day. It was the day of Bitwise 2007 . I participated in this contest with Pranjal as my team mate. I had really high hopes and a bit of arrogance as I could claim 26th rank in this prestigious contest last time amongst 2700 participating teams. Bitwise 2006 was my first official participation in a programming contest. Having done so well in my debut, I was dreaming to climb further up the ladder with Pranjal ( who secured 8th rank in Bitwise 2006 ) along the side.
The arrogance had fogged the part of the brain which does rational thinking, and I ended up starting my day without any kind of warm up practice for the contest. I had not even revised any relevant material.
Bitwise 2k7 started a little late than the announced time of 1300hrs. And as usual, I thought to attempt the "easier" problems ( 100 points ) first. It was based on graph theory where one was required to find out the vertice(s) having the minimum distance to all other vertices in a given tree. Initially, I started with an O(n^3) implementation and when I found the response of the system to be "Time Limit Exceeded" ( which was kind of obvious with such a naive approach to the problem ), I improved it to O(n^2). Even though, I tried harder I could neither change the complexity nor the response of the system. After 2-3 failed attempts I decided to concentrate on some other problem and come back to this one at a later time.
Problem 4, had two parts, the initial part was to decide whether a certain door k out of n will be open or closed having gone through a certain toggling scheme. It was kind of easy. The next part was a variation of the classical Tower of Hanoi problem. No matter how hard I tried, my algorithm was not matching the given sample input/output. I asked the admins to look at the problem again for any possible mistake in the statement or sample input/output. But this time they were not as quick in response as they were for the last event. After around 10-15 questions fired by different teams, they answered only one. The overall contest also had attained height of mismanagement with problem statements being updated several times after the contest timer was started. Having tried for 2-3 hours on Problem 4, to my utter surprise, I found out that many other teams were cribbing about the correctness of its problem statement. I checked the rankings and was shocked to see that none of the teams ( not even those who were sitting at Top 10 ) could solve that problem. So I gave up on this problem too.
Then, I started yet another problem having to do with dynamic programming, coins and denominations. It was a variation of the classic denomination problem. Not that it was too hard to do it, I was kind of getting low because of failures and hunger. We went out to have a dinner at a small restaurant just opposite to IIT where we discussed yet another problem involving prime number and modular arithmetic. I thought to give it a shot after coming back, but that damn "Time Limit Exceeded" was not getting out of my sight.
Finally, we decided to give up as we were still sitting at zero where other Top 50 teams begged more than 800 points. I had never been so dejected in a long time. I was literally ashamed of myself.
Today morning I read a couple of articles on Modular Arithmetic and
Fermat's little theorem and realized why my implementation was not fast enough to defeat that "Time Limit Exceeded" demon. For Problem 1 ( The one with the vertices ) I learned that the middle vertice(s) of the longest path in the tree always have minimum sum of distance to all other vertices. How to find the longest path in a tree? Well, start from any vertex A and find out the furthest vertex B from it. Now start with B and find out the furthest vertex C from B. Path B to C is the longest path and its middle vertice(s) are the ones that we needed to find out. Running time?? O(n)
The bottom line is that I have got rusty. My programming skills and algorithm designing skills have fallen down. It seems I have not been doing much brain stimulating work for a long time. May be this failure is an indication for me to start honing my skills and in addition to giving exercise to my body I should give enough exercise to my brain as well.
The arrogance had fogged the part of the brain which does rational thinking, and I ended up starting my day without any kind of warm up practice for the contest. I had not even revised any relevant material.
Bitwise 2k7 started a little late than the announced time of 1300hrs. And as usual, I thought to attempt the "easier" problems ( 100 points ) first. It was based on graph theory where one was required to find out the vertice(s) having the minimum distance to all other vertices in a given tree. Initially, I started with an O(n^3) implementation and when I found the response of the system to be "Time Limit Exceeded" ( which was kind of obvious with such a naive approach to the problem ), I improved it to O(n^2). Even though, I tried harder I could neither change the complexity nor the response of the system. After 2-3 failed attempts I decided to concentrate on some other problem and come back to this one at a later time.
Problem 4, had two parts, the initial part was to decide whether a certain door k out of n will be open or closed having gone through a certain toggling scheme. It was kind of easy. The next part was a variation of the classical Tower of Hanoi problem. No matter how hard I tried, my algorithm was not matching the given sample input/output. I asked the admins to look at the problem again for any possible mistake in the statement or sample input/output. But this time they were not as quick in response as they were for the last event. After around 10-15 questions fired by different teams, they answered only one. The overall contest also had attained height of mismanagement with problem statements being updated several times after the contest timer was started. Having tried for 2-3 hours on Problem 4, to my utter surprise, I found out that many other teams were cribbing about the correctness of its problem statement. I checked the rankings and was shocked to see that none of the teams ( not even those who were sitting at Top 10 ) could solve that problem. So I gave up on this problem too.
Then, I started yet another problem having to do with dynamic programming, coins and denominations. It was a variation of the classic denomination problem. Not that it was too hard to do it, I was kind of getting low because of failures and hunger. We went out to have a dinner at a small restaurant just opposite to IIT where we discussed yet another problem involving prime number and modular arithmetic. I thought to give it a shot after coming back, but that damn "Time Limit Exceeded" was not getting out of my sight.
Finally, we decided to give up as we were still sitting at zero where other Top 50 teams begged more than 800 points. I had never been so dejected in a long time. I was literally ashamed of myself.
Today morning I read a couple of articles on Modular Arithmetic and
Fermat's little theorem and realized why my implementation was not fast enough to defeat that "Time Limit Exceeded" demon. For Problem 1 ( The one with the vertices ) I learned that the middle vertice(s) of the longest path in the tree always have minimum sum of distance to all other vertices. How to find the longest path in a tree? Well, start from any vertex A and find out the furthest vertex B from it. Now start with B and find out the furthest vertex C from B. Path B to C is the longest path and its middle vertice(s) are the ones that we needed to find out. Running time?? O(n)
The bottom line is that I have got rusty. My programming skills and algorithm designing skills have fallen down. It seems I have not been doing much brain stimulating work for a long time. May be this failure is an indication for me to start honing my skills and in addition to giving exercise to my body I should give enough exercise to my brain as well.
Thursday, February 01, 2007
Parzania : A distorted reflection of Gujarat Riots
So I am back to the blogs after a long break. Life is going on as routine and events happening not worth mentioning. But something happened that forced me to write today, something that evoked memories of gujarat riots. Yes, I am referring to movie "Parzania".
Last sunday evening me and pranjal went to see a movie at PVR Saket. Though the movie has been praised by critics, I did not like it much. It seems to be a fashion to make movies on "sensitive" issues and show that you ( producer / director and the whole league ) are "concerned" about those who suffered those horrific series of events.
The thing I did not like most about the movie is that they depicted the police force as an evil spectator and accomplice. I am not saying that police was acting like an angel during the events and may be some incidents might have happened which caused the notoriety the police has gained. Bollywood keeps on depicting our police force as a demon and then we all yell that police does not perform its duties very well. If someone who has done good deeds is always been criticized for his/her wrongdoing, will there be any motivation to keep on doing good? Isn't it the case that lack of appreciation cultivates a tendency not to take pain in doing something right ( because no body would care/mention/appreciate )?
I had been there in gujarat. I am born and brought up in gujarat itself. And I must say that the biggest villain was media. Stating baseless rumors as facts, presenting events in a sensitized form, showing provoking clips/statements this is all media has done. Should not they act responsibly? But who is to blame, after all, we like things presented in this manner. We always try to hide our irresponsible behavior by criticizing someone.
So called "Top class" reporter barkha dutt was standing on a lonely highway and screaming there is no security force there? What should I say about that asinine woman? Gujarat has thousands of kilometers of highway, what did she want? A policeman at every 50 meter on the highway and leave the burning cities unattended?
Army batallions were air lifted from Jodhpur to get them as fast to gujarat as possible. Those army men did not took a rest. But did we appreciate? My friends were stuck in vidyanagar because of curfew. No mess, no shops and no food. It was the police who came to the rescue, searching for such caged souls and escorting them to Anand railway station. They did not ask whether the students that they are helping is hindu or muslim, the just performed their duties. Alas! it all goes unnoticed. When the mob came to our place and burned shops at the ground floor, police did came. What do you think a group of four people, three carrying a lathi each and one carrying a vintage pistol could have done against a mob of 3000 people? I have seen police officers begging the mob to keep cool. And the way they depict in the movie is that police watched the entire scene taking satanic pleasure in whatever was happening.
Is it police' fault that we do not have enough policemen? Is it police' fault that it is not well equipped and poorly paid? At the time of riots, they were staying in tents in a sensitive areas so that people could feel safe, but no body cared asking them even for a glass of drinking water.
Well, may be I had a lot to write but my anger towards the movie was subdued because of the delay in this writing. And even from a movie point of view, having english as a language while you are filming on a lower class background???
Besides, I still don't understand what was the point of making this movie after years of those horrific past. Did they want to revive the wounds of victims? It is such kind of distorted and exaggerated representation which had damaged gujarat's reputation irrevocably. Gujarat was pushed to a sixth place in industrial investment, because they say gujarat is an "unsafe" place.
For me, gujarat is much much safer than any other place in india where girls can stroll at almost midnight without worries. May the peace prevail!!!
Last sunday evening me and pranjal went to see a movie at PVR Saket. Though the movie has been praised by critics, I did not like it much. It seems to be a fashion to make movies on "sensitive" issues and show that you ( producer / director and the whole league ) are "concerned" about those who suffered those horrific series of events.
The thing I did not like most about the movie is that they depicted the police force as an evil spectator and accomplice. I am not saying that police was acting like an angel during the events and may be some incidents might have happened which caused the notoriety the police has gained. Bollywood keeps on depicting our police force as a demon and then we all yell that police does not perform its duties very well. If someone who has done good deeds is always been criticized for his/her wrongdoing, will there be any motivation to keep on doing good? Isn't it the case that lack of appreciation cultivates a tendency not to take pain in doing something right ( because no body would care/mention/appreciate )?
I had been there in gujarat. I am born and brought up in gujarat itself. And I must say that the biggest villain was media. Stating baseless rumors as facts, presenting events in a sensitized form, showing provoking clips/statements this is all media has done. Should not they act responsibly? But who is to blame, after all, we like things presented in this manner. We always try to hide our irresponsible behavior by criticizing someone.
So called "Top class" reporter barkha dutt was standing on a lonely highway and screaming there is no security force there? What should I say about that asinine woman? Gujarat has thousands of kilometers of highway, what did she want? A policeman at every 50 meter on the highway and leave the burning cities unattended?
Army batallions were air lifted from Jodhpur to get them as fast to gujarat as possible. Those army men did not took a rest. But did we appreciate? My friends were stuck in vidyanagar because of curfew. No mess, no shops and no food. It was the police who came to the rescue, searching for such caged souls and escorting them to Anand railway station. They did not ask whether the students that they are helping is hindu or muslim, the just performed their duties. Alas! it all goes unnoticed. When the mob came to our place and burned shops at the ground floor, police did came. What do you think a group of four people, three carrying a lathi each and one carrying a vintage pistol could have done against a mob of 3000 people? I have seen police officers begging the mob to keep cool. And the way they depict in the movie is that police watched the entire scene taking satanic pleasure in whatever was happening.
Is it police' fault that we do not have enough policemen? Is it police' fault that it is not well equipped and poorly paid? At the time of riots, they were staying in tents in a sensitive areas so that people could feel safe, but no body cared asking them even for a glass of drinking water.
Well, may be I had a lot to write but my anger towards the movie was subdued because of the delay in this writing. And even from a movie point of view, having english as a language while you are filming on a lower class background???
Besides, I still don't understand what was the point of making this movie after years of those horrific past. Did they want to revive the wounds of victims? It is such kind of distorted and exaggerated representation which had damaged gujarat's reputation irrevocably. Gujarat was pushed to a sixth place in industrial investment, because they say gujarat is an "unsafe" place.
For me, gujarat is much much safer than any other place in india where girls can stroll at almost midnight without worries. May the peace prevail!!!
Friday, January 12, 2007
Esterel : Syntax and Indent files for Vim
The other day I was programming in Esterel with my favourite editor Vim. And it turned out that I did not have syntax and indent files which would make my life easier while using Esterel.
I could find syntax file for esterel from somewhere, and I modified, indent file for shell scripts to suit for esterel.
You must add following 3 lines to your .vimrc file :
au BufRead,BufNewFile *.strl set filetype=esterel
au! Syntax ESTEREL source /usr/share/vim/vim63/syntax/esterel.vim
:filetype indent on
Change the source where you had put the syntax file for esterel.
Ideally it should go to $VIMRUNTIME/syntax and $VIMRUNTIME/indent respectively.
Anyways, here are the links for the syntax and indent file for esterel.
I could find syntax file for esterel from somewhere, and I modified, indent file for shell scripts to suit for esterel.
You must add following 3 lines to your .vimrc file :
au BufRead,BufNewFile *.strl set filetype=esterel
au! Syntax ESTEREL source /usr/share/vim/vim63/syntax/esterel.vim
:filetype indent on
Change the source where you had put the syntax file for esterel.
Ideally it should go to $VIMRUNTIME/syntax and $VIMRUNTIME/indent respectively.
Anyways, here are the links for the syntax and indent file for esterel.
Wednesday, November 29, 2006
May I know the time please?
I got bored by reading papers so was going through iitb.h to get some refreshment :-) and here is what i found
-------------
Young Man: Sir, may I know the time, please?
Old Man: Certainly not.
Young Man: Sir, but why? What are you going to lose,if
you tell me the time?
Old Man: Yes, I may lose something if I tell you the
time.
Young Man: But Sir, can you tell me how?
Old Man : See, if I tell you the time you will
definitely thank me and may be tomorrow again you will
ask me the time.
Young Man: Quite possible.
Old Man: May be we meet two three times more and you will
ask my name and address.
Young Man: Quite possible.
Old Man: One day you may come to my house saying you were
just passing by and came into wish me.
Then as a courtsey, I will offer you a cup of tea.
After my courteous approach you will try to come
again.This time you will appreciate tea and ask who has
made it.?
Young Man: Possible
Old Man: Then I will tell you that my daughter has
and I will then have to introduce my young and pretty
daughter to you & you will admire my daughter.
Young Man: Smiles. ;)
Old Man: Now onwards you will try to meet my daughter
again and again. You will offer her to go out for a movie together and a
date with you.
Young Man: Smiles
Old Man: My daughter may start liking you and start
waiting for you. After meeting regularly you will fall in
love with her and propose her for marriage.
Young Man: Smiles
Old Man: One day both of you will come to me and tell me
about your love and ask for my permission.
Young Man: Oh Yes! And smiles
Old Man: (Angrily) Young man, I will never marry my
daughter to a person like you who does not even own a
watch.
-------------
Young Man: Sir, may I know the time, please?
Old Man: Certainly not.
Young Man: Sir, but why? What are you going to lose,if
you tell me the time?
Old Man: Yes, I may lose something if I tell you the
time.
Young Man: But Sir, can you tell me how?
Old Man : See, if I tell you the time you will
definitely thank me and may be tomorrow again you will
ask me the time.
Young Man: Quite possible.
Old Man: May be we meet two three times more and you will
ask my name and address.
Young Man: Quite possible.
Old Man: One day you may come to my house saying you were
just passing by and came into wish me.
Then as a courtsey, I will offer you a cup of tea.
After my courteous approach you will try to come
again.This time you will appreciate tea and ask who has
made it.?
Young Man: Possible
Old Man: Then I will tell you that my daughter has
and I will then have to introduce my young and pretty
daughter to you & you will admire my daughter.
Young Man: Smiles. ;)
Old Man: Now onwards you will try to meet my daughter
again and again. You will offer her to go out for a movie together and a
date with you.
Young Man: Smiles
Old Man: My daughter may start liking you and start
waiting for you. After meeting regularly you will fall in
love with her and propose her for marriage.
Young Man: Smiles
Old Man: One day both of you will come to me and tell me
about your love and ask for my permission.
Young Man: Oh Yes! And smiles
Old Man: (Angrily) Young man, I will never marry my
daughter to a person like you who does not even own a
watch.
Monday, November 27, 2006
Unique Role of Java in Programming Language Innovation
I was lucky to attend IBM IRL workshop on Next Generation Programming languages and Environments on 20-21st of Nov at India Internatinal Centre. Writing below some details of the first talk. Though, there were many talks in the workshop. I am able to recall only a few so wont be able to write about all the talks in my posts.
Unique Role of Java in Programming Language Innovation
------------------------------------------------------
Dr Bob Blainey of IBM Software group being a distinguished engineer and chief java technologist was no doubt the right person to talk about role of java in driving next generation programming languages and environments. He said that at least three mejor extension of java coming up to aid different programming need.
X10
--
X10 is a java extension which is designed to address the need for
concurent programming. One can not ignore the major shift towards
exploiting parallelism as much as possible. Next generation
programming languages can not ignore this shift and they have to
provide programmers construct which make use of underlying
parallelism.
There are a few constructs added in java, some of which I am listing
below.
Place :- This is a logical construct which can be mapped to physical
place in a sense that a place could be mapped to different processor
or a different machine altogether. The X10 framework assumes
distributed memory model and gives control to program in a GALS (
Globally Asynchronous Locally Synchronous ) environment.
Activity :- Activity resembles classical java threads. An activity can
access or modify only those objects which resides in the local place (
place in which the activity is residing ). So if an activity wants to
access a remote object, it has to first create an activity at the
remote place and then have to communicate with that newly created
activity to get the desired result. BadPlaceException is thrown in
case an activity tries to access a remote object.
Clock :- Those who are familiar with typical multi threading/multi
programming environments would say that this object acts as a barrier.
Different activities can register themselves with clocks and use it
for the purpose of synchronization. A place can have multiple clocks
and different activities can register for more than one clocks as
well. There is no global clock in the framework which makes it
globally asynchronous.
A container (e.g. array ) can be distributed across places. For
example programmer can decide to distribute array in such a way so
that an array of size 10 ( 0..9) its elements A[0] A[5] A[6] belong to place1
and
A[2] A[8] A[9] belong to place2. This distribution makes it difficult
to construct a simple for loop which will go through all the array
elements and update it because there is a possibility of a
BadPlaceException. To take care of this situation a projection
operator is introduced. For example,
for( point [i] : A | here )
where "here" refers to the place associated with the given scope just
like "this" refers to the object. This way one can iterate through all
the points ( elements ) of array A only residing within current place.
async( place ) { //some code } - This construct allows programmer to
execute a certain task at a remote place. It is not like a remote
procedure call in a sense that the calling module will not be blocked.
In fact, the code will run as an independent thread which may or may
not communicate back to the calling module after the invocation. In
other words, an asynchronous thread of execution is created at a
remote place to execute certain piece of code.
Many more constructs were described but unfortunately I am not able
to remember other details :-(.
XJ
--
XJ is an augmentation of Java is designed to address need for XML &
Web services. It extends Java syntax as well as semantics. One example
may look like :
Article A = new ( <>
<> getTitle() < /article_title >
getArticleBody()
I am not able to recall the exact syntax but it looked much like the
code I mentioned above.
Metronome
--------
Java with a real-time flavour. Major feature is handling garbage
collection with real-time constraints. I really wonder what kind of
algorithms would it take to perform garbage collection with such
constraints. What happens when the GC is halfway through marking the
live nodes and it has to relinquish control to another thread to
satisfy the constraints? Or what is GC is halfway through the
compaction ? I would really like to know the underlying details which
handles these intricacies.
I would like to end this post by a quote which Dr Bob Blainey
mentioned during his talk.
"Claiming that Java is easier than C++ is like saying that K2 is
shorter than everest" -- Larry O' Brian
Unique Role of Java in Programming Language Innovation
------------------------------------------------------
Dr Bob Blainey of IBM Software group being a distinguished engineer and chief java technologist was no doubt the right person to talk about role of java in driving next generation programming languages and environments. He said that at least three mejor extension of java coming up to aid different programming need.
X10
--
X10 is a java extension which is designed to address the need for
concurent programming. One can not ignore the major shift towards
exploiting parallelism as much as possible. Next generation
programming languages can not ignore this shift and they have to
provide programmers construct which make use of underlying
parallelism.
There are a few constructs added in java, some of which I am listing
below.
Place :- This is a logical construct which can be mapped to physical
place in a sense that a place could be mapped to different processor
or a different machine altogether. The X10 framework assumes
distributed memory model and gives control to program in a GALS (
Globally Asynchronous Locally Synchronous ) environment.
Activity :- Activity resembles classical java threads. An activity can
access or modify only those objects which resides in the local place (
place in which the activity is residing ). So if an activity wants to
access a remote object, it has to first create an activity at the
remote place and then have to communicate with that newly created
activity to get the desired result. BadPlaceException is thrown in
case an activity tries to access a remote object.
Clock :- Those who are familiar with typical multi threading/multi
programming environments would say that this object acts as a barrier.
Different activities can register themselves with clocks and use it
for the purpose of synchronization. A place can have multiple clocks
and different activities can register for more than one clocks as
well. There is no global clock in the framework which makes it
globally asynchronous.
A container (e.g. array ) can be distributed across places. For
example programmer can decide to distribute array in such a way so
that an array of size 10 ( 0..9) its elements A[0] A[5] A[6] belong to place1
and
A[2] A[8] A[9] belong to place2. This distribution makes it difficult
to construct a simple for loop which will go through all the array
elements and update it because there is a possibility of a
BadPlaceException. To take care of this situation a projection
operator is introduced. For example,
for( point [i] : A | here )
where "here" refers to the place associated with the given scope just
like "this" refers to the object. This way one can iterate through all
the points ( elements ) of array A only residing within current place.
async( place ) { //some code } - This construct allows programmer to
execute a certain task at a remote place. It is not like a remote
procedure call in a sense that the calling module will not be blocked.
In fact, the code will run as an independent thread which may or may
not communicate back to the calling module after the invocation. In
other words, an asynchronous thread of execution is created at a
remote place to execute certain piece of code.
Many more constructs were described but unfortunately I am not able
to remember other details :-(.
XJ
--
XJ is an augmentation of Java is designed to address need for XML &
Web services. It extends Java syntax as well as semantics. One example
may look like :
Article A = new ( <>
<> getTitle() < /article_title >
getArticleBody()
I am not able to recall the exact syntax but it looked much like the
code I mentioned above.
Metronome
--------
Java with a real-time flavour. Major feature is handling garbage
collection with real-time constraints. I really wonder what kind of
algorithms would it take to perform garbage collection with such
constraints. What happens when the GC is halfway through marking the
live nodes and it has to relinquish control to another thread to
satisfy the constraints? Or what is GC is halfway through the
compaction ? I would really like to know the underlying details which
handles these intricacies.
I would like to end this post by a quote which Dr Bob Blainey
mentioned during his talk.
"Claiming that Java is easier than C++ is like saying that K2 is
shorter than everest" -- Larry O' Brian
Friday, November 17, 2006
Few Jokes
Hi,
Posting a few jokes from iitb.h
-------------------------------------
Tourist: Whose skeleton is that?
Santa: Tipu's skeleton.
Tourist: Whose that smaller skeleton next to it?
Santa: That was Tipu's skeleton when he was child
-----------------------------------------
� Gabbar: Kitne admi they?
Sambha: Sardar 2
Gabbar: Mujhe ginti nahin aati, 2 kitne hote hain?
Samba: Sardar 2, 1 ke baad aata hai
Gabbar: Aur 2 ke pehle?
Samba: 2 k pehle 1 aata hai.
Gabbar: To beech mein kaun ata hai?
Samba: Beech mein koi nahi aata>
Gabbar:: To phir dono ek saath kyun nahin aate?
Samba: 1 k baad hi 2 aa sakta hai, kyun ki 2, 1 se bada hai.
Gabar: 2, 1 se kitna bada hai?
Samba: 2, 1 se 1 bada hai.
Gabbar: Agar 2, 1 se 1 bada hai to 1, 1 se kitna bada hai?
Samnba: Sardar maine aapka namak khaya hai, mujhe goli maar do
------------------------------------------------
What is the height of Flirting?
It's When your love letter starts with: TO WHOMSOEVER IT MAY CONCERN
------------------------------------------------
Ganguly�s Son: Yeh Kya, Daddy Sixer pe Sixer maare jaa rahe hain Hain?
Ganguly�s Wife: Arey beta, yeh toh ADVERTISEMENT Hai !
� U luv sumone... u marry sumone else. The one u marry becomes ur wife
or husband & the one u loved becomes the password of your emai id...!
-----
� Ab tak meri life ek khuli botal thi, jis mein se sab perfume ki tarah
ud jata tha. Par aap ke aane se sab kuch ruk gaya. Bhagwan kare aap
jaisa DHAKKAN sabko miley
� Baniye ki wife bimaar thi, light na hone ki wajah se usne candle jala
di aur bola: Doc ko lene jaa raha hun, agar tumhe lage ki tum nahin
bachogi to plz candle bujha dena
----------------------------------------
Teacher to class: A for?
Class: Apple
Teacher: Jor Se Bolo
Class: Jai Mata Di
----------------------------
Posting a few jokes from iitb.h
-------------------------------------
Tourist: Whose skeleton is that?
Santa: Tipu's skeleton.
Tourist: Whose that smaller skeleton next to it?
Santa: That was Tipu's skeleton when he was child
-----------------------------------------
� Gabbar: Kitne admi they?
Sambha: Sardar 2
Gabbar: Mujhe ginti nahin aati, 2 kitne hote hain?
Samba: Sardar 2, 1 ke baad aata hai
Gabbar: Aur 2 ke pehle?
Samba: 2 k pehle 1 aata hai.
Gabbar: To beech mein kaun ata hai?
Samba: Beech mein koi nahi aata>
Gabbar:: To phir dono ek saath kyun nahin aate?
Samba: 1 k baad hi 2 aa sakta hai, kyun ki 2, 1 se bada hai.
Gabar: 2, 1 se kitna bada hai?
Samba: 2, 1 se 1 bada hai.
Gabbar: Agar 2, 1 se 1 bada hai to 1, 1 se kitna bada hai?
Samnba: Sardar maine aapka namak khaya hai, mujhe goli maar do
------------------------------------------------
What is the height of Flirting?
It's When your love letter starts with: TO WHOMSOEVER IT MAY CONCERN
------------------------------------------------
Ganguly�s Son: Yeh Kya, Daddy Sixer pe Sixer maare jaa rahe hain Hain?
Ganguly�s Wife: Arey beta, yeh toh ADVERTISEMENT Hai !
� U luv sumone... u marry sumone else. The one u marry becomes ur wife
or husband & the one u loved becomes the password of your emai id...!
-----
� Ab tak meri life ek khuli botal thi, jis mein se sab perfume ki tarah
ud jata tha. Par aap ke aane se sab kuch ruk gaya. Bhagwan kare aap
jaisa DHAKKAN sabko miley
� Baniye ki wife bimaar thi, light na hone ki wajah se usne candle jala
di aur bola: Doc ko lene jaa raha hun, agar tumhe lage ki tum nahin
bachogi to plz candle bujha dena
----------------------------------------
Teacher to class: A for?
Class: Apple
Teacher: Jor Se Bolo
Class: Jai Mata Di
----------------------------
Tuesday, November 14, 2006
Godel's incompleteness theorem
Yesterday I was opportune to watch Dr Raja elucidate the proof of Godel 's
incompleteness theorem .
I still do not know much details of the theorem so I writing it down here in an informal manner.
Basically, what is states is " A statements can be constructed in an axiomatic system which is true but can not be proved or disproved using the axioms of the given axiomatic system ". Or the other statement goes like "No consistent axiomatic system can be complete".
The example that Dr Raja explained goes something like this.
Let there be an alphabet sigma = { (, ), P , N , ~ }
Let there be expression X \in sigma^*
Let us define N(X) to be X(X) called the norm of X
There are four kind of sentences in this language
P(X) - P(X) is true iff X is printable
~P(X) - ~P(X) is true iff X is not printable
PN(X) - PN(X) is true iff N(X) is printable
~PN(X) - ~PN(X) is true iff N(X) is not printable
Let us also have a machine which prints only true sentences. ( in other words only true sentences are printable by the machine )
So now, if X is printable, so is P(X)
Given that a machine prints X then P(X) is true but will the machine print it??
or in other words, is the machine able to print all the true sentences???
The answer to this question is NO
Can you form a sentence which is true in the system discribed above but still won't be printed by the machine?
Hint : Because this is a self referential system, one can think of a sentence which tries to make statement about its own printability.
If you can not think of such a sentence...dont worry as I also was not able think of that then.
The answer is ~PN ( ~PN ) the sentence is true and yet it is not printable. the negation of the sentece is PN ( ~PN ) is false hence won't be printed by the machine.
For axiomatic system one can try to substitute the concept of printability to provability and can derive similar example as well as conclusion.
I have written down whatever I have understood from the talk and whatever I could remember. The information may not be precise or some incosistency may have been introduced because of the long path of information transfer :D
I wish I get such opportunities frequently :-) I am looking forward to IRL workshop for that.
incompleteness theorem .
I still do not know much details of the theorem so I writing it down here in an informal manner.
Basically, what is states is " A statements can be constructed in an axiomatic system which is true but can not be proved or disproved using the axioms of the given axiomatic system ". Or the other statement goes like "No consistent axiomatic system can be complete".
The example that Dr Raja explained goes something like this.
Let there be an alphabet sigma = { (, ), P , N , ~ }
Let there be expression X \in sigma^*
Let us define N(X) to be X(X) called the norm of X
There are four kind of sentences in this language
P(X) - P(X) is true iff X is printable
~P(X) - ~P(X) is true iff X is not printable
PN(X) - PN(X) is true iff N(X) is printable
~PN(X) - ~PN(X) is true iff N(X) is not printable
Let us also have a machine which prints only true sentences. ( in other words only true sentences are printable by the machine )
So now, if X is printable, so is P(X)
Given that a machine prints X then P(X) is true but will the machine print it??
or in other words, is the machine able to print all the true sentences???
The answer to this question is NO
Can you form a sentence which is true in the system discribed above but still won't be printed by the machine?
Hint : Because this is a self referential system, one can think of a sentence which tries to make statement about its own printability.
If you can not think of such a sentence...dont worry as I also was not able think of that then.
The answer is ~PN ( ~PN ) the sentence is true and yet it is not printable. the negation of the sentece is PN ( ~PN ) is false hence won't be printed by the machine.
For axiomatic system one can try to substitute the concept of printability to provability and can derive similar example as well as conclusion.
I have written down whatever I have understood from the talk and whatever I could remember. The information may not be precise or some incosistency may have been introduced because of the long path of information transfer :D
I wish I get such opportunities frequently :-) I am looking forward to IRL workshop for that.
Thursday, September 21, 2006
Cake cutting is NOT a piece of cake
Hi,
My Boss is out of india for a week so I am a bit relaxed now. Yesterday, I was just surfing the net and I recalled something about "Cake cutting". I did a bit of googling and found
this paper. The paper defines the problem formally and then give information about existing cake-cutting algorithms. Initially, I thought the paper might actually contain the algorithms but to my misfortune it does not. However, it shows how sorting can be reduced to the cake-cutting problem ( under certain conditions ). The most interesting piece of information I got from this paper is that it is not even easy ( in terms of complexity ) to cut a cake in a way so as to guarantee a positive share ( not even fair...just positive ) to every contender.
Well, for those of you who are baffled by the above text, let me refer to a lecture note. I am copying the text below in the fear of losing this nice piece of text in case it is removed from the original source.
There is also a very nice book named "Cake cutting algorithms : Be fair if you can" by Jack Robertson and William webb. I am saying this book is nice because I got very good reviews about it. The review says that it is lucid enough for a novice to try out. I wish to read it someday.
Anyways, it did not seem to cut a cake that difficult while celebrating b'days in the department :D ( I guess because we did not bother about the fair share ...:D)
--------------------------------------------
Lecture Notes on Cake Cutting & Fair Division, Thursday 9/18/2003, CS70
The cake-cutting problem:
We have a cake, and n people who want to split it amongst themselves.
However, each person might value different portions of the cake
differently. (I like flowers; you hate them. I hate icing; you
prefer it.) What's worse, we don't trust each other! What can we
do?
A protocol is *fair* for X if the following property is true:
If X follows the party, then X gets at least 1/n-th of the cake
(by X's measure), no matter how the other parties behave.
The protocol is *fair* if it is fair for all parties.
For n=2: cut-and-choose protocol
1. Alice cuts the cake into two equal pieces (equal by her measure)
2. Bob chooses whichever piece looks larger (by his measure)
3. Alice takes the remaining one
Theorem: Cut-and-choose is fair.
Proof: If Alice follows the protocol, she gets exactly 1/2 (by her
measure), no matter how Bob behaves.
Next Let's consider Bob. When it is time for him to choose,
he sees two pieces, one worth W and the other worth 1-W (by his measure).
It is guaranteed that either W >= 1/2 or 1-W >= 1/2 (if W < 1 =" W+1-W" 2 =" 1,">2?
For general n:
If n=2, use cut-and-choose. Otherwise:
Let first n-1 people divide the cake using a recursive
call to this procedure.
Then the nth person steps in and
asks each of the first n-1 people to divide her share into
n equal pieces (by her measure).
Finally, the nth person goes around and collects the
largest (in his view) of the n pieces from each of the other people.
Does each think they've got at least 1/n of the whole pile
(by their measure)?
For first n-1 people, yes, since they get
>= 1/(n-1) after recursive call, divide this into pieces each of
size >= 1/n(n-1), and then get n-1 of these pieces.
For last person, yes, since he gets at least x_i/n from the ith
person, if ith person's whole share is worth x_i. Also,
x_1 + ... + x_{n-1} = 1, so last person's total share is
x_1/n + ... + x_{n-1}/n >= 1/n. Therefore:
Theorem: This protocol is fair.
Proof: By induction on n. We've proved the base case (n=2).
The inductive step is exactly what appears in the previous paragraph. QED.
This general protocol can be implemented as a recursive program.
Q: What's the running time?
A: n! > 2^n ... which is exponential. yuck.
Q: Can it be done in time polynomial in n?
Puzzle: Find a fair cake-cutting protocol with running time polynomial in n.
One answer: A moving knife.
Move a knife slowly from left to right. When area to the left of the knife
covers at least 1/n-th of the cake by your measure, yell "Stop!". First person
to yell "Stop!" gets everything to the left of the knife, and we continue.
However, we might prefer to avoid using moving knifes.
Q: Why not use a moving knife?
A: hard to implement in a distributed system without time synchronization
Puzzle: Find a fair cake-cutting protocol with running time polynomial in n,
with no use of moving knives.
One solution:
Take the n-party moving knife algorithm, and translate it into
a non-moving-knife protocol by having each person cut at first
point they'd yell "Stop!". Take the smallest piece and give it to
the person who cut there. Then, continue dividing up the rest of the
cake up among the remaining n-1 parties.
Running time: O(n^2) basic operations
A protocol is *envy-free* for X if it has the following property:
if X follows the protocol, then X gets at least as much (by X's measure)
as anyone else gets (by X's measure), no matter how the other parties behave.
A protocol is *envy-free* if it is envy-free for all participants.
Q: Is 2-party cut-and-choose envy-free?
A: Yes (do you see why?)
Q: Is the recursive algorithm I gave last time envy-free for n=3?
(i.e., A+B cut-and-choose, then divide their pieces into 3 sub-pieces;
C gets to choose one sub-piece from A & one from B)
A: No.
(A+B might conspire to give whole cake to A; then C gets 1/3,
but A gets 2/3, not envy-free)
Q: Is the 3-party moving knife algorithm envy-free?
(i.e., move knife slowly to right until someone yells Stop!, repeat)
A: No.
(suppose A yells Stop! first. then B+C might conspire to give
all of remainder to B and none to C, not envy-free)
By the way, this is a non-zero-sum game.
Non-zero sum games often allow everyone to come away with better
than 1/n-th of the cake.
An example of "arbitrage" and a non-zero-sum game:
Alice believes that Gore will win the election with probability
5/8. Bob believes that Bush will win the election with probability
3/4.
Assuming that Alice and Bob are both willing to accept any bet
that gives them a positive expectation of winning, did you know
that there's a way to place bets with both of them so that you can
make money for certain?
Here's what you can do. Bet with Alice that you'll pay her $2 if
Gore wins and she'll pay you $3 otherwise. Alice agrees because
her expectation is: $2(5/8)-$3(3/8)=$1/8.
Bet with Bob that you'll pay him $2 if Bush wins, and he'll pay
you $3 otherwise. Bob agrees because his expectation is
$2(3/4)-$3(1/4)=$3/4.
Alice and Bob both believe they have positive expectation, but
you will win for certain: if either Bush or Gore wins, you will net
a dollar!
Credits: http://www.math.hmc.edu/funfacts/ffiles/30003.6.shtml
An envy-free cake-cutting protocol for n=3 people:
http://www.math.hmc.edu/funfacts/ffiles/30001.4-8.shtml
Problem: polynomial-time envy-free cake-cutting protocol for all n
(This might be open?)
-----------------------------------------
My Boss is out of india for a week so I am a bit relaxed now. Yesterday, I was just surfing the net and I recalled something about "Cake cutting". I did a bit of googling and found
this paper. The paper defines the problem formally and then give information about existing cake-cutting algorithms. Initially, I thought the paper might actually contain the algorithms but to my misfortune it does not. However, it shows how sorting can be reduced to the cake-cutting problem ( under certain conditions ). The most interesting piece of information I got from this paper is that it is not even easy ( in terms of complexity ) to cut a cake in a way so as to guarantee a positive share ( not even fair...just positive ) to every contender.
Well, for those of you who are baffled by the above text, let me refer to a lecture note. I am copying the text below in the fear of losing this nice piece of text in case it is removed from the original source.
There is also a very nice book named "Cake cutting algorithms : Be fair if you can" by Jack Robertson and William webb. I am saying this book is nice because I got very good reviews about it. The review says that it is lucid enough for a novice to try out. I wish to read it someday.
Anyways, it did not seem to cut a cake that difficult while celebrating b'days in the department :D ( I guess because we did not bother about the fair share ...:D)
--------------------------------------------
Lecture Notes on Cake Cutting & Fair Division, Thursday 9/18/2003, CS70
The cake-cutting problem:
We have a cake, and n people who want to split it amongst themselves.
However, each person might value different portions of the cake
differently. (I like flowers; you hate them. I hate icing; you
prefer it.) What's worse, we don't trust each other! What can we
do?
A protocol is *fair* for X if the following property is true:
If X follows the party, then X gets at least 1/n-th of the cake
(by X's measure), no matter how the other parties behave.
The protocol is *fair* if it is fair for all parties.
For n=2: cut-and-choose protocol
1. Alice cuts the cake into two equal pieces (equal by her measure)
2. Bob chooses whichever piece looks larger (by his measure)
3. Alice takes the remaining one
Theorem: Cut-and-choose is fair.
Proof: If Alice follows the protocol, she gets exactly 1/2 (by her
measure), no matter how Bob behaves.
Next Let's consider Bob. When it is time for him to choose,
he sees two pieces, one worth W and the other worth 1-W (by his measure).
It is guaranteed that either W >= 1/2 or 1-W >= 1/2 (if W < 1 =" W+1-W" 2 =" 1,">2?
For general n:
If n=2, use cut-and-choose. Otherwise:
Let first n-1 people divide the cake using a recursive
call to this procedure.
Then the nth person steps in and
asks each of the first n-1 people to divide her share into
n equal pieces (by her measure).
Finally, the nth person goes around and collects the
largest (in his view) of the n pieces from each of the other people.
Does each think they've got at least 1/n of the whole pile
(by their measure)?
For first n-1 people, yes, since they get
>= 1/(n-1) after recursive call, divide this into pieces each of
size >= 1/n(n-1), and then get n-1 of these pieces.
For last person, yes, since he gets at least x_i/n from the ith
person, if ith person's whole share is worth x_i. Also,
x_1 + ... + x_{n-1} = 1, so last person's total share is
x_1/n + ... + x_{n-1}/n >= 1/n. Therefore:
Theorem: This protocol is fair.
Proof: By induction on n. We've proved the base case (n=2).
The inductive step is exactly what appears in the previous paragraph. QED.
This general protocol can be implemented as a recursive program.
Q: What's the running time?
A: n! > 2^n ... which is exponential. yuck.
Q: Can it be done in time polynomial in n?
Puzzle: Find a fair cake-cutting protocol with running time polynomial in n.
One answer: A moving knife.
Move a knife slowly from left to right. When area to the left of the knife
covers at least 1/n-th of the cake by your measure, yell "Stop!". First person
to yell "Stop!" gets everything to the left of the knife, and we continue.
However, we might prefer to avoid using moving knifes.
Q: Why not use a moving knife?
A: hard to implement in a distributed system without time synchronization
Puzzle: Find a fair cake-cutting protocol with running time polynomial in n,
with no use of moving knives.
One solution:
Take the n-party moving knife algorithm, and translate it into
a non-moving-knife protocol by having each person cut at first
point they'd yell "Stop!". Take the smallest piece and give it to
the person who cut there. Then, continue dividing up the rest of the
cake up among the remaining n-1 parties.
Running time: O(n^2) basic operations
A protocol is *envy-free* for X if it has the following property:
if X follows the protocol, then X gets at least as much (by X's measure)
as anyone else gets (by X's measure), no matter how the other parties behave.
A protocol is *envy-free* if it is envy-free for all participants.
Q: Is 2-party cut-and-choose envy-free?
A: Yes (do you see why?)
Q: Is the recursive algorithm I gave last time envy-free for n=3?
(i.e., A+B cut-and-choose, then divide their pieces into 3 sub-pieces;
C gets to choose one sub-piece from A & one from B)
A: No.
(A+B might conspire to give whole cake to A; then C gets 1/3,
but A gets 2/3, not envy-free)
Q: Is the 3-party moving knife algorithm envy-free?
(i.e., move knife slowly to right until someone yells Stop!, repeat)
A: No.
(suppose A yells Stop! first. then B+C might conspire to give
all of remainder to B and none to C, not envy-free)
By the way, this is a non-zero-sum game.
Non-zero sum games often allow everyone to come away with better
than 1/n-th of the cake.
An example of "arbitrage" and a non-zero-sum game:
Alice believes that Gore will win the election with probability
5/8. Bob believes that Bush will win the election with probability
3/4.
Assuming that Alice and Bob are both willing to accept any bet
that gives them a positive expectation of winning, did you know
that there's a way to place bets with both of them so that you can
make money for certain?
Here's what you can do. Bet with Alice that you'll pay her $2 if
Gore wins and she'll pay you $3 otherwise. Alice agrees because
her expectation is: $2(5/8)-$3(3/8)=$1/8.
Bet with Bob that you'll pay him $2 if Bush wins, and he'll pay
you $3 otherwise. Bob agrees because his expectation is
$2(3/4)-$3(1/4)=$3/4.
Alice and Bob both believe they have positive expectation, but
you will win for certain: if either Bush or Gore wins, you will net
a dollar!
Credits: http://www.math.hmc.edu/funfacts/ffiles/30003.6.shtml
An envy-free cake-cutting protocol for n=3 people:
http://www.math.hmc.edu/funfacts/ffiles/30001.4-8.shtml
Problem: polynomial-time envy-free cake-cutting protocol for all n
(This might be open?)
-----------------------------------------
Tuesday, September 19, 2006
I am back..!!
Hi,
Well, No wonder I have not been posting anything on blogger since long. July was undoubtedly the most exhausting week because of the final project presentation. After that, I enjoyed a real nice vacation...and for me, vacation means vacation, no emails, no connectivity...in short.. no worry :D.
So currently I am sitting in IBM India Research Lab at IIT Delhi. I have joined here on 2nd august but since then nothing interesting happend which would push me to write over here. In fact, right now I am writing no because I have something to write. But because I am sitting idle for a while.
The main character of my last few posts, the hero of the story or comedian of the story is missing. Yeah, the number of post on my blog is reduced because the entire gang is now scattered...me in delhi, malik in h'bad, saket in dubai, guptav in pune, keyur in b'lore and sushil in mumbai. No wonder this post is boring :D but I hope to write something interesting now onwards may be with a flambuoyant language because of GRE preparation. But this posting was like a "keep alive" packet.
Well, No wonder I have not been posting anything on blogger since long. July was undoubtedly the most exhausting week because of the final project presentation. After that, I enjoyed a real nice vacation...and for me, vacation means vacation, no emails, no connectivity...in short.. no worry :D.
So currently I am sitting in IBM India Research Lab at IIT Delhi. I have joined here on 2nd august but since then nothing interesting happend which would push me to write over here. In fact, right now I am writing no because I have something to write. But because I am sitting idle for a while.
The main character of my last few posts, the hero of the story or comedian of the story is missing. Yeah, the number of post on my blog is reduced because the entire gang is now scattered...me in delhi, malik in h'bad, saket in dubai, guptav in pune, keyur in b'lore and sushil in mumbai. No wonder this post is boring :D but I hope to write something interesting now onwards may be with a flambuoyant language because of GRE preparation. But this posting was like a "keep alive" packet.
Subscribe to:
Posts (Atom)