Questions:

1.  [8 marks] Prove the following two identities using the limit method. Recall that lg n = log2 n.

(i)  [4 marks] n/ lg n = o(n/ lg lg n). (ii)  [4 marks] ^n lg n = o(n/ lg n).

Give sucient details in your solutions.  For example, to show ln   = 0, give the steps of applying l’Hopital’s Rule.

2.  [12 marks] For each of the following recurrences, use the “master theorem” and give the solution using big-Q notation.  Explain your reasoning.  If the “master theorem” does not apply to a recurrence, show your reasoning, but you need not give a solution.

You are required to use the version of the master theorem taught in class (also posted in the online notes), which is the same as the master theorem in the 4th edition of the textbook.  Do NOT use the master theorem in the third edition of the textbook, which covers fewer cases.

(a) T (n) = 8T (n/2) + n2

(b) T (n) = 16T (n/2) + (n/ lg n)4

(c) T (n) = 8T (n/3) + Q(n2 )

(d) T (n) = 3T (⌈n/3⌉) + n lg n

3.  [10 marks] A problem database people are often interested in is the following: Consider a set of hotels of acceptable ratings. For each hotel, we know how far away it is from the beach and how much a room costs a night.   Ideally, we want to book a room in the cheapest hotel that is closest to the beach, but probably such a hotel will be impossible to ind. Therefore, we are willing to compromise. Whether we are willing to trade distance from the beach for price depends very much on our personal preferences, but we would like to avoid booking in a hotel A if there exists a hotel B that is both cheaper and closer to the beach than hotel A.

For a hotel H, let dH  be its distance from the beach and dH  its price. Then, according to the discussion above, we consider a hotel A a candidate for booking a room if there is no hotel B that satisies the following conditions:

(a) dB  ≤ dA ,

(b) pB  ≤ pA , and

(c) at least one of these two inequalities is strict.

Given a set S of n hotels, your goal in this assignment is to develop an algorithm that inds all the candidate hotels in O(n lg n) time using divide-and-conquer, listed in increasing distance to the beach.

You are not allowed to using any sorting algorithms in your solution. You can make the following assumptions about the input and the output:

Input:  An array S[1..n] of pairs of integers (d, p), in which S[i].d stores the distance of hotel i to the beach and S[i].p stores the price of hotel i. Note that two hotels may have the same distances and/or prices.