Management > QUESTIONS & ANSWERS > CSE 551 Graded Quiz 2 Solutions/Rationale (All)

CSE 551 Graded Quiz 2 Solutions/Rationale

Document Content and Description Below

Question 1 In the proof of optimality for the greedy algorithm in interval scheduling, we picked r to be the maximum for which the greedy and optimal solutions were identical choices. Why was this ... important in the overall proof? Correct Response Because a contradiction about r is reached from a substitution-type argument (substituting a job from optimal into the greedy schedule). Rationale We first assume toward a contradiction that greedy is not optimal. Recall that the greedy solution and the optimal solution agree up to job jr. Greedy then picks a job whose finish time is earlier than the next job optimal picks. If we have optimal pick the same job as greedy at time step r + 1, then the number of jobs selected by optimal remains unchanged, thus the optimal algorithm still produces an optimal schedule. Now optimal agrees with greedy through time step r + 1, which is a contradiction, since we defined r as the largest time step where optimal and greedy agree. Therefore, greedy is optimal. Question 2 What is the best asymptotic run-time of the greedy algorithm for Interval Partitioning, if there are n intervals? Correct Response O(nlogn(n)) [Show More]

Last updated: 3 years ago

Preview 1 out of 5 pages

Buy Now

Instant download

We Accept: