(Closed Unit Intervals Covering Points) CLR problem 16.2-5 in the book \" Introd
ID: 3629445 • Letter: #
Question
(Closed Unit Intervals Covering Points) CLR problem 16.2-5 in the book " Introduction To Algorithms, 3rd Edition by Thomas H. Cormen" : Describe an efficient algorithm that, given a set {x1, x2, . . . ,xn} of n points on the real line, determines the smallest set of closed unit-length intervals that contains all of the given points. Prove that your algorithm is correct. Note that the word “efficient” means that the complexity is no worse than polynomial-time. Be sure that your algorithm is clearly written in readable and understandable pseudocode. (Closed Unit Intervals Covering Points) (Closed Unit Intervals Covering Points) CLR problem 16.2-5 in the book " Introduction To Algorithms, 3rd Edition by Thomas H. Cormen" : Describe an efficient algorithm that, given a set {x1, x2, . . . ,xn} of n points on the real line, determines the smallest set of closed unit-length intervals that contains all of the given points. Prove that your algorithm is correct. Note that the word “efficient” means that the complexity is no worse than polynomial-time. Be sure that your algorithm is clearly written in readable and understandable pseudocode.Explanation / Answer
Algorithm smallest-set (n)
1 m := 1;
2 B[1]:= A[1];
3 for j := 1 to n do
4 if (A[j] > B[m] +1)
5 m: = m+1; // Add a new interval
6 B[m]:= A[j];
7 else
8 A[j] is in [B[m], B[m] +1]
Theorem: smallest-set returns the minimal number of unit intervals that cover
A[1], A[2], …, A[n].
Lemma: None of the intervals obtained by smallest-set can move right by any distance, otherwise some points won’t be covered.
Proof: Induction on m
Base case: m = 1 and B[1] = A[1]. If [B[1], B[1]+1] moves right, then A[1] cannot be covered.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.