CSCI 3110 Design and Analysis of Algorithms I - Assignment 4

• 作业标题：CSCI 3110 - Assignment 4
• 课程名称：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. [10 marks] Use the recursion-tree method to solve the following recurrence:
   T (n) = 2T (n/2) + n lg n.
   You can assume that T (1) = 1 and that n is a power of 2 for convenience. Show your
   steps and give your solution using big-O notation

2. [10 marks] In class, we learned that for the fractional knapsack problem, the greedy
   strategy of selecting the item with the highest value to weight ratio first will always
   yield an optimal solution.
   Now construct counterexamples for the following two greedy strategies, to show that
   they will not always produce an optimal solution to the fraction knapsack problem.
   In your solution, provide sufficient details to show what you constructed are indeed
   counterexamples.
   (a) [5 marks] Always select the most valuable item first.
   (b) [5 marks] Always select the lightest item first

3. [10 marks] We are given a set I of n (possibly overlapping) intervals and a set N of n
   numbers. Our goal is to compute the smallest subset S of I such that for each number
   in N, there exists at least one interval in S that covers it. The intervals in S are
   allowed to overlap.
   Design a greedy algorithm to solve this problem in O(n2) time or better. When you
   justify the correctness of your algorithm, carefully prove that your greedy strategy
   always gives an optimal solution.

。。。