CPSC 411: Quiz 9
October 30, 2008
"On my honor, as an Aggie, I have neither given nor received
unauthorized aid on this academic work.
In particular, I certify
that I have not received or given any assistance that is
contrary to the letter or the spirit of the collaboration
guidelines for this assignment."
- (1 pt) Consider a card game in which each player initially gets 5 cards
from a deck of 52 cards. Suppose someone claims "The probability
of getting 4 kings is one in a million." Regardless of the truth
of the claim, what is the underlying sample space to which the
person is referring?
- (2 pt)
What assumpion has to be made in order to do a probabilistic
analysis of a deterministic algorithm?
- (2 pt)
How does a randomized algorithm avoid the necessity of making
the assumption referred to in the previous question?