The first part of today's tutorial makes effective use of the ADT implementations from Tutorial 3 in order to compute some experimental probabilities involving poker hands. Next, we will look at a given implementation of a function, analyze the cost, then write an improved version and redo the analysis. The material here comes from lecture modules 4 and 5 (see Handouts).
For this part of the tutorial, we will be using the two classes
card% that were developed in
last week's tutorial. Code for these classes can
be found here.
We can represent a deck of playing cards as an ADT:
A Deck of Cards is a sequence c1, c2, ..., c52, where each ci is one of the 52 distinct playing cards. There are four operations on a deck of cards:
Intuitively, the cut operation takes k cards from the top of the deck and moves them to the bottom, the deal operation returns the top k cards from the deck, and the shuffle and deal-random operations do exactly what we would expect.
In the skeleton code for this tutorial, you are given a partial
implementation of this ADT in Scheme. This is achieved via a class
card-deck% with one private field, an instance of the
DEQ% class, and four public operations as described above.
The class initialization, as well as definitions for procedures
shuffle!, have been given to you.
Using the class's public functions, implement the
deal-random! procedures, in that order.
For a given list of
card%s, define the "rank profile" to be a list
of the size of each group of cards with the same rank, sorting in decreasing
order. So, for example, a list of four cards with the 10 of diamonds, the
8 of hearts, the 10 of spades, and the 9 of diamonds would have rank profile
(2 1 1). A list containing any two queens and three aces would have rank
profile (3 2).
Write a procedure,
rank-profile which consumes a list of
card%s and produces a list of numbers which is the rank profile
for the given list.
To implement this procedure, you may want to proceed
in three stages: First, use the built-in
sort function to
group all cards with the same rank together in the list. Next, go through
the list and count the size of each group of cards with the same rank, producing
a list of group sizes. Finally, use the
sort function again to
sort these group sizes and produce the rank profile.
Now we are ready to do something really interesting!
In a regular game of poker, each player receives a "hand" consisting of
5 cards. The success or failure of the player is based largely on whether or not
her 5 cards match some pattern. For example, having one pair of cards with the
same rank, another pair that share another rank, and a fifth card with a
different rank, is known as "two pair", and is not a very great hand.
Write a function,
two-pair?, which consumes a list of 5 cards
and produces true iff those 5 cards form a two-pair hand (hint: use the
the probability that a randomly-selected list of 5 cards will be two-pair
is exactly 198/4165, or approximately 0.047539. We want to run experiments
to test this probability. Useful in this endeavor will be a function,
run-experiment, which is also included in the skeleton code for
today's tutorial. This function consumes a procedure that takes no arguments
and always produces true or false, and a positive integer n.
The given procedure will be called exactly n times, and the
experimental probability that the procedure returns true will be returned
(which is just the number of times the procedure returned true in the
n trials, divided by n). The time it took for the
computer to run the trials will also be displayed.
card-deck% class and the two procedures
run-experiment, find the experimental
probability that a randomly-selected 5-card hand is a two-pair hand with
1000 trials (you can adjust this number for more or less accuracy).
Note: you can also use the
rank-profile function to easily
test whether a given 5-card hand is a single pair, three of a kind, full
house, or four of a kind. You can also write functions to test if a given
set of cards is straight, flush, or straight flush. To find out more about
the probabilities of getting all these hands, see for example
this nice website from SFU.
Look at the implementation of the
cut! function in the
given skeleton code. Define the (mathematical)
function C(k) to be the cost of the call to
cut! with parameter k. Prove that
C(k) is O(k).
Now look at the implementation of
shuffle!. It may help to
recall that the built-in Scheme function
random takes one
parameter, an integer m and returns a randomly-chosen integer
in the range [0,m-1].
Define the (mathematical) function S(n) to be
cost of one call to the
shuffle! function on a deck with
n cards. Prove that S(n) is
Now look at the given (simple) implementation of
deal-random!. For this question, we will consider the parameter
to the function, k, to be constant (think about the importance
and validity of this distinction). Define the function
D(n) to be the maximal cost of one call to
deal-random! on a deck with n cards. First, convince
yourself that D(n) is O(n2) for
our simple implementation.
Now write a different implementaion of
deal-random! such that
D(n) is O(n) (and prove this).
Compare the new and old implementations with respect to
time it takes to perform the experimental tests, to see how much the theoretical
improvement saved in practice (for n=52).
Last modified on Friday, 19 August 2011, at 18:05 hours.