Discrete distribution. Design a fast algorithm to repeatedly generate numbers from the discrete distribution: Given an array a[] of non-negative real numbers that sum to 1, the goal is to return index...

Discrete distribution. Design a fast algorithm to repeatedly generate numbers from the discrete distribution: Given an array a[] of non-negative real numbers that sum to 1, the goal is to return index i with probability a[i]. Form an array sum[] of cumulated sums such that sum[i] is the sum of the first i elements of a[]. Now, generate a random real number r between 0 and 1, and use binary search to return the index i for which sum
 r
 sum[i+1]. Compare the performance of this approach with the approach taken in RandomSurfer (Program 1.6.2).

Program 1.6.2