To show that the RANDOM-SAMPLE procedure returns a random m -subset of { 1 , 2 , 3 , .. n } where each m -subset is equal likely.

Question

Want to see the full answer?

Answer 1

Question

Chapter 5.3, Problem 7E

Program Plan Intro

To show that the RANDOM-SAMPLE procedure returns a random m -subset of {1,2,3,..n} where each m -subset is equal likely.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Students have asked these similar questions

Given an array of numbers X₁ = {x₁, x2, ..., n } an exchanged pair in X is a pair xi, xj such that i x¡ . Note that an element x; can be part of up to n - 1 exchanged pairs, and that the maximal possible number of exchanged pairs in X is n(n − 1)/2, which is achieved if the array is sorted in descending order. Give a divide-and-conquer algorithm that counts the number of exchanged pairs in X in O(nlogn) time.

Consider a set of random numbers IIDR [0,1] = [0.11,0.63,0.37,0.08,0.71,0.56,0.45,0.29,0.68]. Convert the set of random number to a set of random variates for N(0,1). Further convert this set of random variates to another set for N(5,3). Present the random numbers and the random variates in a Table as sought below. S.no IIDR[0,1] Random Variates for N(0,1) Random Variates for N(5,3)

Write a Python function mat_to_prob (R) that returns the matrix P = (P₁, P2, ..., Pm) where Pi is the i-th row of matrix P , and Pi is the probability vector obtained from R; using the formulation in Question 1. In other words, convert each row of the input matrix into a probability vector. Sample inputs and outputs: • Input: np.array([[4, 6], [3.5, 9.11) Output: [[0.11920292 0.88079708] [0.00368424 0.99631576]] • Input: np.array([[2, 3.1, 5], [10, 3.7, 12], [4, 5.5, 0]])) Output: [[4.15115123e-02 1.24707475e-01 8.33781013e-01] [1.19176835e-01 2.18844992e-04 8.80604320e-01] [1.81818026e-01 8.14851861e-01 3.33011331e-03]] Hint: use numpy.sum with an appropriate axis and keepdims settings. You should also check broadcasting in numpy. Question 2b In fact, the function above is called the softmax function, and scipy has an implementation for it. First, read the API at: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.softmax.html. Then write code to apply this version of…