Alguém por um acaso teria como scanear os exercícios para colocar online? Ou disponibilizar um CLRS para que eu possa fazê-lo?
[]'s
Lemes
C2-2
Professor Rosencrantz flips a fair coin once. Professor Guildenstern flips a fair coin twice. What is the probability that Professor Rosencrantz obtains more heads than Professor Guildenstern?
C2-3
A deck of 10 cards, each bearing a distinct number from 1 to 10, is shuffled to mix the cards thoroughly. Three cards are removed one at a time from the deck. What is the probability that the three cards are selected in sorted (increasing) order?
C2-4
Describe a procedure that takes as input two integers a and b such that 0 < a < b and, using fair coin flips, produces as output heads with probability a/b and tails with probability (b-a)/b. Give a bound on the expected number of coin flips, which should be O(1). (Hint: represent a/b in binary.)
C2-7
Show how to construct a set of n events that are pairwise independent but such that no subset of k > 2 of them is mutually independent.
C2-8
Two events A and B are conditionally independent, given C, if
Pr{ A [intersecção] B | C } = Pr {A | C} * Pr {B | C}
Give a simple but nontrivial example of two events that are not independent but are conditionally independent given a third event.
C3-2
An array A[1..n] contains n distinct numbers that are randomly ordered, with each permutation of the n numbers being equally likely. What is the expectation of the index of the maximum element in the array? What is the expectation of the index of the minimum element in the array?
C3-5
Let X and Y be independent random variables. Prove that f(X) and g(Y) are independent for any choice of functions f and g.
C3-8
Which is larger: the expectation of the square of a random variable, or the square of its expectation?
Professor Rosencrantz flips a fair coin once. Professor Guildenstern flips a fair coin twice. What is the probability that Professor Rosencrantz obtains more heads than Professor Guildenstern?
C2-3
A deck of 10 cards, each bearing a distinct number from 1 to 10, is shuffled to mix the cards thoroughly. Three cards are removed one at a time from the deck. What is the probability that the three cards are selected in sorted (increasing) order?
C2-4
Describe a procedure that takes as input two integers a and b such that 0 < a < b and, using fair coin flips, produces as output heads with probability a/b and tails with probability (b-a)/b. Give a bound on the expected number of coin flips, which should be O(1). (Hint: represent a/b in binary.)
C2-7
Show how to construct a set of n events that are pairwise independent but such that no subset of k > 2 of them is mutually independent.
C2-8
Two events A and B are conditionally independent, given C, if
Pr{ A [intersecção] B | C } = Pr {A | C} * Pr {B | C}
Give a simple but nontrivial example of two events that are not independent but are conditionally independent given a third event.
C3-2
An array A[1..n] contains n distinct numbers that are randomly ordered, with each permutation of the n numbers being equally likely. What is the expectation of the index of the maximum element in the array? What is the expectation of the index of the minimum element in the array?
C3-5
Let X and Y be independent random variables. Prove that f(X) and g(Y) are independent for any choice of functions f and g.
C3-8
Which is larger: the expectation of the square of a random variable, or the square of its expectation?