Use indicator random variables to solve the following problem, which is known as the hatcheck problem. Each of n customers gives a hat to a hat-check person at a restaurant. The hatcheck person gives the hats back to the customers in a random order. What is the expected number of customers that get back their own hat?
Answer to relevant QuestionsLet A[1 .. n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, ...Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities ...Show that the running time of QUICKSORT is Θ (n2) when the array A contains distinct elements and is sorted in decreasing order.Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for ...
Post your question