- Prove upper and lower bounds on the function
*T(n)*defined by*T(n) = 6T(⌊n/2⌋) + 16T(⌊n/4⌋) + 2n*when^{3}*n ≥ 4*, with*T(1) = T(2) = T(3) = 1*. - Consider the problem of taking a
**sorted**array*A*containing distinct (and not necessarily positive) integers, and determining whether or not there is a position*i*such that*A[i] = i*.- Describe a divide-and-conquer algorithm to solve this problem. Your algorithm should return such a position if it exists, or
`false`otherwise. If*A[i] = i*for several different integers*i*, then you may return any one of them. - Analyze the running time of your algorithm as a function of the number of elements of
*A*.

- Describe a divide-and-conquer algorithm to solve this problem. Your algorithm should return such a position if it exists, or
- King Yéméchan has given his royal mathematician Yséconthé a list of treasures that belong to neighbouring countries. For each treasure, the list specifies
- How much the treasure is worth.
- How easy it would be for Yprantou (the royal thief) to
*acquire*this treasure.

Each treasure can thus be represented by a point in the plane: the

*x*coordinate represents how much the treasure is worth, and the*y*coordinate is the difficulty of stealing that treasure (where a higher*y*coordinate corresponds to a treasure that is easier to steal). Given two such points, we will say that a point*q = (q.x, q.y)***dominates**the point*p = (p.x, p.y)*if*q.x ≥ p.x*and*q.y ≥ p.y*. That is,*q*lies to the right of and above*p*, as illustrated in picture on the left.Clearly, a point*p*that is dominated by a point*q*is of no interest, since*q*is both worth more and easier to steal than*p*. Hence, to help you reach a decision, you only need to worry about locations that correspond to**maximal**points: those that no other point dominates. For instance, in the picture on the right, the points*p*,_{3}*p*are_{4}*p*are maximal, as you can see from the fact that their upper-right quadrants are empty._{6}- Describe an algorithm that takes as input a set
*P*of points, and a point*q*, and returns all points of*P*that*q*does not dominate. - Describe an efficient divide-and-conquer algorithm that takes as input a set
*P*of points, and returns the list of treasures that Yprantou might be asked to steal first (that is, all maximal points of*P*).*Hints*:- Try to divide the problem into two subproblems so that points that are maximal in one of the subproblems are guaranteed to be maximal in
*P*. - When you are combining the solutions to your subproblems, you should choose a point carefully in one subproblem, and then call your algorithm from part (a) exactly once to eliminate maximal points from the other subproblem that are not maximal in
*P*.

- Try to divide the problem into two subproblems so that points that are maximal in one of the subproblems are guaranteed to be maximal in
- Analyze the worst-case running time of your algorithm from (b).

# Tutorial #6 Problems

Leave a reply