代做CSCI 3110程序、代写c++，Java，Python编程语言

日期：2020-11-04 11:23

Dalhousie University

CSCI 3110 — Design and Analysis of Algorithms I

Fall 2020

Assignment 7

Distributed Thursday, October 29 2020.

Due 5:00PM, Thursday, November 5 2020.

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. http://web.cs.dal.ca/~mhe/csci3110/assignments.htm

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.

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, 10, 3, 12, 5, 50, 6.

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. 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.

2