Save maximum prisoners

There are 64 prisoners who are to be executed the same day. The executioner didn't want to waste his whole day getting the electric chair set up and preferred to shoot them all. However, he thought it would be unfair to deviate from the procedure and just shoot them without giving them a second chance. So he thought of a plan.
He informed all the 64 prisoners that they would be made to stand in a line in such a way that each of the prisoners could view the heads of all the prisoners standing in front of him, and then the executioner would put one hat on each prisoner's head which would be either white or black in colour (The prisoners would not be able to see the colour of the hat on top of their own heads). Then each of the prisoners would be given a chance to shout out the colour of his own hat starting from the last prisoner (The prisoner who can see all the hats except his own). Whoever shouts out the wrong colour would be shot and the others let go.
The prisoners have quite a good unity and they want most of them to be saved. You have to help them device a strategy which if they follow would make the probability of saving all the prisoners highest!

Solutution to Random Pointer

Link to the Problem

Vandana gave a simple solution which was correct but it needed O(n) extra space and Anonymous got rid if that extra space and gave us an O(n) solution using constant space.
My solution is same as Anonymous'! Here it goes :

As Anonymous pointed out, the random pointer is a little too weak, so the idea is to use the next pointer to maintain correspondences between the old and the new (copy) list before assigning the random pointers for the new list!
Let the old list be
O1 --> O2 --> O3 --> O4 --> NULL
create new nodes and insert them in between the old nodes with old list's next pointing to the corresponding new node and the new node's next pointing to old's original next. So we get something like,
O1 --> N1 --> O2 --> N2 --> O3 --> N3 --> O4 --> N4 --> NULL
Also while creating the new nodes, copy the corresponding old node's data to the new node's data.
Now traverse through this list and assign current node's random pointer's next to the next node's random pointer.
Thus if O1->random was pointing to O3, then we get N1->random = O1->random->next = O3->next = N3;
Skip the alternate (new) nodes while doing this. When this traversal is done through the whole list, we have the new nodes having the exact structure as the old nodes. Hence, the only thing now left to be done is detaching the two lists, which can be easily done by storing old->next to a temporary pointer and then assigning old's next to old's next's next and similarly for the new nodes. Hence we get two lists
O1 --> O2 --> O3 --> O4 --> NULL and
N1 --> N2 --> N3 --> N4 --> NULL
with the random pointers also properly assigned!

Random Pointer

We've had enough of logic puzzles! Here goes a data structures problem:

You have a linked list of nodes with the following fields:

struct Node {
int data;
Node * next;
Node * random;
}

The random pointer here can point to any node in the list including itself.

Now given a pointer to such a list, your task is to create a similar copy! The structure of the links should remain the same.

To clarify, all the nodes in the list are linked through the next pointer;
Mind you, You may or may not reach all the nodes if you try to access random pointers.

Link to the Solution

Solution to Blue eyes

Link to the Problem

Manikandan's solution was almost correct and Yash correctly modified it!
Here's my solution:

In such type of problems always try decreasing the number of parameters (i.e. Use induction).

If there was only 1 blue eyed person, he would have left at the end of the first day itself as he doesn't see any other blue eyed person there (and he knows that there is at least one blue eyed person).

If there were 2 blue eyed people, then the first would see one other blue eyed person on the first day and vice versa and hence both won't leave on the first day (as they can't determine their own eye colour). However, on the second day they know that there are more than one blue eyed persons (if there was only one blue eyed person then he would have left the first day itself). And since the blue eyed persons see only one other blue eyed person, each of them themselves is the other blue eyed person creating confusion on the first day. So the two blue eyed persons know that their eye colour is blue on the second day and hence would leave at the end of that day.

Similarly, if there were 3 blue eyed people, these three blue eyed people would be confused for the first two days as they see 2 other blue eyed people not leaving the island, however on the third day they would know there is one more blue eyed person and it could be only be he himself (as they know that if there were only 2 blue eyed people, they would have left at the end of the 2nd day by above argument). So these three blue eyed people would leave at the end of the 3rd day.

By similar argument we can prove that if there are N blue eyed people, they would be confused till N-1 days but on the Nth day they would all come to know that their eye colour is blue! And hence all the N blue eyed people leave at the end of the Nth day.

Hence in this case all the 100 Blue eyed people leave on the 100th day and no one else leaves!

Blue Eyes

Two hundred and one perfect logicians with assorted eye colours are stuck in a deserted island. Of these, 100 have blue eyes, 100 have brown eyes and one has green eyes which however they don't know. These people can see everyone else (and hence know their eye colours) but they don't know their own eye colour (they don't even know the all colours present there)! Also, they cannot communicate with each other by any means. Every midnight a ship comes to the island and takes away only those people who know their own eye colour for sure at that point of time. The Guru (who happens to have green eyes) is allowed to speak one sentence to the islanders (at noon) after which no one speaks (communicates) and he says, "I see blue eyes!"
Now the question is: Who all leave the island and at what time?

Link to the Solution

Solution to The emperor's party

Link to the Problem

Nice try by Mythalez, Vivek and Ankit! I had never thought of such a solution!
Here goes my Solution:
2^11 = 2048 which is greater than 2009. Hence, all numbers from 1 to 2009 can be represented
using 11 bits! Now represent each bottle number in 11 bit binary format and list them row wise. Each row now has a 11 bit number representing a bottle number. Let each column be a single bit. So, each column would contain either a 0 or a 1 corresponding to each bottle(row). Keep one slave per column and make the slave drink from all the bottles which have a 1 in that column! Hence, you get the poisoned bottle using the combination of slaves who die (write 1's for the slaves who die and 0's for the slaves who don't and the binary number hence formed gives the bottle number corresponding to the poisoned bottle).
e.g.
Let's say the third bottle was poisoned.

1   2   3   4   5   6   7   8   9   10   11     - Slave numbers

0   0   0   0   0   0   0   0   0    0    1     - 1st bottle
0   0   0   0   0   0   0   0   0    1    0     - 2nd bottle
0   0   0   0   0   0   0   0   0    1    1     - 3rd bottle
0   0   0   0   0   0   0   0   1    0    0     - 4th bottle
.
.
.
.

Now the slaves from 1 to 9 wont die and 10th and 11th slave would die after 10 to 15 hrs. From this we can decode the bottle number by writing nine 0s followed by two 1s i.e. 00000000011 which is 3. Hence, we conclude that the third bottle is poisoned!

Here time of death was included just to introduce some confusion while solving the problem. However, if Vivek's time window concept is used (which seems reasonable) we can achieve this using ceil(11/3) slaves i.e. 4 slaves!!!!

The emperor's party

You are an emperor of a huge kingdom and are conducting a party tomorrow in which you have invited very important guests. You had ordered for 2009 bottles of expensive wine for the celebration. However, you come to know that the wine in one of these bottles has been poisoned (but you don't know which one) and that this poison exhibits no symptoms until death. Also, death occurs within ten to fifteen hours after consuming even the minutest amount of this poison. Since the guests are very important you cannot risk serving them poisoned wine. You have slaves at your disposal who could be made to drink the wine in order to detect the poisoned bottle. Since you don't want to disturb the other important tasks the slaves are carrying out, you want to do this with the least number of slaves possible. How would you go about doing this so that you could have a smooth celebration tomorrow and what is the minimum number of slaves you would have to use?

Link to the Solution