Computer Science > QUESTIONS & ANSWERS > Johns Hopkins UniversityEN 600.463hw6_solutions-GRADED A+ (All)

Johns Hopkins UniversityEN 600.463hw6_solutions-GRADED A+

Document Content and Description Below

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]

Last updated: 2 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept: