An interval's weight is defined as the reciprocal of the interval size. For example if an...

 

Transcribed Image Text:

An interval's weight is defined as the reciprocal of the interval size. For example if an interval contains two elements, then its weight is 1/2; and it contains 5 elements, its weight is then 1/5. Given a sorted array A in increasing order and an integer k, the interval [i, j] contains j-i+1 elements, and thus it has a weight 1/(j-i+1). The weighted minimum good interval cover problem is to find a group of good intervals that the total interval weight is minimized. The intervals are mutually disjoint. For Example, If A is [20, 21, 25, 26, 30, 31, 32, 34,37,39], and k is 7. [1, 3] is a good interval and its weight is 1/3-1/(3-1 + 1). [2, 2] is a good interval and its weight is 1=1/(2-2 + 1). There can be multiple groups of intervals that can cover all elements in A. We list out several good interval covers and the total weight as shown below. Actually, one can find that the sum of intervals' weight can not be less than 11/12. The [1, 4], [5, 7], [8, 10] (The fourth line) is a weighted minimum good interval cover.< 2 Good Intervals Sum of intervals weight [20, 21, 25, 26, 30, 31, 32, 34, 37,39 1/3+1/3+1/2+1/2-5/3 [20, 21, 25, 26, 30, 31, 32, 34, 37,39 1/2+1/2+1/2+1/2+1/2-5/2 [20, 21, 25, 26, 30, 31, 32, 34, 37,39 1/4+1/5+1=29/20 [20, 21, 25, 26, 30, 31, 32, 34, 37,39] 1/4+1/3+1/3=11/12 I 1 1) Suppose that A is [1, 3, 5, 6, 8, 13, 14, 17, 19, 20, 25], and k is 8, Please write out a weighted minimum good interval cover. (20% ) < 2) Now, given any sorted array A in increasing order and a positive integer k, please design a dynamic programming algorithm to find a weighted minimum good interval cover for A. What is the running time in terms of big-Oh. (20%) An interval's weight is defined as the reciprocal of the interval size. For example if an interval contains two elements, then its weight is 1/2; and it contains 5 elements, its weight is then 1/5. Given a sorted array A in increasing order and an integer k, the interval [i, j] contains j-i+1 elements, and thus it has a weight 1/(j-i+1). The weighted minimum good interval cover problem is to find a group of good intervals that the total interval weight is minimized. The intervals are mutually disjoint. For Example, If A is [20, 21, 25, 26, 30, 31, 32, 34,37,39], and k is 7. [1, 3] is a good interval and its weight is 1/3-1/(3-1 + 1). [2, 2] is a good interval and its weight is 1=1/(2-2 + 1). There can be multiple groups of intervals that can cover all elements in A. We list out several good interval covers and the total weight as shown below. Actually, one can find that the sum of intervals' weight can not be less than 11/12. The [1, 4], [5, 7], [8, 10] (The fourth line) is a weighted minimum good interval cover.< 2 Good Intervals Sum of intervals weight [20, 21, 25, 26, 30, 31, 32, 34, 37,39 1/3+1/3+1/2+1/2-5/3 [20, 21, 25, 26, 30, 31, 32, 34, 37,39 1/2+1/2+1/2+1/2+1/2-5/2 [20, 21, 25, 26, 30, 31, 32, 34, 37,39 1/4+1/5+1=29/20 [20, 21, 25, 26, 30, 31, 32, 34, 37,39] 1/4+1/3+1/3=11/12 I 1 1) Suppose that A is [1, 3, 5, 6, 8, 13, 14, 17, 19, 20, 25], and k is 8, Please write out a weighted minimum good interval cover. (20% ) < 2) Now, given any sorted array A in increasing order and a positive integer k, please design a dynamic programming algorithm to find a weighted minimum good interval cover for A. What is the running time in terms of big-Oh. (20%)

Answer rating: 100% (QA)

1 Weighted Minimum Good Interval Cover Example If A is 1 3 5 6 8 13 14 17 19 20 25 and k is 8 here i... View the full answer