Page 1 of 1
4. (20 points) For the following problem, give an optimal greedy strategy. Prove that it is optimal by any technique, gi
Posted: Sun May 15, 2022 12:43 pm
by answerhappygod
- 4 20 Points For The Following Problem Give An Optimal Greedy Strategy Prove That It Is Optimal By Any Technique Gi 1 (98.2 KiB) Viewed 87 times
4. (20 points) For the following problem, give an optimal greedy strategy. Prove that it is optimal by any technique, give an algorithm implementing it, and give a time analysis for your algorithm. You have n real numbers x1 < x2 < x3 <...< xn and an integer k. You want to find k intervals [Si, Fi] so that they cover the numbers (each xj is in one of the intervals, i.e. Si sxj s Fi) in a way that minimizes the total length of intervals used, i.e., minimizes P 1sisk Fi -Si. For example if k = 3 and the numbers are 1, 3, 7, 12, 19, 23, 27, we could cover them with [1, 7], [12, 12], [19, 27] for a total length of 6 + 0 + 8 = 14. a.