Let A[1], A[2], A[n], be n integers (possibly with repetitions) in the range 1 .
ID: 3562955 • Letter: L
Question
Let A[1], A[2], A[n], be n integers (possibly with repetitions) in the range 1 ... k i.e. all the entries of the array A are between 1 and k. You want to repeatedly answer range queries of the form [a. 6] where 1 le a le b le k; each range query asks how many A[i]'s are in the range a... b, i.e.. how many numbers from A lie between a and b. For example, if k = 10. and the array A has seven elements 5,9,3,5,10,6,1,7 the range query [2,7] asks how many numbers are there in the array A between 2 and 7. so the answer should be 5 (because the numbers 3,5,5,6,7 from A lie in the range [2,7]). You want to do this efficiently. In order to do thus, you first do some preprocessing, which is a one-time operation i.e. you are willing to pay the one-time relatively expensive cost of doing preprocessing before starting to answer the range queries, in order to save time with the many range queries which will follow. Your algorithm should work within the following time bounds: The one time preprocessing step should take O(n + k) time. Each range query should be answered in O(1) (i.e. constant) time i.e. the amount of time to answer the range query [a, b] will be a small number which will in no way depend on n,k,A,a,b or the number of elements which actually lie in the range [a, b]. Give a clear description of your algorithm for the above problem. This description should include both how the preprocessing step Ls carried out, and then how the range queries are answered. 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]. 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. You will need to keep the auxiliary array C[1..k] we used for counting sort where C[j] represents the number of elements from A which are less than or equal to j. In the above example, C[2] will be 1 since there is one element (i.e. 1) in A which is le 2: C[7] will be 6 since there are 6 elements (i.e. 1,3,5,5,6,7) which are le 7. In class we saw how to fill C in time O(n + k) (this Ls the preprocessing step), and once the array C is available, you should show how to use it to answer range queries in O(1) time.Explanation / Answer
a) let the range of the numbers be 1to k and n be the total number of numbers.
we make a count array C[1..k] which we will build in following manner:
to answer the range query [a,b] we return the following:
if(a!=1 && (C[a]==C[a-1] || C[b]==C[b-1]) // it means that one of a or b doesn't belong to A
return C[b]-C[a];
else
return C[b]-C[a]+1;
b) For the given example , in the preprocessing step following count array C is created:
1 , 1, 2, 2, 4, 5, 6, 6, 7 , 8
thus for the query [2,7]
C[2]=1, C[7]=6
and C[2]=C[1] thus answer is C[7]-C[2]=6-1=5
for the query [1,9]
C[1]=1 C[9]=7
and a!=1 return false so else condition is evaluated thus,
ans=C[9]-C[1]+1=7-1+1=7
c) preprocessing step has to first build up count array which takes O(n) time then has to traverse count array which takes O(k) time thus in worst case it will take O(n+k) time and if k is O(n2) it will take O(n2 ) time.
range query takes O(1) time i.e. constant time as it just do simple computation by accessing entries of count array in O(1) time.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.