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
- 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
**deal-random**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`randomly-chosen cards from`D`in any order. - Rank profile
- Experimental probabilities
- Efficiency
- Analysis of
`cut!`

- Analysis of
`shuffle!`

- A better
`deal-random!`

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.

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:

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
`cut!`

and `shuffle!`

, have been given to you.
*Using the class's public functions*, implement the `deal`

and `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
`rank-profile`

function!).

We know
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.

Using the `card-deck%`

class and the two procedures
`two-pair?`

and `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
the maximal
cost of one call to the `shuffle!`

function on a deck with
`n`

cards. Prove that `S`(`n`) is
O(`n`^{2}).

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(`n`^{2}) 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.