Give a high-level pseudocode for an algorithm that, given a list of n integers f

Question

Give a high-level pseudocode for an algorithm that, given a list of n integers from the set {0, 1, . . . , k 1}, preprocesses its input to extract and store information that makes it possible to answer any query asking how many of the n integers fall in the range [a..b] (with a and b being input parameters to the query) in O(1) time. Explain how your algorithm works.

The preprocessing time should be O(n + k) in the worst case. Provide an argument showing that your preprocessing algorithm meets that bound.

Explanation / Answer

Ans: pseudocode for an algorithm

function countingSort(array, min, max)

count: array of (max – min + 1) elements

initialize count with Zero

for every number in array do

    count[number – min] := count[number-min] + 1

done

z:= 0

    while(count[ i – min] >0) do // for I from min to max

      array[z] := i

      z := z + 1

      count[i – min] := count [i – min] – 1

    done

   done

Find Pseudo Code

find(a, b)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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