6.Consider the following Binary Search Tree

 10 / \ 5 20 / / \ 4 15 30 / 11 

If we randomly search one of the keys present in above BST, what would be the expected number of comparisons? Note that you are ONLY searching for things that are in the tree. When you find something you are looking for, you stop.

a)2.75

b)2.57

c)2.25

3.Algorithms which have complexity 2ⁿ are considered intractable. Which of the following problems likely have only intractable solutions?

a)Towers of Hanoi

b)Traveling Salesperson problem: Given a collection of cities on a map, a salesman must make a tour of the cities, visiting each once, and returning to the city from which he started in the shortest amount of mileage.

c)The input is a positive integer C and n objects whose sizes are positive integers s1, s2,..., sn. Among all subsets of objects with sum at most C, what is the largest subset sum?

d)Bin Packing: Suppose we have unlimited number of bins each of unit capacity and n objects with sizes s1, s2,..., sn where the sizes si(i = 1,..., n) are rational numbers in the range 0 < si <=1. Determine the smallest number of bins into which the objects can be packed and find an optimal packing.