600.463 Introduction to Algorithms / Algorithms I Fall 2016
Homework #6 Due: October 18, 2016, 1:30pm
Remember: you may work in groups of up to three people, but must write up your solution entirely
on your own. Colla
...
600.463 Introduction to Algorithms / Algorithms I Fall 2016
Homework #6 Due: October 18, 2016, 1:30pm
Remember: you may work in groups of up to three people, but must write up your solution entirely
on your own. Collaboration is limited to discussing the problems { you may not look at, compare,
reuse, etc. any text from anyone else in the class. Please include your list of collaborators on the
first page of your submission. You may use the internet to look up formulas, definitions, etc., but
may not simply look up the answers online.
Please include proofs with all of your answers, unless stated otherwise.
1 Completing Homeworks (50 points)
Suppose (hypothetically) that you were taking a class, possibly called \Algorithms", in which the
homeworks were extremely difficult. After enough complaining, the professor decided to make the
following changes. There are two homework assignments each week rather than one, an \easy"
assignment and a \hard" assignment. The hard assignment is worth more points, but it is in fact
so difficult that you can only complete it if you’re completely rested and prepared, meaning that
you cannot have done either of the assignments the week before.
More formally, let n be the number of weeks in the class, let hi be the number of points for
the hard assignment in week i, and let ei be the number of points for the easy assignment in week
i. Note that hi does not have to be equal to hj for i 6= j (although it might be), and similarly
with ei and ej. Assume that you know all of these values in advance. Then the goal is compute
a schedule which in each week tells you whether to do nothing, the easy assignment, or the hard
assignment and maximizes the total number of points, subject to the restriction that if you do a
hard assignment in week i you cannot have done any assignment in week i − 1.
(a) (15 points) One obvious approach would be to choose a hard assignment in week i if we get
more points than if we completed the easy assignments for weeks i and i − 1. This would be
the following algorithm:
i = 1
whil e (i < n) f
i f (hi+1 ≥ ei+1 + ei) f
choose no assignment in week i ,
choose the hard assignment in week i + 1 ,
i = i + 2
g
e l s e f
choose the easy assignment in week i ,
i = i + 1
g
g
Give an instance in which this algorithm does not return the optimal solution. Also say what
the optimal solution is (and its value) and what the algorithm finds instead.
1
[Show More]