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.