I have pending post from few months. It is on application of decision trees to analyze algorithms.
The puzzle is given below,
"We are provided a two pan fair balance and N identically looking coins, out of which only one coin may be defective. How can we trace which coin, if any, is odd one, and also determine whether it is lighter or heavier in minimum number of trials in the worst case?"
Try to solve the puzzle on your own, and then read my systematic solution on the following link
"We are provided a two pan fair balance and N identically looking coins, out of which only one coin may be defective. How can we trace which coin, if any, is odd one, and also determine whether it is lighter or heavier in minimum number of trials in the worst case?"
Try to solve the puzzle on your own, and then read my systematic solution on the following link
There are other applications of decision trees, like analyzing comparison based sorting routines. We may think that comparison is cheap operation, however, in reality we deal with large objects than simple integers, where comparison is costly operation. We need decision trees to analyze lower bounds of comparison sorting.
There are other advantages of trees like solving game of Nim, probability problems, etc...
Again the link is for my reference. Any comments post on Geeksforgeeks.org site.
