Some computer science PJs

Courtesy : Ramprasad, Deepanjan

One day Deepanjan (a PhD student at IITK) and I were waiting for a bus
and we started coming up with CS PJs. Needless to say, they were
complete kundis! Thought I'll share the madness with you guys as well.
----------

P and NP walk into a bar and order the same cider each. The bartender
prepares one of them and place it on the table. P looks at NP and
asks, "Is this yours or mine?" and NP replies "Mine, I guess".
-------------

People are sitting in a bar, and Balanced-Paranthesis walks in and
shouts "Yabbadabbadooo". The bartender asks someone, "What's with that
guy?". "Oh him... he's context free".
---------------

A prof is taking attendance and shouts, "Palindromes...... (no
response) ... Palindromes ....(again nothing).... Can someone tell me
why palindromes isn't here?" and some student replies "He is not
regular sir".

--------------
A prof asks a student "what is 6x6" and gets the answer "32" from him.
And the prof still gives him some marks because he was only off by a
bit.

------------
(this srikanth and I were talking about someday) Someone asks me whom
I work under and I reply, "RP is in MA of course!" ( hint : Ramprasad works with Manindra Agrawal )

----------------------
(okay, a really horrible that I came up with while composing this
mail) P is walking in an alley and some suspicious guys are following
him. He starts running and those guys pursue. P gets very tense and
suddenly discovers his new power and starts tossing coins at them. The
robbers just run for those coins and P escapes. Someone who saw this
asks him what happeend and how he got these powers. And P replies,
"I'm P. But when I am tense, I become BPP"
 -------------------
 If a guy named Franklin Joe shows that graph isomorphism is in P, what
would he be called? GI-Joe!
----------------------


A chemistry student was studying the acidity of some compound and he
found it to be very alkaline. Meanwhile, some other CS grad student
managed to show that NP \subseteq P/poly. Suddenly the chemistyr
student foudn that his compound was very acidic. Why?
Because pH collapsed

-----------------------------
An immortal SMS by Rahul Muthu:
Hey, what did Manindra and co prove in 2002? I got an oxford
dictionary which is a 1960 edition, and even there 'Primes' is in P!
--------------------------------


Another one by Rahul Muthu:
A bunch of mathematicians were going for a cycle race in a forest. All
of them made it more or less on time but one of them finished the race
VERY late. When asked why, he explained that he walked the course. He
was a graph theorist, and thought cycles weren't allowed in forests.
--------------------------
P is late for class but has to head back for lunch. He rushes into the
lab and shouts "hey, can someone lend me their cycle?". Hamilton
offers his keys and P replies "No no, you keep yours. I can't find
your goddamn cycle. I'll take Euler's"

Math humour

http://nfccomic.com/comics/205.jpg

Logic and Games

Hi All,
Well, it has been some time since I have posted anything technical on this blog. Lately I have been very lazy about writing down interesting things over here. The biggest pain that I face is that there is no support for latex in blogspot.

Anyways, coming down to the point. I am attending a few lectures by Rohit Parikh at Logic School. He is a very good orator, I must say. As a part of his talk on "Finite and Infinite Dialogues", he mentioned a very famous product-sum puzzle. I am writing it down here just for the sake of completeness.

----

Mr P and Mr S are told product and sum of two number a and b respectively, where 2<= a,b <= 99.
P : I don't know the numbers.
S : I knew you did not know them.
P : Now, I know the numbers
S : Now, I know them too.

the solution can be found from dijkstra's paper.
----

With this example, Prof. Rohit went on to describe interesting world of finite and infinite dialogs between two parties in order to determine certain information. Yet another interesting example that he gave was as follows :

A randomly chosen positive integer n is chosen. One of them is written on Ann's forehead and n+1 is written on Bob's forehead. Now, each of them are asked to determine the numbers written on their forehead.

If 1 is written on Ann ( called as A now on ) and 2 is written on Bob ( called as B from now on ). Bob can immediately deduce that his number is 2. If A has got 3 and Bob has got 2 then A have two possibilities 1 or 3. When Bob says I don't know, A can determine that number she has got is 3. It is easy to prove by induction how they can determine their numbers in linear time with respect to number n.

One can devise a game where it would take infinite amount of time to determine one's number. Here is the interesting lecture notes which covered these beautiful examples.

PS : Please note that lecture notes/papers may be copyrighted. Contact the authors in case one wish to use it for non-academic purpose.

The Biggest Number

Hi,
Well, I was referred to a very nice article by ali today. It describes human's quest to find the biggest number, in a very interesting way. I actually wished to copy it over here to make sure I do not loose it, in case the original post is removed. But then the it contained some images too. So here is the place where original article can be found :
http://www.scottaaronson.com/writings/bignumbers.html

Space v/s Time

Hi all,
I know there has been a long pause on my blog. Well, it was a transition period for me from IRL to IITK. Yes, I have joined its CSE department as a PhD student. Anyways, I know the title is somewhat misleading as many would think this post has something to do with einstein's theory of relativity and the four dimensional world. You are grossly mistaken if you think so.

Actually, as part of my coursework here I am attending a course by Prof Manindra Aggarwal. Well, it is a big mistake on my side that I have not registered for this course. Even the bigger mistake is that I have registered for a course named "Computational Number Theory and Algebra" by Prof Piyush Kurur. The content itself may be interesting but the way that guy teaches the course, makes it difficult. The worst part is that all the exams of this course are "take home" exams.

Anyways, let's get back to the point. It is indeed an honour to sit in Prof Manindra's class and see him deliver some of the toughest content of the course with a flair. All the people with computer science background are aware of the P not equals NP conjecture. This decade old conjecture has still remain unbeaten. In other words, this conjecture states that the set of problems that can be solved by a deterministic turing machine in polynomial time and the set of problems that can be solved by a non-deterministic turing machine in polynomial time are equal.

There is another notion called Space Complexity in computer science. Space complexity is a measure of the space required to solve any problem by an algorithm. One wonders, whether there is any difference between the set of problems which can be solved by a deterministic turing machine in polynomial space , and the set of problems which can be solved by a non-deterministic turing machine in polynomial space. It actually turns out that non-determinism does not give any more power over deterministic mechanism when space is the criterion. Due to Savitch's theorem it is proven that PSPACE equals NPSPACE.

One may wonder why the similar version in time complexity is yet unbeaten? Non-determinism gives the power to explore exponentially many threads of computation simultaneously. If a deterministic turing machine tries to mimic the behaviour of a non-deterministic one, it has to explore all the paths one by one. It costs time to go through all the paths one by one. One has to add up all the time that has been spend. But does one really have to add up the space as well??? I felt really stupid when I come to know that the reason why power of deterministic and non-deterministic turing machine comes out to be same, is that space can be reused!!!!

As a wild thought, may be if a deterministic turing machine can go back in time to explore the alternate future, thus, reusing the time we may as well have P = NP :D.

Young Tableau

Hi All,
The other day me, sanjeet, and pranjal were discussing a few questions ( or puzzles ) which are likely to be asked in technical interviews. One of the question that was asked to someone in google was about finding out a specific element in an n x n Young Tableau.

Let me first define, what a young tableau is. It is an m x n array with the following property.

for all j = 1 to n-1, A[p][i] <= A[p][i+1]
and for all , i = 1 to m-1 , A[i][q] <= A[i+1][q] It is easy to see that following statement holds for a young tableau.

1. For any sub-matrix of a young tableau, the top-left element is the smallest element within that sub-matrix.
2. For any sub-matrix of a young tableau, the bottom-right element is the largest element within that sub-matrix.

Now, the problem is to find out a given element within an n x n young tableau.

----
Method -1
----

Start with the top-right element of the tableau. Compare this element e with the element to be found x.
if e > x then
discard the column in which e appears. ( Because e is the first(smallest ) element of that column.
else
discard the row in which e appears.
end if.
Repeat this exercise until the element is found or the tableau is exhausted.

It is easy to see that time complexity of Method-1 is O(n). As at every step we will discard either row or column which will take at most 2n steps.

---------
Method - 2
---------
Do a binary search over the diagonal of the tableau. If we find the desired element x then we are done. If not, we will have two element u and v where u <> u is the bottom-right element and v is the top-left element. The elements that we will discard at each step would be at least half of the elements in the original matrix.
Here is why,

i^2 + (n-i)^2 function is minimum where i=n/2. With i=n/2 the value of the function is (n^2)/2.

Now, if we do the analysis with respect to number of elements.
T(n^2) = 2T((n^2)/4) + logn

or

T(m) = 2T(m/4) + 0.5 logm

Solution of this recurrence, turns out to be O(m^(0.5)) = O(n). So, there is no improvement over the complexity as compared to the first method. Besides, this second method fails when the sub-matrices that were discarded were not square. In which case, the remaining two sub-matrices will not be square either.
----
Method 3
------
Compare the central element e with the desired element x.
if e > x then discard the bottom-right quadrant of the tableau.
else discard the top-left quadrant of the tableau.

Now , we are left with three sub-matrices of the size n/2 x n/2.

The recurrence would be

T(n) = 3T(n/2) + O(1).

Solving it would give us n^(log_2 3) = n^1.585. It turns out that even though in Method-1 you discard n elements and in this method you discard (n^2)/4, the complexity does not favour Method-3. Anyways, it was a good exercise to do this analysis.

Necklace puzzle - yet another solution

Hi all,

I am posting here another solution to "Necklace Puzzle". The solution is by my friend Vaibhav Gupta

-------

Let A and B are the 2 necklaces with N gemstones. A and B has three types of
gemstones which are equal in number.

A = A[1] A[2] ... A[N]
B = B[1] B[2] ... B[N]

Where A[i] is the ith gemstone in Necklace A.
B[i] is the ith gemstone in Necklace B.

Let Color(A[i]) represents the type of the gemstone A[i].

We construct a bipartite graph G = (X,Y,E), with the following condition:

For each gemstone A[j] in A we create a node X_j in X. So |X| = N
Foe each gemstone B[j] in B we create a node Y_j in Y. So |Y| = N
E is the edges set from node in X to node in Y.

E = { (u,v) | u \in X and v \in Y and Color(u) = Color(v)}

|E| = (N^2) / 3 since each node has exactly N/3 edges.

We define weight to each edge in E:
Weight(e) = orientation of the string.
OR Mathematically
Weight((X_i,Y_j)) = i - j if i>=j
= N+i-j otherwise

0 <= Weight((X_i,Y_j)) <= N-1 since 1<=i<=N, 1<=j<=N So there are N possible values of weight.

Now we just need to prove that there are atleast N/3 edges of same weight.
This can be proved by pigon hole principle. There are (N^2) / 3 edges and
each edge has N possible values of weight so there must exist a set of
ceil(|E|/N) edges of same weight

|E| / N >= N/3

Hence proved.

For general case :

For 3 gemstone types
( a^2 + b^2 + c^2 ) / (a + b + c)

Where a is the number of gemstone of type 1.
b is the number of gemstone of type 2.
c is the number of gemstone of type 3.

For m gemstone types:
(N_1^2 + N_2^2 + N_3^2 ... + N_m^2) / (N_1+N_2+N_3 ..+N_m)

where N_i is the number of gemstone of type i.

---------

Necklace Theorem - Solutions to puzzles

Hi All,
So I am back again after some gap. This post will describe the solutions to the two puzzle that I posed as part of my prequel post "Necklace Theorem". For the sake of clarity I am copying the puzzles again over here.

1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.
As shown in the figure on the left, let us consider a baseline B. The circle represent the point set we are interested in. Refer to the prequel of this post and convince yourself that it is possible to have a line in any given direction which divides the point set into two equal half. Hence, it is also possible to have two orthogonal lines both of which will divide the point set into two equal half. ( When I say, two equal half, I mean that division in two portion satisfying the constraint "less or equals n/2" ). As both p and q divides the point set into two equal half, the region which is captured on top-left and bottom-right will be equal ( call it x, or to be more precise "less or equal x" ). Similarly, tom-right and bottom-left would be equal ( call it y). Let us have a function f(x,y) = (x-y) = v. By rotating p and q , 90 degrees we will have function value exactly negative, as x and y would swap their places. From intermediate value theorem we can argue that there will be a configuration where x = y = n/4.

2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.

With respect to the baseline B, we can have two lines p and q, each dividing the point set into equal half and region trapped as shown in figure would be equal to n/6 on each side. ( n/6 is written outside the circle to make it readable ). Now, as shown in the prequel post, we can have a line r which will divide the two point sets ( each of size n/3 ) into two equal half. This line r need not be concurrent with p and q. Let the triangle trapped between these three lines is equal to A. As we rotate this configuration 180 degree the area will become -A. Again, from intermediate value theorem we can state that area will be 0 at some configuration making r concurrent to p and q. Thus, each segment will have size n/6.

Necklace Puzzle

Hi All,
So I am here back again with a new interesting puzzle ( courtesy Vaibhav Gupta ). I am copying his mail verbatim below followed by the solution that I have in mind.
---------- Puzzle ------
NECKLACE PUZZLE #2

There are two circular necklaces with same number of three types of gemstones,
but the gemstones may be strung in different order along the necklace.

Now the two necklaces are placed on one top of the other so that the
gems are aligned
one above the other. Count the number of locations where the pair of
gems (one from
the lower necklace, one from the upper) is of the same type.
Since one necklace can be rotated relatively to the other, there are
many orientations
in which the count of matching gems can be taken.

Prove that there is at least one orientation where the number of
matches is at least
a certain number v.

For the special case of equal numbers of each kind of gem, v = N/3,
where N = total number of gems in one necklace (and 3 kinds of gems).

1. prove this for the special case.
2. find, with proof, value of v in the general case (with m kinds of
gems not necessarily equal in number).

some clarifications:
1. the necklace is circular i.e. its a simple closed loop. so given
two necklaces RGB and RBG,
the second can be rotated wrt first to give three orientations (but
this small example
is unusual because the number of matches is same in all 3 orientations):

RGB
RBG 1 matches

RGB
GRB 1 matches

RGB
BGR 1 matches

so v = 1

2. "there is at least one orientation where the number of matches is
at least v"
label the orientations from 1 to N. denote the number of matches for
orientation i as m[i].
then " there exists an i such that m[i] >= v" is the more formal way
of saying this.


-Vaibhav.
------------------
Well, indeed an interesting puzzle. Intially for a few minutes I thought whether it can be proved by contradiction or not. I tried to see whether I am able to hit a contradiction by imagining that "v is always less than N/3". Within a few minutes I realized that this is not going to work. As I remembered the lessons from Prof Sundar Vishvanathan , I thought of trying to prove it by induction. Prof Sundar always used to say that most of the proofs can be given by the principle of mathematical induction. This time I did not bank too much on this options as I learnt it from my earlier experience as I mentioned in my previous post. The solution of this proof also along the line which was taught to me by Prof Sundar.

The proof here makes use of the fact that if expected value of some random variable is a then there exist a possibility where the random variables has a values at least a.

Let us assume that first necklace is fixed and the second necklace is rotated with respect to the first one. Let us define a random variable X such that
X_i = 1 ( if ith gem of first necklace matches with the second one )
X_i = 0 Otherwise.

The ordering in the second necklace can be anything so assuming a uniform distribution there.
Calculating the expected value,
E(X_i) = Pr(X_i).X_i = (Number of gems having the same colour as ith gem/Total number of gems)
For 3 different kind of gems
E(X) = Sum(i=1 to N) ( E(X_i) ) = R^2/N + B^2 /N + G^2/N.

For the special case where R = B = G = N/3 we will have
E(X) = N/3. As the expected value is N/3 we can say that there is at least one configuration of second necklace which would make the number of matching gems at least N/3.

When there are m kinds of gems, not necessarily equal in number, let C[i] denote the number of gems of the same kind as i, where i varies from 1 to m.
Therefore, for general case the expected value is
E(X) = Sum (i = 1 to n ) ( C[i]^2/N )

Well, a nice puzzle indeed. As a closing remark, I have the solutions to the puzzle that I mentioned in my previous post. It will require some figures to be embedded to explain the solution in a lucid way. I will post it soon as I get the time.

Necklace Theorem

Hi all,
As mentioned in my last post, after lunch talks can be very fruitful at times. Describing a yet another fruitful chat with my friend Sambuddha Roy.

The other day he gave me an interesting problem to think about, which is formerly known as, as he told me, necklace theorem. Two thieves have stolen queen's very precious necklace. There are three kinds of gems in the necklace called R, G and B. All are even. The problem is to divide the necklace in such a way that both the thieves get equal amount of gems of each kind. The necklace can have any interleaving of the gems. ( e.g. RRGBGGRBBBG..... ) Prove that it is always sufficient to divide the necklace in equal share by at most 3 cuts.

The proof makes use of Ham Sandwich Theorem. For brevity, I will quote it as HST now on. HST for 2-dimension says that given any two point sets in a plane, there always exist a line which will cut both these point sets simultaneously into half. To say it more formally, call the point sets R and B. Then one side of line will contain at most |R|/2 points and at most |B|/2 points. The same constraints will be followed on the other side too.

If there is only 1 point set R. For a given direction we can always have a line which will divide R in two. The proof is based on intermediate value theorem. It says that for a continuous function if f(x1) = 0 and f(x2)=1 then there exist a z \in (x1,x2) such that f(z) = 1/2.

Now that we have two point sets. What we can do is we get a line for point set R. Now we evaluate how this line L behaves with respect to B. Let us define diff(L) = number of blue gems on the left of L - number of blue gems on the right of L. For initial line L, let the value of diff(L) be b. What we can do is rotate this line a bit. We know that for any given direction, we have a corresponding line L which will divide R equally. We will again evaluate wrt B. We keep on doing this until we have rotated the line for 180 degree. At this point value of diff(L) would be -b. From intermediate value theorem, we can state that there will be a line where diff(L) will be 0.

How about, Ham Sandwich theorem in 3-dimension?? Well, my friend has given me the proof as an exercise. The statement is that given 3 point sets R, G, B in R^3 ( or 3-dim space ) there always exist a plane which will divide all 3 point sets simultaneously into equal portion.

Now, we need to reduce Necklace Theorem to HST in 3D. Starting from left to right, assign every gem an index i. Plot a parametric curve ( t, t^2, t^3 ) using these indices. HST assures us that we will have a plane ax+by+cz+d=0 which will divide R, G, B equally. This plane will divide the parametric curve at , at most 3 points as at + bt^2 + ct^3 + d = 0 will have at most 3 roots. Now, it is easy to map these 3 intersection points on the curve to 3 cuts on the necklace.

Phew!!! It never occurred to me that this proof will use such weird things. Induction based method was too tempting for me to let me think in some different direction. But the story is not over yet. The proof given above is not constructive. So if we were to find an algorithm to find these 3 cuts we might have to explore all possibilities taking O(n^3) time. So another exercise would be to try to find more efficient algorithm to find these cuts.

The generalization of HST is that given k point sets in R^k there would be always be a hyperplane which would cut all these k point sets simultaneously into equal portion. Yet another generalization one can think of is that, what if there are more thieves??? Given q number of thieves and k kind of gems, what would be the upper bound on the number of cuts required?? The answer is due to dold's theorem ( Neither sambuddha nor I have read the proof ). It say that for such situation at most k(q-1) cuts would be necessary.

What if there are 3-point sets in two dimension?? Definitely a line would not suffice. An exercise would be to prove that two rays originating from an apex would be sufficient. Give an algorithm for finding them out.

Two more puzzles are :
1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.

2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.

That's enough to tease our brain for a while :D.

Sudoku Solver

It is very unlikely for me to post twice in a day, yet I am back again. I had a little idle time at my disposal so I thought to put it to some use.

A couple of months back I read in Times of India about world Sudoku championship which was to happen in March 2007. In addition to the day to day sudoku puzzles they included certain variation of the puzzle too, to encourage readers to take part as well as to stimulate their brain :D.

Sudoku took over my mind during those days and I was completely engrossed in reading about Sudoku as well as solving them at websudoku . It occurred to me why not write a program to solving the puzzle? So I took up the task and was ready with a small Sudoku Solver .

Of course, for certain inputs it does not give the solution. I pondered over the completeness and soundness issues of the initial sudoku board. I don't know whether it is appropriate to use these terms which are often used and associated with algorithms. Let me define it this way. Completeness means that the initial information given in the board should be sufficient to solve the puzzle by using only inferences ( No guessing game/No coin tossing/ No breaking tie). In other words, there must exist at most one solution that can be derived from the initial configuration of the board. Soundness means that the information should not be conflicting, or say, at least one solution exist that can be derived from the initial information. I discussed the matter with my mathematics teacher Mr Motilal Panigrahi at GCET .

We could not arrive at any definitive proofs or conditions to ensure the soundness and completeness, but it was nice to chat with him over these things years after I left the college.

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.

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?)
-----------------------------------------

List of NP-Complete Problems

I was just wondering whether the problem that i am stuck up with have any resemblence to any of the NP-Complete problems. The problem that i am encountered with is so close to some of them, however, the difference is, placing one cut in the circuit graph changes the weight of the edges. So unlike some of the NP-Complete problems, I am facing a dynamic problem.

Here goes the link where I found out list of NP complete problem. I dont know whether this is an exhaustive listing or not.

http://www.nada.kth.se/~viggo/problemlist/compendium.html