close
- A person has some candies that are of different weight and wants to divide them evenly between 3 children, so that they don't get jealous at each other. He wants to know how bad the fairest distribution is, i.e. what is the minimum difference in the candies weight, of the kid getting the candies of the most total weight and the kid getting the least. For example, assume that he gives the three children candies of weight a>=b>=c, respectlively. The badness of this distribution is a-c. Try your best to solve this problem and analyze the time efficiency of your algorithm.
- Let x1, x2, ..., xn be a sequence of real numbers ( not necessarily positive ) . Design an algorithm to find a subsequence xi, x(i+1), ..., xj ( of consecutive elements ) such that the product of the numbers in it is maximum over all subsequences of consecutive elements. The product of the empty subsequence is defined as 1.
- Give an algorithm to solve the following version of 0/1 knapsack problem. There are n items with different sizes and values, and each item is unlimited supplied. The size of knapsack is K. We are interested in maximizing the total value, subject to the constraint that there is enough room for the chosen items in the knapsack.
- Let T be an undirected tree. The distance between two vertices in T is the length of the path connecting these two vertices ( neighbors have distance 1 ). The diameter of T is the maximal distance over all pairs of vertices. Design an algorithm to find the diameter of the given tree. Assume that T is given in the adjacency list representation.
- Give asymptotic tight bounds for T(n) in each of the following problems. Assume that T(n) is constant for n<=2.
- T(n) = T(n/2) + n^(1/2)
- T(n) = 2T(n/2) + (lgn)^2
- T(n) = 2T(n/4) + n^(1/2)
- T(n) = T(pn) + T(qn) + O(n), p<1, q<1, and p+q<1
全站熱搜
留言列表
