
Tutorial 4:
Poker Hands and Efficiency (May 25)
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).
 Using an ADT implementation
For this part of the tutorial, we will be using the two classes
DEQ% and card% that were developed in
last week's tutorial. Code for these classes can
be found here.
 Deck of cards
We can represent a deck of playing cards as an ADT:
A Deck of Cards is a sequence
c_{1},
c_{2}, ...,
c_{52},
where each c_{i} is one of the 52 distinct
playing cards. There are four operations on a deck of cards:
 The cut operation has two arguments: an integer
k in the range
0 ≤ k < 52, and a deck of cards
D = c_{1},
c_{2}, ...,
c_{52}, with precondition "true".
The postcondition is that
D = c_{k+1},
c_{k+2}, ...,
c_{52},
c_{1}, ...,
c_{k}, and no value is produced.
 The shuffle operation has one argument: a deck of cards
D = c_{1},
c_{2}, ...,
c_{52}, with precondition "true".
The postcondition is that D contains all the same cards
c_{1} through c_{52}, but in
a random order, and no value is produced. (To be more precise, we might say
something about permutations of (1,2,...,52) or probability distributions, but
this is not really necessary.)
 The deal operation has two arguments: an integer
k in the range
1 ≤ k ≤ 52, and a deck of cards
D = c_{1},
c_{2}, ...,
c_{52}, with precondition "true".
The postcondition is "true", and the (possibly empty) sequence
H = c_{1},
c_{2}, ...,
c_{k} is produced.
 The dealrandom operation
has two arguments: an integer
k in the range
1 ≤ k ≤ 52, and a deck of cards
D = c_{1},
c_{2}, ...,
c_{52}, with precondition "true".
The postcondition is that the order of the sequence D might change,
and a sequence H is produced containing k
randomlychosen cards from D in any order.
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 dealrandom 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
carddeck% 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
cut! and shuffle! , have been given to you.
Using the class's public functions, implement the deal
and dealrandom! procedures, in that order.
 Rank profile
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, rankprofile 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 builtin 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.
 Experimental probabilities
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, twopair? , which consumes a list of 5 cards
and produces true iff those 5 cards form a twopair hand (hint: use the
rankprofile function!).
We know
the probability that a randomlyselected list of 5 cards will be twopair
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,
runexperiment , 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.
Using the carddeck% class and the two procedures
twopair? and runexperiment , find the experimental
probability that a randomlyselected 5card hand is a twopair hand with
1000 trials (you can adjust this number for more or less accuracy).
Note: you can also use the rankprofile function to easily
test whether a given 5card 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.
 Efficiency
 Analysis of
cut!
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).
 Analysis of
shuffle!
Now look at the implementation of shuffle! . It may help to
recall that the builtin Scheme function random takes one
parameter, an integer m and returns a randomlychosen integer
in the range [0,m1].
Define the (mathematical) function S(n) to be
the maximal
cost of one call to the shuffle! function on a deck with
n cards. Prove that S(n) is
O(n^{2}).
 A better
dealrandom!
Now look at the given (simple) implementation of
dealrandom! . 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
dealrandom! on a deck with n cards. First, convince
yourself that D(n) is O(n^{2}) for
our simple implementation.
Now write a different implementaion of dealrandom! 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).
