Suppose I am going to choose an integer between 1 and n, inclusive, according to some probability distribution. For each integer i, I have written pi, the probability that I select i as the chosen integer. You may assume that ni=1 pi = 1. (a) Give an O(n3) time algorithm to compute a 2D-array X, where X[i, j] is the probability that some integer in the range [i, j] (inclusive) is chosen. You may assume that arith- metic operations take O(1) time each.
(b) Give an O(n2) time algorithm to solve the problem in part (a). If you are confident that your answer to this question is O(n2), you may elect to skip the previous part and count this as your answer to both.