CSCI 3110 Design and Analysis of Algorithms I - Assignment 5

• 作业标题：CSCI 3110 - Assignment 5
• 课程名称：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] Suppose that we need to compute the matrix-chain product A1 × A2 × A3 ×
   A4 × A5 × A6. The dimensions of these matrices are given in the dimension array p as
   defined in class, and the content of p is 5, 20, 4, 3, 10, 5, 8.
   Final an optimal parenthesization of this matrix-chain product. You can simply write
   down your solution (as a fully parenthesized expression), without showing intermediate
   steps or arguing about correctness

2. [10 marks] Suppose you are scheduling jobs in a factory to maximize profit. In the ith
   week, you can choose not to do any job, do an easy job with profit ei ≥ 0, or do a hard
   job with profit hi ≥ 0. In order to do a hard job, you must use all your manpower to
   gather resources for it in the previous week. That is, if you wish to do a hard job in
   week i, then you must choose not to do any job in week i − 1 (this also means you
   cannot do a hard job in the first week). If you do an easy job in week i, then you are
   free to do any type of job (or no job at all) in week i − 1.
   Your task is to come up with a schedule of the jobs to be done in each week (i.e.,
   choose among the easy job for this week, the hard job for this week, or no job), so that
   the total profit is maximized.
   A greedy algorithm is to compare h2 with e1 +e2. If h2 is larger, then do not do any job
   in week 1 and do the hard job in week 2. Otherwise, do easy jobs in both week 1 and
   week 2. Then consider h4 and use the same strategy, and so on. This will schedule jobs
   for all the weeks if n is an even number. If n is an odd number, then after scheduling
   all the weeks up to and including week n − 1, do an easy job in week n.
   Give a counterexample to show that this greedy algorithm will not always yield an
   optimal solution. Argue carefully why it is a counterexample.

3. [10 marks] Design an efficient dynamic programming algorithm to solve the problem
   in Question 2 optimally. In this question, you are only required to report the value of
   the maximum profit.
   For this question, assume that the input contains two arrays: e[1..n], in which e[i]
   stores the profit of the easy job for week i, and h[1..n], in which h[i] stores the profit
   of the hard job for week i. Your output is the value of the maximum profit

。。。