COMPSCI 311 Midterm: CMPSCI 311 UMass Amherst Solutions 4
31 Jan 2019
School
Department
Course
Professor
Document Summary
Note: latex template courtesy of uc berkeley eecs dept. You make work in groups, but you must individually write your solutions yourself. This assignment is due by 8:00pm on 11/4/2016 in moodle. You may submit a scanned handwritten document, but a typed submission is preferred: dynamic programming short answer (a) scheduling. The solution here is based on a reduction to subset sum, which we already saw how i=1 ti and observe that for any set s {1, . , n} equivalent to trying to maximize f1, provided that we do not exceed t /2 (since if we stay below. T /2, the term t f1 will be the maximum). to solve with dynamic programming. Let t =pn we have f1 = pi s ti and f2 = t f1. We are trying to minimize max{f1, t f1}, which is. Thus, we want to nd a subset s {1, .
