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.
Wednesday, November 29, 2006
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() < /article > );
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.
Posted by
Saurabh Joshi
at
4:27 PM
Labels:
mathematics,
theorems
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?)
-----------------------------------------
Posted by
Saurabh Joshi
at
1:37 PM
Labels:
algorithms,
mathematics
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.
Monday, June 26, 2006
Original Joke : life kya hoti hai?
Hi,
so here I am back again after several days of rest. I was not exactly resting much as I am busy with my MTech report submission right now. Anyways, here goes yet another incident of gupta's humour.
------------------------------
Me, Gupta and Sushil went to Laxmi to have our dinner. Sarat joined after a few minutes. We all were having our dinner, talking, sharing jokes.. Suddenly, Gupta asked sarat "Tune kabhi dange ( riots ) ka samna kiya hai?", "No", answered sarat in a baffled manner. "Tune kabhi baadh ( flood ) ka samna kiya hai?", gupta went on without giving any clue what was this all about. "No". "Tune kabhi akaal ( draught ) ka samna kiya hai? ". "No". We all were trying to know gupta's intentions. "Tune kabhi bhukamp ( earthquake ) ka samna kiya hai?". Sarat replied in negation again. Gupta" To tuje kya pata life kya hoti hai???!!!!", everybody bursted out laughing.
During all this time I observed that all the calamities gupta mentioned about happened in gujarat during not so distant past. So I was feeling a little proud of myself to have faced some of the danger situation gupta had mentioned. I could not resist my feeling and went on to cut my leg with my own axe, "Maine ye sab ka samna kiya hai" I told gupta with a glimpse of pride and enthusiasm.
Gupta "Phir bhi tuje nahi pata life kya hoti hai???!!".
--------------------------------
so here I am back again after several days of rest. I was not exactly resting much as I am busy with my MTech report submission right now. Anyways, here goes yet another incident of gupta's humour.
------------------------------
Me, Gupta and Sushil went to Laxmi to have our dinner. Sarat joined after a few minutes. We all were having our dinner, talking, sharing jokes.. Suddenly, Gupta asked sarat "Tune kabhi dange ( riots ) ka samna kiya hai?", "No", answered sarat in a baffled manner. "Tune kabhi baadh ( flood ) ka samna kiya hai?", gupta went on without giving any clue what was this all about. "No". "Tune kabhi akaal ( draught ) ka samna kiya hai? ". "No". We all were trying to know gupta's intentions. "Tune kabhi bhukamp ( earthquake ) ka samna kiya hai?". Sarat replied in negation again. Gupta" To tuje kya pata life kya hoti hai???!!!!", everybody bursted out laughing.
During all this time I observed that all the calamities gupta mentioned about happened in gujarat during not so distant past. So I was feeling a little proud of myself to have faced some of the danger situation gupta had mentioned. I could not resist my feeling and went on to cut my leg with my own axe, "Maine ye sab ka samna kiya hai" I told gupta with a glimpse of pride and enthusiasm.
Gupta "Phir bhi tuje nahi pata life kya hoti hai???!!".
--------------------------------
Friday, June 16, 2006
Shayari from shAan
Hi,
It's been a long time since I wrote down something here. So many things happened but I am just too lazy to post it over here. Just copying some shayaris that my friend shAan wrote. I hope u dont mid, shAan :-)
~~Daaman~~
youn na mujhko dekh tera dil pighal na jaaye
mere aansooyon se tera daaman jal na jaaye
woh mujhse phir mila hai aaj khwaabon mein
ae khudaya kahin meri neend khul na jaaye
poocha na kar sab ke saamne meri kahani
kabhi tera naam hothon se nikal na jaaye
jee bhar ke dekh lo "shAan" ko tum sanam
kya pata phir zindagi ki shaam dhal na jaaye
~~Chiraag mein~~
jab koi junoon aata hai dimaag mein
apna khoon daal deta hoon chiraag mein
aik chehra ban jaata hai meri aahon se
aik soorat chhupi huii hai dil ke daag mein
dard ke siwaa mujhko milaa kuch bhi nahin
maine dil lagaaya tha khushiyon ki laag mein
lapton mein mujhko dekh kar mayous hote hain
jhoonk to dete hain mere khat woh aag mein
kaanton se apna daaman bhar ke laaya hoon
mil gaya tha aik shakhs phoolon ke baag mein
~~banaa diya~~
khoon se rangeen deewar-o-dar banaa diya
zara sa haath maine zakhmon se utthaa diya
teri yaadon ne dastak jab bhi dil pe di
aik aah bhar lee aik aansoo bahaa diya
cheekh-te hain dil ke chhalle naam-e-marham pe
rog kaise tumne ye dil ko lagaa diya
phir bhi deta hai tum hi ko dil duaayen
mana ke tune mujhe khaak mein milaa diya
baitha hoon jaise lutt gaya ho dilli ka taaj
aaj maine tera aakhiri khat bhi jalaa diya
woh chehre ko duppatte mein chhuppaye chal diye
"shAan" ka ek sheyr maine kya sunaa diya
It's been a long time since I wrote down something here. So many things happened but I am just too lazy to post it over here. Just copying some shayaris that my friend shAan wrote. I hope u dont mid, shAan :-)
~~Daaman~~
youn na mujhko dekh tera dil pighal na jaaye
mere aansooyon se tera daaman jal na jaaye
woh mujhse phir mila hai aaj khwaabon mein
ae khudaya kahin meri neend khul na jaaye
poocha na kar sab ke saamne meri kahani
kabhi tera naam hothon se nikal na jaaye
jee bhar ke dekh lo "shAan" ko tum sanam
kya pata phir zindagi ki shaam dhal na jaaye
~~Chiraag mein~~
jab koi junoon aata hai dimaag mein
apna khoon daal deta hoon chiraag mein
aik chehra ban jaata hai meri aahon se
aik soorat chhupi huii hai dil ke daag mein
dard ke siwaa mujhko milaa kuch bhi nahin
maine dil lagaaya tha khushiyon ki laag mein
lapton mein mujhko dekh kar mayous hote hain
jhoonk to dete hain mere khat woh aag mein
kaanton se apna daaman bhar ke laaya hoon
mil gaya tha aik shakhs phoolon ke baag mein
~~banaa diya~~
khoon se rangeen deewar-o-dar banaa diya
zara sa haath maine zakhmon se utthaa diya
teri yaadon ne dastak jab bhi dil pe di
aik aah bhar lee aik aansoo bahaa diya
cheekh-te hain dil ke chhalle naam-e-marham pe
rog kaise tumne ye dil ko lagaa diya
phir bhi deta hai tum hi ko dil duaayen
mana ke tune mujhe khaak mein milaa diya
baitha hoon jaise lutt gaya ho dilli ka taaj
aaj maine tera aakhiri khat bhi jalaa diya
woh chehre ko duppatte mein chhuppaye chal diye
"shAan" ka ek sheyr maine kya sunaa diya
Thursday, May 18, 2006
Original Joke : Cartoon super hero
Hi,
I am back from my vacation at home. I know it's been a while since I posted anything over here but sometimes it is better to remain disconnected for a while:-)
Writing below the proof of saket's quick witted humour
-------------------------------------------
Before I start writing anything let me tell you that gupta is a very huge fan of batman. By word "huge" I dont mean to refer to his body :D. It just refer to the amount of madness he posses for batman.
Saket ane Gupta were sitting in kaksha lab. Gupta ,in his usual enthusiastic style, was describing batman and his qualities. After describing batman as an ideal super hero, gupta asked saket in anticipation " Saket, what is your favourite cartoon super hero?". "You!!!" said Saket wihtout even taking time to think :D.
---------------------------------------------
I am back from my vacation at home. I know it's been a while since I posted anything over here but sometimes it is better to remain disconnected for a while:-)
Writing below the proof of saket's quick witted humour
-------------------------------------------
Before I start writing anything let me tell you that gupta is a very huge fan of batman. By word "huge" I dont mean to refer to his body :D. It just refer to the amount of madness he posses for batman.
Saket ane Gupta were sitting in kaksha lab. Gupta ,in his usual enthusiastic style, was describing batman and his qualities. After describing batman as an ideal super hero, gupta asked saket in anticipation " Saket, what is your favourite cartoon super hero?". "You!!!" said Saket wihtout even taking time to think :D.
---------------------------------------------
Friday, April 21, 2006
Shayari
it's shayri time again. obviously, not my creation.
-----------------------------------------------------
Hum mud mud ke unhe dekh rahe the aur woh hame...
Hum mud mud ke unhe dekh rahe the aur woh hame...
Kyunki exam me na unhe kucch aa raha tha, na hame ...
-----------------------------------------------------
I wish aisi exam har din hoti rahe,
isi bahane kisi ki nigahein hum pe padti rahe
----------------------------------------------------
"Churi chalane ki hum par, zarurat hai unhe kya,
Ek dafa wo nazre milake to dekhe, hum abhi yahin ghayal ho jaenge..."
-------------------------------------------------------
Tu dekh ya na dekh, tere dekhne ka gam nahi,
Par teri ye na dekhne ki ada dekhne se kam nahi.
---------------------------------------------------------
amein dekhane waalo ki is duniya mein kami nahi,
Par teri nazhro wali baat kisi aur mein nahi !!!
---------------------------------------------------------
tufan me kashti ko kinare bhi mil jate hai
jahan me logo ko sahare bhi mil jate hai
duniya me sabse pyari hai zindagi
kuch log zindagi se pyare bhi mil jate hai
-----------------------------------------------------------
Khidki khuli, Zhulfe nikli,
Khidki khuli, Zhulfe nikli,
Maine soch kismat khuli,
Par afsos, din itwaar tha,
Khuli zhulfo wala Sardar tha
-------------------------------------------------------------
vaado ko ikraar na samjho,
Khamoshi ko inkaar na samjho,
Nazre milti hai hazaroo se,
Nazro ke milne ko pyar na samjho..
------------------------------------------------------------
Koi ankhon se baat kar leta hai,
Koi ankhon mein mulakat kar leta hai,
Bada mushkil hota hai jawab dena,
Jab koi khamosh rehkar sawaal kar leta hai.
-------------------------------------------------------------
PHIR AAJ WAHI MAIKADE KI YAAD AA RAHI HAI
PHIR AAJ WAHI SHARAB KI KUSHBU AA RAHI HAI
PHIR AAJ WAHI SAQI KI PUKAR AA RAHI HAI
PHIR AAJ WAHI BHEED KI TANHAEE MUJE SATA RAHI HAI......
--------------------------------------------------------------
Sharab bani to maikhane bane ...
Sharab bani to maikhane bane ...
pyar bana to deewane bane
Kuch to baat hogi aap mein
ki yuhi nahin paagal khane bane.
----------------------------------------------------------------
-----------------------------------------------------
Hum mud mud ke unhe dekh rahe the aur woh hame...
Hum mud mud ke unhe dekh rahe the aur woh hame...
Kyunki exam me na unhe kucch aa raha tha, na hame ...
-----------------------------------------------------
I wish aisi exam har din hoti rahe,
isi bahane kisi ki nigahein hum pe padti rahe
----------------------------------------------------
"Churi chalane ki hum par, zarurat hai unhe kya,
Ek dafa wo nazre milake to dekhe, hum abhi yahin ghayal ho jaenge..."
-------------------------------------------------------
Tu dekh ya na dekh, tere dekhne ka gam nahi,
Par teri ye na dekhne ki ada dekhne se kam nahi.
---------------------------------------------------------
amein dekhane waalo ki is duniya mein kami nahi,
Par teri nazhro wali baat kisi aur mein nahi !!!
---------------------------------------------------------
tufan me kashti ko kinare bhi mil jate hai
jahan me logo ko sahare bhi mil jate hai
duniya me sabse pyari hai zindagi
kuch log zindagi se pyare bhi mil jate hai
-----------------------------------------------------------
Khidki khuli, Zhulfe nikli,
Khidki khuli, Zhulfe nikli,
Maine soch kismat khuli,
Par afsos, din itwaar tha,
Khuli zhulfo wala Sardar tha
-------------------------------------------------------------
vaado ko ikraar na samjho,
Khamoshi ko inkaar na samjho,
Nazre milti hai hazaroo se,
Nazro ke milne ko pyar na samjho..
------------------------------------------------------------
Koi ankhon se baat kar leta hai,
Koi ankhon mein mulakat kar leta hai,
Bada mushkil hota hai jawab dena,
Jab koi khamosh rehkar sawaal kar leta hai.
-------------------------------------------------------------
PHIR AAJ WAHI MAIKADE KI YAAD AA RAHI HAI
PHIR AAJ WAHI SHARAB KI KUSHBU AA RAHI HAI
PHIR AAJ WAHI SAQI KI PUKAR AA RAHI HAI
PHIR AAJ WAHI BHEED KI TANHAEE MUJE SATA RAHI HAI......
--------------------------------------------------------------
Sharab bani to maikhane bane ...
Sharab bani to maikhane bane ...
pyar bana to deewane bane
Kuch to baat hogi aap mein
ki yuhi nahin paagal khane bane.
----------------------------------------------------------------
Thursday, April 20, 2006
Original Joke : The Longest Hour ...
There are times which make us think about how we take things for granted. How we forget about everybody else who may be craving for water and use it carelessly just because we have it in abundance. You must be thinking what is with all this preaching. Ok, let me come straight to the point.
Today began just like any other day. As usual sun rose (for me ) at 10:00. After answering nature's call and brushing my teeth I went back to my routine, that is, to sleep again. If it was not for the pressure, do you think I would be up so early?? I was having a dream about kite flying when my sleep was interrupted by keyur's knock on my door. You all still must be puzzled "what does all this have to do with the longest hour?". Chill out, have patience, I am just coming right there.
I had my lunch and after a couple of hour pressure was building up in my intestine. So I carried the bottle of dettol liquid hand wash to the rest room. So far so good, isn't it? I went in there, finished my business, opened the tap and ooops!!! Just one moment ago I was living my life happily and now I was cadaverous. Seemed like my whole world was on the verge of termination. Was it a sign of a doom's day or was I over-reacting? Yes, you guessed it right. Not even a single droplet of water came out the tap.
They ask you about a zillion different weird situation at SRT ( Situation Reaction Test ) in SSB ( Services selection board ), but this kind of situation never made its way in SRT. May be none of the officers had to encouter such problems or may be because there is no right answer for this. Even if any of them had faced such a situation, who would want it to be shared publicly? Hey, I am writing all this things down here in the public interest.
Someone really said it true that we dont remember GOD unless we are in trouble. If this is not a trouble then what is? I was praying to god earnestly to come to the rescue. Of course, I felt very shameful to remember GOD at such a place and in such a situation. Lekin marta kya na karta!!
As I had nothing else to do there, I started thinking!! My mind experienced an an avlanche of thoughts. Boy I wished I had been in america, at least I could have had some tissues to clean out my a** and I could have come out of the cubicle(!!). I started to realise how it must have felt like being in a gas chamber.
I composed myself and started consoling me. "Hey, someone else might have trapped also". "Sooner or later, somebody would realise that there is no water supply and will inform security to start the water pump". So I decided to be in there until I get help. How was I supposed to know that it would take an hour?? My legs started to go numb. At each passing moment hope of getting any help was fading. That was not the place I wished to die!!.
All of a sudden, a sweet sound filled my ear with a feeling of exuberance. That was the sound of a droplet of water colliding with the bottom of a mug. My heart was filled with ray hope. I was not even half as eager to know my 12th std score as I was to hear the sound of a cascade coming out of the tap. Finally, my patience paid off. Freedom, the most beautiful word in this world.
So guyz, what did we learn from this story?
1) Precaution is better than cure : always check whether enough water is there in the rest room before you order your artillary to attack pakistan.
2) Save water : Because can you imagine what could have happen in its absence?
Today began just like any other day. As usual sun rose (for me ) at 10:00. After answering nature's call and brushing my teeth I went back to my routine, that is, to sleep again. If it was not for the pressure, do you think I would be up so early?? I was having a dream about kite flying when my sleep was interrupted by keyur's knock on my door. You all still must be puzzled "what does all this have to do with the longest hour?". Chill out, have patience, I am just coming right there.
I had my lunch and after a couple of hour pressure was building up in my intestine. So I carried the bottle of dettol liquid hand wash to the rest room. So far so good, isn't it? I went in there, finished my business, opened the tap and ooops!!! Just one moment ago I was living my life happily and now I was cadaverous. Seemed like my whole world was on the verge of termination. Was it a sign of a doom's day or was I over-reacting? Yes, you guessed it right. Not even a single droplet of water came out the tap.
They ask you about a zillion different weird situation at SRT ( Situation Reaction Test ) in SSB ( Services selection board ), but this kind of situation never made its way in SRT. May be none of the officers had to encouter such problems or may be because there is no right answer for this. Even if any of them had faced such a situation, who would want it to be shared publicly? Hey, I am writing all this things down here in the public interest.
Someone really said it true that we dont remember GOD unless we are in trouble. If this is not a trouble then what is? I was praying to god earnestly to come to the rescue. Of course, I felt very shameful to remember GOD at such a place and in such a situation. Lekin marta kya na karta!!
As I had nothing else to do there, I started thinking!! My mind experienced an an avlanche of thoughts. Boy I wished I had been in america, at least I could have had some tissues to clean out my a** and I could have come out of the cubicle(!!). I started to realise how it must have felt like being in a gas chamber.
I composed myself and started consoling me. "Hey, someone else might have trapped also". "Sooner or later, somebody would realise that there is no water supply and will inform security to start the water pump". So I decided to be in there until I get help. How was I supposed to know that it would take an hour?? My legs started to go numb. At each passing moment hope of getting any help was fading. That was not the place I wished to die!!.
All of a sudden, a sweet sound filled my ear with a feeling of exuberance. That was the sound of a droplet of water colliding with the bottom of a mug. My heart was filled with ray hope. I was not even half as eager to know my 12th std score as I was to hear the sound of a cascade coming out of the tap. Finally, my patience paid off. Freedom, the most beautiful word in this world.
So guyz, what did we learn from this story?
1) Precaution is better than cure : always check whether enough water is there in the rest room before you order your artillary to attack pakistan.
2) Save water : Because can you imagine what could have happen in its absence?
Tuesday, April 18, 2006
Original Joke : Gupta v/s Orange
Hi,
It's been quite a while since I was away from blogging. I know, I have missed many interesting incident that I should have written over here. Writing down a couple of incidence of gupta's invincible humour.
-------------------------------------------
Gupta talked to me one day about a new victim of his humour. He was describing how he stumped a girl from orange who called him regarding advantages of post-paid plans. Here is how it goes....
It was early morning ( Though it was 10'o clock, it must be considered early morning according to gupta's routine ) when gupta's mobile rang.
xyz : Hello sir, sorry to disturb you but I will only take two minutes of your time.
Gupta ( he must have chuckled knowing his prey is coming on its own to be hunted :D ) : Ok go ahead
xyz : Sir, I am nisha, callling from orange. According to our records you are using our prepaid services. I guess you must be using 300 Rs Prepaid coupons to recharge your mobile phone
Gupta : Who said I am using 300 Rs Prepaid coupons to recharge my mobile??
xyz : Oh... then which coupon do you use to recharge?
Gupta : 500 Rs
xyz : Ok sir, if you using 500 Rs coupon then you must be getting talk time around 300 but according to our new scheme....
Gupta ( interrupting the girl ) : Who said that I get talk time of only 300 on 500 rs coupon?
xyz ( quite puzzled by now ) : Ok sir, so under which scheme are you using 500 rs coupon?
Gupta : Sorry young lady, your two minutes are over :D
Things do not finish here. Just after a few days of this incidence achyut came to visit IIT. We all went to anudeep's place by bus. Gupta shared his tale of above mentioned encounter with an orange girl. Just then an idea popped in my mind and I blurted it out. "Gupta, ab ki baar agar vo phone kare to use bol ki, 'why don't we discuss this over a cup of coffee?' ". I just mentioned my thought to him casually, hardly have I known that his mind made a note to implement it as soon as an opportunity arrives.
He did not had to wait too long for the same. The opportunity rang on his mobile ( or knocked his door.. or whtever you call it is ) . I was sitting there in his room checking my mails. He was fast asleep because the sun was not set yet :D. Tring tring... tring tring...( Now, this is not how his mobile rings .. but I do not know how to mimic it in words.. so you have to bear with me ). Gupta woke up with an unpleasant expression, ( He must be thinking in a rage " Kis gustakh ne aisi harkat ki hai?? " ). "Hello Sir, I am nisha speaking from orange, I wanted to let you know about a new postpaid plan which is ... " said a girl with a sweet, calm voice ( without having any clue of what is going to happen the next moment ) was interrupted by gupta. "Why dont we discuss this over a cup of coffee?? ". There you go my friend... I was laughing my a** out uttering in my mind "ye laga chhakka aur gupta phir champion". Obviously the girl was stunned and could not speak anything for at least 7-8 second. She said "Oh! my GOD!!!" after composing herself a bit. She repeated the phrase a couple of more times. "Sir please, pahele plan sun lijiye" she pleaded. "So you dont like coffeee??" said gupta, not in a mood to let go. "Sir , plan sun lijiye na... pleeeaazze", an intense pleading this time. "But I like coffee", gupta remained unaffected. Some more request from the girl and some more teasing from gupta went on for a while. Finally gupta blew her off saying he is not interested in listening to her "plans" if she is not interested in his coffee.
This made it clear to me why gupta is not having any luck with gals :D. I wonder whether there exist a girl who can understand and appreciate gupta's humour. Anyways, no wonder he has to end his day by having a cup of coffee with saket :D.
It's been quite a while since I was away from blogging. I know, I have missed many interesting incident that I should have written over here. Writing down a couple of incidence of gupta's invincible humour.
-------------------------------------------
Gupta talked to me one day about a new victim of his humour. He was describing how he stumped a girl from orange who called him regarding advantages of post-paid plans. Here is how it goes....
It was early morning ( Though it was 10'o clock, it must be considered early morning according to gupta's routine ) when gupta's mobile rang.
xyz : Hello sir, sorry to disturb you but I will only take two minutes of your time.
Gupta ( he must have chuckled knowing his prey is coming on its own to be hunted :D ) : Ok go ahead
xyz : Sir, I am nisha, callling from orange. According to our records you are using our prepaid services. I guess you must be using 300 Rs Prepaid coupons to recharge your mobile phone
Gupta : Who said I am using 300 Rs Prepaid coupons to recharge my mobile??
xyz : Oh... then which coupon do you use to recharge?
Gupta : 500 Rs
xyz : Ok sir, if you using 500 Rs coupon then you must be getting talk time around 300 but according to our new scheme....
Gupta ( interrupting the girl ) : Who said that I get talk time of only 300 on 500 rs coupon?
xyz ( quite puzzled by now ) : Ok sir, so under which scheme are you using 500 rs coupon?
Gupta : Sorry young lady, your two minutes are over :D
Things do not finish here. Just after a few days of this incidence achyut came to visit IIT. We all went to anudeep's place by bus. Gupta shared his tale of above mentioned encounter with an orange girl. Just then an idea popped in my mind and I blurted it out. "Gupta, ab ki baar agar vo phone kare to use bol ki, 'why don't we discuss this over a cup of coffee?' ". I just mentioned my thought to him casually, hardly have I known that his mind made a note to implement it as soon as an opportunity arrives.
He did not had to wait too long for the same. The opportunity rang on his mobile ( or knocked his door.. or whtever you call it is ) . I was sitting there in his room checking my mails. He was fast asleep because the sun was not set yet :D. Tring tring... tring tring...( Now, this is not how his mobile rings .. but I do not know how to mimic it in words.. so you have to bear with me ). Gupta woke up with an unpleasant expression, ( He must be thinking in a rage " Kis gustakh ne aisi harkat ki hai?? " ). "Hello Sir, I am nisha speaking from orange, I wanted to let you know about a new postpaid plan which is ... " said a girl with a sweet, calm voice ( without having any clue of what is going to happen the next moment ) was interrupted by gupta. "Why dont we discuss this over a cup of coffee?? ". There you go my friend... I was laughing my a** out uttering in my mind "ye laga chhakka aur gupta phir champion". Obviously the girl was stunned and could not speak anything for at least 7-8 second. She said "Oh! my GOD!!!" after composing herself a bit. She repeated the phrase a couple of more times. "Sir please, pahele plan sun lijiye" she pleaded. "So you dont like coffeee??" said gupta, not in a mood to let go. "Sir , plan sun lijiye na... pleeeaazze", an intense pleading this time. "But I like coffee", gupta remained unaffected. Some more request from the girl and some more teasing from gupta went on for a while. Finally gupta blew her off saying he is not interested in listening to her "plans" if she is not interested in his coffee.
This made it clear to me why gupta is not having any luck with gals :D. I wonder whether there exist a girl who can understand and appreciate gupta's humour. Anyways, no wonder he has to end his day by having a cup of coffee with saket :D.
Friday, March 17, 2006
Good bye my friend...
well,
it's me again after a long time. A lot of things happened during this time but becuase of my laziness, could not write it down over here. One more friend of mine have headed to abroad for better career... but this time ..that friend was one of my best friend pranay.
Initially, his plan was to stay at parla but then, luckily, he changed his mind ( needless to say i was the actuator ) to stay at my room. Obviously, he was worried for the life ahead.. after all , saudi arabia is not what people dream for. But I guess he would make much more money over there as compared to what he was making it over here.
He was sad the night before his departure, it was not the worry
about his future, but it was regarding his mom. He was already
feeling nostalgic in just one day. I guess it would be much much hard
for his mom to brook the pain of separation.
Anyways, I could not go to the airport to drop him because his
timings exactly coincided with SecNet dates. So he is not at Saudi and
feeling nostalgic. I dont know how exactly it feels. I have never been
so far from my home... may be I will have to bear the same agony if i
crack a university for PhD.
Good bye my friend... and wish you a very best of luck for your future ahead.
--
it's me again after a long time. A lot of things happened during this time but becuase of my laziness, could not write it down over here. One more friend of mine have headed to abroad for better career... but this time ..that friend was one of my best friend pranay.
Initially, his plan was to stay at parla but then, luckily, he changed his mind ( needless to say i was the actuator ) to stay at my room. Obviously, he was worried for the life ahead.. after all , saudi arabia is not what people dream for. But I guess he would make much more money over there as compared to what he was making it over here.
He was sad the night before his departure, it was not the worry
about his future, but it was regarding his mom. He was already
feeling nostalgic in just one day. I guess it would be much much hard
for his mom to brook the pain of separation.
Anyways, I could not go to the airport to drop him because his
timings exactly coincided with SecNet dates. So he is not at Saudi and
feeling nostalgic. I dont know how exactly it feels. I have never been
so far from my home... may be I will have to bear the same agony if i
crack a university for PhD.
Good bye my friend... and wish you a very best of luck for your future ahead.
--
Wednesday, January 25, 2006
One nice pic of mine :-)
This photo was taken by hitesh when we were experimenting with the new bought sony cybershot camera. This is one of my nice pics that was taken by keyur's digicam. Here one can easily look at the mess in the background. Yes, that's my room at Hostel 4 New wing.
On my way towards mental peace ...
So as expected, I got a BB in my second stage presentation. The grade did not come as a surprise as I knew I could not have got better grade after such a disaster. Anyways, whatever happened has happened and one can't turn it back.
I thought my guide would have been very angry after the presentation. But when I talked to him the next day, I was relaxed to find out that is not the case. In fact he was searching for me to tell me about a job opportunity in the field of formal verification at atrenta. Though he does not talk informally with his students, he cares a lot about his students.
Anyways, now the presentation is over I am just counting hours for me to reach my home. Home : A place where all worries leave me and I just enjoy like anything. I dont have PC at my home but frankly speaking that's the best part. I can enjoy a real vacation, without connectivity, without PC . I can be myself. No need to involve computer science at home :-)
I am sure my visit to my home, bhavnagar and rajkot will referesh me and I will again have the strength to fight rest of the battle that are to come.
I thought my guide would have been very angry after the presentation. But when I talked to him the next day, I was relaxed to find out that is not the case. In fact he was searching for me to tell me about a job opportunity in the field of formal verification at atrenta. Though he does not talk informally with his students, he cares a lot about his students.
Anyways, now the presentation is over I am just counting hours for me to reach my home. Home : A place where all worries leave me and I just enjoy like anything. I dont have PC at my home but frankly speaking that's the best part. I can enjoy a real vacation, without connectivity, without PC . I can be myself. No need to involve computer science at home :-)
I am sure my visit to my home, bhavnagar and rajkot will referesh me and I will again have the strength to fight rest of the battle that are to come.
Monday, January 23, 2006
Second stage presentation : A disaster
That's me again after a long break. From last several days my status in yahoo messenger shown "deeply burried into trouble" and one can easily guess what that trouble was.
I did not want to push myself to the limits as I did in my first stage I started working well before the submission date. I started my work in september, although slowly but at a constant pace. After finishing with my subject GRE ( Fortunately, I manage to get 91% in a week's effort) I accelerated my efforts in my project.
Entire circuit manipulation by myself!!! I used STL very extensively and overwhelming use of pointers and indirection. No wonder I spend many hours trying to get rid of the nightmare of any programmer, that is : "Segmentation fault". Also, I discovered another nightmare which many other fellow programmers are fortunate not to see it in their lifetime. That is "****glibc error***:double free or corruption". I really wonder how difficult would it be if someone tries to extend my MTP. Of course, I have put in comments in the program and a lot of guidelines can be found in the CVS logs. But I must admit, in order to complete certain functionality in a hurry, i compromised in terms of design. I could have done better design but I would rather go on with adding other functionalities than rewriting a lot of code.
Anyways, at the end of december I was busy in placements. I had not signed yahoo, MS, qualcomm, morgan stanley, sybase. Google, amazon and trilogy came at the early stage of CSE placement and they all kicked me out after the written test. However, it did not come as a surprise to me as I was damn confident about my skill of writing a C/C++ program on a paper. I knew that as long as companies will ask to write a program on a piece of paper, I am not going to be selected for the interview. Companies came and gone but it did not had any effect on me. I was still working very hard with my second stage implementation.
Then came symantec, the first company for me which did not ask to write a C/C++ program on a piece of paper. Of course, I made my way through all three interviews. But, HR screwed me up. The moment I finished my HR interview I knew that I am gone. Rejection by symantec shook me up. Fortunately I was able to crack Induslogic the next day. This time I had to tell a lot of lie in front of HR, but I knew I had no other choice if I wanted to get selected.
Anyways, the same day I went to meet my supervisor. I asked him which company is better to work with in the area of formal verification. He was supportive. He offered to get me an interview with all those companies. So nice of him!!! But as soon as we switched topic to my MTP, I did not knew that a long TODO list was waiting for me. Last 9 days were remaining and I had to finish the work on the TODO list. From the moment I heard what my supervisor is asking me to do, I knew that implementation is way beyond my capacity. So it was obvious, I could not finished all three things which he asked me to implement in time.
Without worrying much about the implementation I started writing my report. I could not afford to waste much time on implementation anymore. I would have missed my submission deadline if I had continued with my implementation.
And as usual, my guide was too busy to look at my report, which by the way, I handed him over two days prior to submission deadline. I thought the same thing will happen to the slide. Fortunately or unfortunately he had a look at my slide a day ahead of my presentation. Series of suggestion followed and I had to burnt my night again to modify the slides.
As the time of presentation approached my anxiety increased. I had not slept well for two days ( and two nights also ;-) ). Something inside me was telling me that things may go wrong and it did. Examiner started with very simple questions but I got confused, my mind just went blank. I was not understanding what he was asking, what he was saying. And even if I knew the answer I could not present or express it. Fortunately my guide came to the rescue when examiner and chairman started to corner me on the wrong basis.
So all in all, my presentation was a disaster. It's been a relief to me that my guide did not think so. I have not gone to see my grades and I know that AA and AB are out of sight after having such a bad presentation. And I can not blame it all to examiner. I must admit I was not well prepared for the presentation.
Now I have only one chance.. the third stage. I better be prepared for that.
I did not want to push myself to the limits as I did in my first stage I started working well before the submission date. I started my work in september, although slowly but at a constant pace. After finishing with my subject GRE ( Fortunately, I manage to get 91% in a week's effort) I accelerated my efforts in my project.
Entire circuit manipulation by myself!!! I used STL very extensively and overwhelming use of pointers and indirection. No wonder I spend many hours trying to get rid of the nightmare of any programmer, that is : "Segmentation fault". Also, I discovered another nightmare which many other fellow programmers are fortunate not to see it in their lifetime. That is "****glibc error***:double free or corruption". I really wonder how difficult would it be if someone tries to extend my MTP. Of course, I have put in comments in the program and a lot of guidelines can be found in the CVS logs. But I must admit, in order to complete certain functionality in a hurry, i compromised in terms of design. I could have done better design but I would rather go on with adding other functionalities than rewriting a lot of code.
Anyways, at the end of december I was busy in placements. I had not signed yahoo, MS, qualcomm, morgan stanley, sybase. Google, amazon and trilogy came at the early stage of CSE placement and they all kicked me out after the written test. However, it did not come as a surprise to me as I was damn confident about my skill of writing a C/C++ program on a paper. I knew that as long as companies will ask to write a program on a piece of paper, I am not going to be selected for the interview. Companies came and gone but it did not had any effect on me. I was still working very hard with my second stage implementation.
Then came symantec, the first company for me which did not ask to write a C/C++ program on a piece of paper. Of course, I made my way through all three interviews. But, HR screwed me up. The moment I finished my HR interview I knew that I am gone. Rejection by symantec shook me up. Fortunately I was able to crack Induslogic the next day. This time I had to tell a lot of lie in front of HR, but I knew I had no other choice if I wanted to get selected.
Anyways, the same day I went to meet my supervisor. I asked him which company is better to work with in the area of formal verification. He was supportive. He offered to get me an interview with all those companies. So nice of him!!! But as soon as we switched topic to my MTP, I did not knew that a long TODO list was waiting for me. Last 9 days were remaining and I had to finish the work on the TODO list. From the moment I heard what my supervisor is asking me to do, I knew that implementation is way beyond my capacity. So it was obvious, I could not finished all three things which he asked me to implement in time.
Without worrying much about the implementation I started writing my report. I could not afford to waste much time on implementation anymore. I would have missed my submission deadline if I had continued with my implementation.
And as usual, my guide was too busy to look at my report, which by the way, I handed him over two days prior to submission deadline. I thought the same thing will happen to the slide. Fortunately or unfortunately he had a look at my slide a day ahead of my presentation. Series of suggestion followed and I had to burnt my night again to modify the slides.
As the time of presentation approached my anxiety increased. I had not slept well for two days ( and two nights also ;-) ). Something inside me was telling me that things may go wrong and it did. Examiner started with very simple questions but I got confused, my mind just went blank. I was not understanding what he was asking, what he was saying. And even if I knew the answer I could not present or express it. Fortunately my guide came to the rescue when examiner and chairman started to corner me on the wrong basis.
So all in all, my presentation was a disaster. It's been a relief to me that my guide did not think so. I have not gone to see my grades and I know that AA and AB are out of sight after having such a bad presentation. And I can not blame it all to examiner. I must admit I was not well prepared for the presentation.
Now I have only one chance.. the third stage. I better be prepared for that.
Posted by
Saurabh Joshi
at
1:30 PM
Saturday, January 14, 2006
Original Joke : ek penjon le lunga!
well, here i am back after a long time. i was a bit preoccupied ( or at least was pretending to be occupied ;-) ) in my report submission work. Anyways, here it goes
Scenario : A typical IIT night. At H2 canteen at around 12:30 in the night. Me, gupta, saket and sushil were chatting. Gupta was in his usual mood of "hypothetical situation".
Gupta : To Mr Saurabh Joshi, Aap ko IIT main kaun si ladki pasand hai?
Gupta : A ) Girl1 B) Girl2 C) Girl3 D) Girl4.
( I would prefer not to put the original options .. coz gupta was at his height of imagination while providing options )
Gupta : To bataiye... kis ke sath jana chahenge aap. A, B, C ya D?
( I knew I had to choose one of the options.. not choosing an option would have given them more excuse to tease me ;-) :D. So I was puzzled by this question and was wondering what to say! )
Gupta : Bahut confused dikh rahe hai? Life line use karna chahenge?
( I still did not answer .. to save myself from being teased anymore I knew I had to give answer very very cautiously )
Gupta : Audience poll lena chahenge aap? Oh... Aur results hai? A) 25% B) 25% C) 25% D) 25%
Badi hi kathin samasya me fans gaye hai aap. Audience poll aap ki kuchh khas madad nahi kar sakta. Aisi situation me aap kya karenge?
Sushil (out of the blue) : Aasan hai, ek penjon le lunga ( !!!! :-O :D :-)) )
(This was a punch line of an ad of a painkiller 'penjon')
Scenario : A typical IIT night. At H2 canteen at around 12:30 in the night. Me, gupta, saket and sushil were chatting. Gupta was in his usual mood of "hypothetical situation".
Gupta : To Mr Saurabh Joshi, Aap ko IIT main kaun si ladki pasand hai?
Gupta : A ) Girl1 B) Girl2 C) Girl3 D) Girl4.
( I would prefer not to put the original options .. coz gupta was at his height of imagination while providing options )
Gupta : To bataiye... kis ke sath jana chahenge aap. A, B, C ya D?
( I knew I had to choose one of the options.. not choosing an option would have given them more excuse to tease me ;-) :D. So I was puzzled by this question and was wondering what to say! )
Gupta : Bahut confused dikh rahe hai? Life line use karna chahenge?
( I still did not answer .. to save myself from being teased anymore I knew I had to give answer very very cautiously )
Gupta : Audience poll lena chahenge aap? Oh... Aur results hai? A) 25% B) 25% C) 25% D) 25%
Badi hi kathin samasya me fans gaye hai aap. Audience poll aap ki kuchh khas madad nahi kar sakta. Aisi situation me aap kya karenge?
Sushil (out of the blue) : Aasan hai, ek penjon le lunga ( !!!! :-O :D :-)) )
(This was a punch line of an ad of a painkiller 'penjon')
Subscribe to:
Posts (Atom)