Question is from algorithams analysis & design course 6. In this part you have t

Question

Question is from algorithams analysis & design course

6. In this part you have to come up with an algorithm to answer a more complicated range query, namely, given an array A as above, a range query [a,b] now requires you to actually list all of the A[i]’s in the range a...b. Using the same array A as above, the range query [2,7] asks which numbers from A are there in the array A are between 2 and 7, so the answer should be 3,5,5,6,7 (it doesn’t matter in what order the numbers are outputted). Your algorithm should work within the following time bounds:

• The one time preprocessing step should take O(n + k) time (the preprocessing here will be dierent from that in the rst part).

• Given a range query [a,b], the time taken to answer this query should not depend on k or on n or on the quantity ba; instead, the query should be answered in time O(t) where t is the number of elements in the output (the number of A[i]’s in the range [a,b]). For example, if we consider two range queries, [a1,b1] and [a2,b2], [a1,b1] leads to an output of 500 elements, and [a2,b2] leads to an output of 100 elements, then answering [a1,b1] should take approximately 5 times as much time as answering [a2,b2]. Or consider another example, where k = 106, n = 105, a = 2000, b = 3000, and there are only three elements in the range [2000,3000]. If you look at every entry in C between 2000 and 3000 i.e. you look at C[2000],C[2001],C[2002],...,C[3000], you are looking at ba = 1001 entries which is too expensive since t = 3 is much smaller than b1 i.e. there are only three elements in the range [2000,3000].

(a) Give a clear description of your algorithm for the above problem. This description should include both how the preprocessing step is carried out, and then how the range queries are answered.

(b) Trace your algorithm on the above example i.e. for the array A as above, show what will happen in the preprocessing step. Then show how the algorithm will answer the range query [2,7]. Also show how the algorithm will answer the range query [1,9].

(c) Do a worst case time analysis (use big O notation) of your algorithm i.e. answer the two questions: how much time does the preprocessing step take and how much time does answering the range query take.

Hint: You will need to keep one or more auxillary arrays; what these are going to be, you need to gure out. You should show how to ll these auxillary array(s) in time O(n + k) (this is the preprocessing step), and once these auxillary array(s) are available, you have to gure out how they can be used to quickly answer the range queries.

Explanation / Answer

First of all we need to create an array C[1..k]. ranges will be selected from 1..k. C is the array such the C[i] denote the number of elements less than or equal to i. To make this array the time complexity will be O(n+k). We need to travesrse the array A once to make the array C. So this will take n steps and we need to update C which will take k steps and hene total steps are n+k.
Once this is in place , given a range [a,b}, we just need to get the values of C[a] and C[b]. Finding the difference C[b] - C[a] will give the total number satisfying the range [a,b].This is a constant time step irrespective of n or k

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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