I have attached the question
Analysis of Algorithms COMP 2080 Department of Computer Science University of Manitoba Assignment 6 Solutions: Greedy Algorithms 1. Θ(n log n) The for-loop (Lines 2–3) iterates n times, with each call to insert requiring Θ(log i) time, where i = 1 . . . n, resulting in Θ(n log n) time for the for-loop. Each call to extractMin (Line 4) requires Θ(log n) time. Lines 5–6 requires O(1) time. The while loop (Lines 7–11) iterates at most n times, with each extractMax requiring Θ(log i) time, where i = log n . . . 1. The remaining operations in the loop (Lines 9–11) require O(1) time per iteration. Thus, the while loop takes O(n log n) time, resulting in a total time of O(n log n) for Algorithm 1. Recall from COMP 2140 that an unordered array of size n can be heapified in Θ(n) time. Thus, the running time of the for-loop could be reduced from Θ(n log n) time to Θ(n), but the while loop’s time would remain Θ(n log n). 2. Among the remaining activities from A, Algorithm 1 selects the activity [sj , fj ] with the earliest finish time. If this activity does not conflict with the set of selected activities S, then [sj , fj ] is added to the partial solution S, otherwise [sj , fj ] is discarded. Thus, the greedy strategy is: select the activity with the earliest finish time that does not conflict with the set of selected activities. 3. There can be at most one element in S′ that conflicts with [s1, f1]. Suppose otherwise; let [sa, fa] and [sb, fb] denote any two elements in S ′ that conflict with [s1, f1]. By definition of [s1, f1], for all [si, fi] ∈ A, f1 ≤ fi. In particular, f1 ≤ fa and f1 ≤ fb. Since [sa, fa] and [sb, fb] conflict with [s1, f1], therefore sa ≤ f1 and sb ≤ f1. Consequently, [sa, fa] and [sb, fb] both overlap f1, implying that [sa, fa] and [sb, fb] conflict. Since [sa, fa] and [sb, fb] are both in S ′, they can’t conflict because S′ is an optimal solution, deriving a contradiction. Since S′ and S are both optimal, S′ must contain at least one activity that conflicts with [s1, f1]; otherwise, [s1, f1] could be added to S ′, contradicting the fact that S′ is optimal. Therefore, S′ contains exactly one activity that conflicts with S. 4. Since at most one element in S′ conflicts with [s1, f1], replace that element with [s1, f1] to obtain a solution S such that |S| = |S′| and S contains [s1, f1]. Since S′ is optimal and |S| = |S′|, it follows that S is also optimal. If [s2, f2] is the element in S ′ that conflicts with [s1, f1], then S = (S ′ ∪ {[s1, f1]}) \ {[s2, f2]}. 5. This is the greedy-choice property. 6. Let S∗ = S \ {[s1, f1]}. That is, remove [s1, f1] from S to obtain S∗. 7. This is the optimal substructure property. 8. Consider a greedy strategy that chooses from the remaining activities the one with the earliest start time. Let A = {[1, 5], [2, 3], [4, 5]}. This greedy algorithm selects the subset S = {[1, 5]}, while the optimal solution (selected by Algorithm 1) is S′ = {[2, 3], [4, 5]}. 9. Let A = {(1, 5, 3), (2, 3, 1), (4, 5, 1)}. Algorithm 1 selects S = {(2, 3, 1), (4, 5, 1)}, for which the weighted benefit is 2. The optimal solution is S′ = {(1, 5, 3)}, for which the weighted benefit is 3. Winter 2021, Assignment 6 Solutions page 1 This study source was downloaded by 100000850015285 from CourseHero.com on 07-18-2022 23:51:44 GMT -05:00 https://www.coursehero.com/file/87403432/a6solpdf/ Powered by TCPDF (www.tcpdf.org) https://www.coursehero.com/file/87403432/a6solpdf/ http://www.tcpdf.org