” 写作CSCI 3110程序、 辅导c++，Java，Python编程语言Dalhousie UniversityCSCI 3110 Design and Analysis of Algorithms IFall 2020Assignment 7Distributed 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 understoodpolicies regarding the assignments of this course, especially the policy regardingcollaboration. https://web.cs.dal.ca/~mhe/csci3110/assignments.htm2. Submit a PDF file With your assignment solutions via Brightspace. If you have notused Brightspace for assignment submission before, you may find the the followingdocumentation for Brightspace useful: httpss://documentation.brightspace.com/EN/le/assignments/learner/submit_assignments.htm3. If you submit a joint assignment, only one person in the study group should make thesubmission. At the beginning of the assignment, clearly write down the names andstudent IDs of the up to three group members.4. We encourage you to typeset your solutions using LaTeX. However, you are free touse other software or submit scanned handwritten assignments as long as they arelegible. 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. Agood strategy is to create an initial submission days in advance after you solve someproblems, 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 asdefined 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 writedown your solution (as a fully parenthesized expression), without showing intermediatesteps or arguing about correctness.2. [10 marks] Suppose you are scheduling jobs in a factory to maximize profit. In the ithweek, you can choose Not to do any job, do an easy job with profit ei 0, or do a hardjob with profit hi 0. In order to do a hard job, you must use all your manpower togather resources for it in the previous week. That is, if you wish to do a hard job inweek i, then you must Choose not to do any job in week i 1. If you do an easy jobin 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 thatthe total profit is maximized.A greedy algorithm is to compare h2 with e1+e2. If h2 is larger, then do not do any jobin week 1 and do the hard job in week 2. Otherwise, do easy jobs in both week 1 andweek 2. Then consider h4 and Use the same strategy, and so on. This will schedule jobsfor all the weeks if n is an even number. If n is an odd number, then after schedulingall 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 anoptimal solution. Argue Carefully why it is a counterexample.3. [10 marks] Design an efficient dynamic programming algorithm to solve the problemin Question 2 optimally. In this question, you are only required to report the value ofthe 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 profitof the hard job for week i. Your output is the value of the maximum profit.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
