CPSC 411: Quiz 9
October 30, 2008

Printed Name:________________________________________

"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. (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. (2 pt) What assumpion has to be made in order to do a probabilistic analysis of a deterministic algorithm?

  3. (2 pt) How does a randomized algorithm avoid the necessity of making the assumption referred to in the previous question?