CSCI 3110 Design and Analysis of Algorithms I - Assignment 3

• 作业标题：CSCI 3110 - Assignment 3
• 课程名称：Dalhouse University CSCI 3110 Design and Analysis of Algorithms I
• 完成周期：2天

Instructions:

1. Before starting to work on the assignment, make sure that you have read and understood policies regarding the assignments of this course, especially the policy regarding collaboration. https://dal.brightspace.com/d2l/le/content/230447/Home?
   itemIdentifier=D2L.LE.Content.ContentObject.ModuleCO-3221550

2. Submit a PDF file with your assignment solutions via Brightspace. If you have not
   used Brightspace for assignment submission before, you may find the the following
   documentation for Brightspace useful: https://documentation.brightspace.com/
   EN/le/assignments/learner/submit_assignments.htm

3. If you submit a joint assignment, only one person in the study group should make the
   submission. At the beginning of the assignment, clearly write down the names and
   student IDs of the up to three group members.

4. We encourage you to typeset your solutions using LaTeX. However, you are free to
   use other software or submit scanned handwritten assignments as long as they are
   legible. We have the right to take marks off for illegible answers.

5. You may submit as many times as needed before the end of the grace period. A
   good strategy is to create an initial submission days in advance after you solve some
   problems, and make updates later.

1. 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 sufficient details in your solutions. For example, to show lim
   n→∞
   lg n
   n = 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-Θ 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) + Θ(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 find. 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 satisfies 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 finds all the candidate hotels in O(n lg n) time using divide-and-conquer, listed in
   increasing distance to the beach

。。。