### DECEMBER 2010 – QUESTION NO 25

This particular question is not clear for few readers. So, I am taking it up once again.

25. Which of the following can be the sequence of nodes examined in binary search tree while searching for key 88 ?

(A) 90, 40, 65, 50, 88

(B) 90, 110, 80, 85, 88

(C) 190, 60, 90, 85, 88

(D) 65, 140, 80, 70, 88

**Ans:- B**

**Explanation:-**

I am taking the liberty of retaining an explanation given for a similar question from yahoo answers.

**Best Answer:** For a binary search tree, the entire tree is sorted such that for any node, every node to the left is less than the current node value and every node to the right is more than the current node value.

When walking a BST tree, you “zero in” on the value by following the correct nodes down the tree. Ideally you work closer and closer to your answer, kind of like the “guess the number” game where you give “nope, more!” and “nope, less!” hints.

a) 2, 399, 387, 219, 266, 382, 381, 278, 363

This sequence is possible.

b) 935, 278, 347, 621, 299, 392, 358, 363

This sequence is not possible. Since 621 is to the right of 347, every other node under 621 must ALSO be to the right of 347. 299 is not — so this is an impossible walk. Basically, once you pass 347, 299 is swinging too far in the opposite direction.

c) 924, 220, 911, 244, 898, 258, 362, 363

This sequence is possible.

d) 925, 202, 911, 240, 912, 245, 363

Not possible — 240 is to the left of 911, so every other node must also be less than 911 (but still may be to the right of 240). 912 is not to the left of 911.

e) 2, 252, 401, 398, 330, 344, 397, 363 This sequence is possible. Just barely though — 397 is to the left of 398 but just barely!

I am taking the example b which explains why a particular sequence is not possible. **Since 621 is to the right of 347, every other node under 621 must ALSO be to the right of 347.**

Let us apply the same rule to all the sequences given above for us in the question.

The first sequence is 90,40,65,50,88. Do not consider any particular element as the root. But start analysing the numbers from first. 90 is the first number. 40 is the second one. So, 40 will be to the left of 90, since it is less than 90. Since 40 is to the left of 90, all numbers following 40 also should be to the left of 90, which is true in this sequence. 65,50, and 88 will be to the left of 90. So this sequence is possible.

Let us consider the second sequence which is 90,110,80,85,88. Again 90 is the first number. 110 will be to its right since it is greater than 90. So all the numbers following 110 also should be to the right of 90,but 80,85 and 88 fall to its left. So, this sequence is not possible.

Let us consider the third sequence which is 190,60,90,85,88. So, 190 is the first number. 60 is to its left. So all the other numbers following 60 should be to the left of 190, which is holding good here. 90,85 and 88 will be to the left of 190. So, this sequence is possible.

Let us consider the fourth sequence which is 65,140,80,70,88. 65 is the first number. 140 will be to its right. All the numbers following 140 should be to the right of 65 which is true. 80,70 and 88 will be to the right of 65 as well.

So, the correct answer is option B and not C.

## JUNE 2014 – PAPER III Q.NO 62

62. Consider the fractional knapsack instance n=4, (p1,p2,p3,p4) = (10,10,12,18)

(w1,w2,w3,w4)=(2,4,6,9) and M=15. The maximum profit is given by,

(Assume p and w denotes profit and weights of objects respectively).

(A)40

(B)38

(C)32

(D)30

**Ans:-B**

**Explanation:-**

Knapsack problem can be solved either using Greedy approach or through Dynamic programming. I am going to be explaining using the former. It has been proved that for the knapsack problem using greedy method we always get the optimal solution provided the objects are arranged in decreasing order of pi/wi. So, before solving the problem, let us arrange all the objects in decreasing order of pi/wi.

Capacity of the knapsack M = 15

Number of objects = 4

Profits(p1,p2,p3,p4)=(10,10,12,18)

Weights(w1,w2,w3,w4)=(2,4,6,9)

To get the solution arrange objects in decreasing order of profit/weights as shown below.

p1/w1=10/2 =5

p2/w2=10/4=2.5

p3/w3=12/6=2

p4/w4=18/9=2

Arrange in decreasing order of pi/wi, we get

Object | Weight | Profit | Pi/wi |
---|---|---|---|

1 | 2 | 10 | 5 |

2 | 4 | 10 | 2.5 |

3 | 6 | 12 | 2 |

4 | 9 | 18 | 2 |

The fractions of the objects selected and the profit we get can be computed as shown below:

Remaining Capacity | Object selected | Weight of the object | Fraction of the object selected |
---|---|---|---|

15 | 1 | 2 | 1 full unit |

15-2=13 | 2 | 4 | 1 full unit |

13-4=9 | 3 | 6 | 1 full unit |

9-6=3 | 4 | 9 | 3/9 or 1/3 fraction of unit |

So, the solution vector will be=(1,1,1,1/3)

Profits=1 X 10 + 1 X 10 + 1 X 12 + 1/3 X 18

Profits=10+10+12+6

Profits=20+18

=**38**

So the correct answer will be 38. The maximum profit is given by **option (B) which is 38**.

__Solve the following problem and see.__

I. Obtain the optimal solution for the knapsack problem given the following: M=40,n=3, (p1,p2,p3)=(30,40,35) and (w1,w2,w3)=(20,25,10).

. The answer for the above problem is **82.5**