CSE 551 Graded Quiz 2 Solutions
Jamison Weber
June 2019
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
...
CSE 551 Graded Quiz 2 Solutions
Jamison Weber
June 2019
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))
1Rationale
Although the main loop clearly has a time complexity linear on the number of
jobs, the preprocessing step involves sorting the jobs, and the lower bound for
sorting by comparison is, of course, O(nlog(n)).
Question 3
Informally, in the minimizing maximum lateness problem, why does sorting jobs
in ascending order of processing time not allow for a greedy-type approach to
find an optimal solution?
[Show More]
.png)
.png)
.png)
.png)
.png)
