4. (15 pts.] A common operation in many computer simulations is the generation of samples from a discrete random variable. The problem essentially can be mathematically reduced to the following simple case. Consider a discrete random variable X taking values in the set Sx = {0, 1, 2, ...,n 1} with probability mass function (PMF) px, so that px(x) is the probability that the random variable X takes value x Sy. Let Fx be the cumulative distribution function (CDF) of X, whose domain is the set of real values R = (-0, too, and is defined as Fx(z) = P(X n-1. (1, A simple general approach to generate random samples from X according to its PMF px is to draw a number r uniformly at random from the interval [0, 1], and then use the CDF FX to select the value x as the random sample of X if Fx (x - 1) F[x] do 10: x +1 11: return x Algorithm 2 RANDDISCRETE2(P) 1: F + new n-element array 2: F[0] + P[0] 3: for j+ 1 to n - 1 do 4: F[j] F[j - 1] + P[j] 5: r + RANDO 6: + 0 7: while r > F[x] do 8: + 2+1 9: return c (a) Give the tightest running-time and space characterization using big-Oh and big-Omega, or big-Theta, of RAND DISCRETE1 in terms of n. Briefly justify your answer. Time Space (b) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of RANDDISCRETE2 in terms of n. Briefly justify your answer. Time Space (c) Which algorithm do you recommend to implement, and why? Briefly justify your answer. (d) Write, in pseudocode, a linear-time algorithm RANDDISCRETE3 for this computational problem that takes an array P of n elements as input and outputs a random integer consistent with a discrete random variable with integer values 0, 1,...,n 1 according to the probability mass function encoded by P and that uses a constant amount of space. Is this algorithm better than the algorithm you recommended to implement in the previous part of this problem? Please explain briefly. 4. (15 pts.] A common operation in many computer simulations is the generation of samples from a discrete random variable. The problem essentially can be mathematically reduced to the following simple case. Consider a discrete random variable X taking values in the set Sx = {0, 1, 2, ...,n 1} with probability mass function (PMF) px, so that px(x) is the probability that the random variable X takes value x Sy. Let Fx be the cumulative distribution function (CDF) of X, whose domain is the set of real values R = (-0, too, and is defined as Fx(z) = P(X n-1. (1, A simple general approach to generate random samples from X according to its PMF px is to draw a number r uniformly at random from the interval [0, 1], and then use the CDF FX to select the value x as the random sample of X if Fx (x - 1) F[x] do 10: x +1 11: return x Algorithm 2 RANDDISCRETE2(P) 1: F + new n-element array 2: F[0] + P[0] 3: for j+ 1 to n - 1 do 4: F[j] F[j - 1] + P[j] 5: r + RANDO 6: + 0 7: while r > F[x] do 8: + 2+1 9: return c (a) Give the tightest running-time and space characterization using big-Oh and big-Omega, or big-Theta, of RAND DISCRETE1 in terms of n. Briefly justify your answer. Time Space (b) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of RANDDISCRETE2 in terms of n. Briefly justify your answer. Time Space (c) Which algorithm do you recommend to implement, and why? Briefly justify your answer. (d) Write, in pseudocode, a linear-time algorithm RANDDISCRETE3 for this computational problem that takes an array P of n elements as input and outputs a random integer consistent with a discrete random variable with integer values 0, 1,...,n 1 according to the probability mass function encoded by P and that uses a constant amount of space. Is this algorithm better than the algorithm you recommended to implement in the previous part of this problem? Please explain briefly