CS 136 Tutorials - Spring 2007

Tutorials »

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₁, c₂, ..., c₅₂, 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₁, c₂, ..., c₅₂, with precondition "true". The postcondition is that D = c_k+1, c_k+2, ..., c₅₂, c₁, ..., c_k, and no value is produced.
• The shuffle operation has one argument: a deck of cards D = c₁, c₂, ..., c₅₂, with precondition "true". The postcondition is that D contains all the same cards c₁ through c₅₂, 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₁, c₂, ..., c₅₂, with precondition "true". The postcondition is "true", and the (possibly empty) sequence H = c₁, c₂, ..., 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₁, c₂, ..., c₅₂, 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.

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.

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, 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.

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, 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.

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 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²).

A better deal-random!

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²) 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.