Question 1: Question 2: Question 1: Given a sorted array of distinct integers A[

Question

Question 1:

Question 2:

Question 1: Given a sorted array of distinct integers A[1 ... n]. We are interested in determining if there is an index i in the array so that A[i] = i. Of course, one can simply scan the array to solve the problem. We want to do better. a. Design an O(log n) - time algorithm that solves the problem. (Hint: Keep in mind that the elements of A[1... n] are distinct integers and already sorted.) b. Why is your algorithm correct, and why is its runtime O(log n)? The Minimum Coverage Problem Let L be a set of n line segments on the x-axis. The ith line segment is [li,ri], where li and ri denote the left and right endpoints of the line segment respectively. For some positive number M, we want to cover the segment [0, M] completely using the fewest number of line segments from M. a. Warm up! Let L = {[-1.5,1.5], [-4,2], [2,3], [3,5], [1, 4.5]} and M = 4.2. What is the fewest number of line segments from L that cover [0,4.2]. What are they? b. Given a set L and a positive number M, solve the Minimum Coverage Problem using a greedy algorithm. In particular, if the line segments in L can cover [0, M], the algorithm should output the fewest number of line segments that can do so; otherwise, it should indicate that the line segments from L cannot do so. c. Argue why your answer is correct. What is its runtime?

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;

int find(int l[],int low,int high){

   if (low > high)
       return -1;
   if (low == high){
       if (l[low] == low)
           return low;
       return -1;
   }
   int mid = (low+high)/2;
   if (l[mid] == mid)
       return mid;
   int res = find(l,low,mid-1);
   if (res != -1)
       return res;
   return find(l,mid+1,high);
}

int main(){
   int l[] = {1,6,6,6,6,6,6};
   cout << find(l,0,6) << endl;
   return 0;
}

recursion relation :
T(n) = T(n/2) + 1

Repeat the recurrence...

T(N) = T(N/4) + 2

       = T(N/8) + 3

          ...  

       = T(N/2k) + k

so the time complexity is O(log n)  

Answer 2 :

  1. Minimum number of Line segements needed from L to coever [0,4.2] is 2. ( [-1.5,1.5] and [1,4.5] )

  2. We first sort the intervals in nondecreasing order of their left endpoint. Ties are broken as follows: if ai = aj then [ai, bi] precedes [aj, bj] in the sorted sequence if bi > bj. Otherwise, if bi < bj, [aj, bj] precedes [ai, bi] (note that it cannot be the case that bi = bj or the two intervals would be the same). In other words, ties are broken in favor of the larger interval. Once the intervals are so sorted, we perform a linear scan of the intervals. The greedy choice is to select the first interval. At the i-th iteration, let [ak, bk] denote the last interval that was selected. Interval [ai, bi] is discarded if it is contained in [ak, bk], and is selected otherwise.

use quick sort to sort the set L which is time complexity O(n log n).
then O(n) to pick the desired interval.
total time complexity O(n log n) + O(n).

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.