Note: You are responsible for protecting your solutions to these problems from being seen by other students both physically (e.g., by looking over your shoulder) and electronically. (More information can be found in the instructions for Programming Assignment 2.)
Some small portion of your grade will be allocated for style. This means that you are required to keep each line of code under 80 characters in length, to properly indent your code (ask a TA or post to Piazza if you are unsure how to indent), and to try and use meaningful variable names where appropriate (i.e. if you are summing the elements in a list, use a variable such as sum instead of x).
[2 points] Blum Blum Shub
Recall from class that the linear congruential random number generator creates random numbers using the formula: $$ x_{i+1} = (a * x_{i} + c)\mod{m}$$
That is, if you know the $i_{th}$ random number $x_{i}$, then you can compute the next number in the sequence $x_{i+1}$ using the formula.
Another pseudo random number generator is the Blum Blum Shub (BBS) pseudorandom number generator. (The Blums are faculty members here at Carnegie Mellon University!) Blum Blum Shub uses the formula: $$x_{i+1} = x_{i}^{2}\mod{m}$$
(with certain restrictions on the seed $x_{0}$ and modulus $m$) to compute a new pseudorandom number based on a previous one. In general, compared to LCG, BBS is slower, but provides higher quality random numbers that can't be predicted without first factoring $m$, which is hard when $m$ is the product of two large prime numbers. An example of an $m$ that satisfies the requirements is 2006591449, which is the product of the prime numers 44771 and 44819.
In a file bbs.rb, write a Ruby function bbs_seq(x0,n) that returns an array of $n$ pseudorandom numbers $(x_{0}…x_{n-1})$ generated using Blum Blum Shub starting with a seed of $x_{0}$ with an $m$ of 2006591449.
Example:
>> load "bbs.rb" => true >> bbs_seq(1320173001,9) => [1320173001, 1250489923, 1654713313, 317068542, 1414597374, 1257516709, 1036152133, 891491908, 1351900575]
[5 pts] Implementing "unconventional" coins
[2 points]
In this question we're going to make a biased coin. Normally we assume that a coin is a binary random variable with equal probability of coming up heads or tails. We can model this in Ruby by calling rand(2) and treating a result of 1 as heads and 0 as tails. But suppose we want to model a coin that comes up heads 60% of the time. One way to do this is to provide for 10 random values, say 0 through 9. A fair coin would treat any value from 0 to 4 as tails, and 5 to 9 as heads. If we instead set our tails threshold at 3, then the last six values (4 to 9) will be treated as heads, giving this outcome a 6/10 = 60% probability. In the file biased.rb, write the function biased_coin() that comes up heads 75% of the time.
Example:
>> load "biased.rb" => true >> biased_coin() => "heads" >> biased_coin() => "tails"
[3 points] 3 sided-coin
Assume there exists a coin with three sides: heads, tails, and legs. In the file biased.rb, write the function three_sided_coin() that comes up heads, tails, or legs equal amounts of the time.
Example:
>> load "biased.rb" => true >> three_sided_coin() => "heads" >> three_sided_coin() => "legs" >> three_sided_coin() => "tails"
[3 points] The RandomLab in RubyLabs provides facilities for creating and manipulating Card objects.
Define a function score21(hand) in cards.rb, which takes an array of RandomLab Card objects called hand and computes and returns a score for that hand based on the familiar card game Twenty One (Blackjack). Each card with a numerical rank (2-10) is scored worth that many points. A card with a rank of Jack, Queen, or King is worth 10 points. An Ace is worth 11 points, unless that would put the total score over 21, in which case it is only worth one point. The score for the hand is the sum of the points for each of the cards.
Use the following algorithm:
Example:
>> load "cards.rb" => true >> h = [Card.new(1), Card.new(17), Card.new(39)] => [KS, 10H, AC] >> score21(h) => 21 >> h = [Card.new(39), Card.new(19), Card.new(6)] => [AC, 8H, 8S] >> score21(h) => 17
You should now have a pa8 directory that contains the files bbs.rb, biased.rb, and cards.rb each containing the corresponding function. Zip up your directory and hand it in.