15110 Fall 2011 [Cortina/von Ronne]

Written Homework 8 - due Friday, November 4 in class

Reading Assignment

Read sections 9.1-9.6 in chapter 9 of the textbook Explorations in Computing.



  1. (1 pt) A linear congruential random number generator is created with a = 3, c = 7, m = 16. What is the period of this random number generator if it starts with a seed of 0? What is the sequence of values generated by this random number generator in one period? Show your work for full credit.

  2. (2 pts) Use the random function in Ruby to solve each of the following tasks:

    1. Write a Ruby function spin1() that returns an integer and simulates the wheel spinner from the Milton Bradley game of Life. The wheel contains the numbers from 1 to 10.

    2. Write a Ruby function spin2() that returns an integer and simulates the Showcase Showdown wheel from the Price Is Right game show. The wheel contains the multiples of 5 from 5 to 100.

    3. Write a Ruby function roll1() that returns an integer and simulates a backgammon doubling cube. The 6-sided cube contains the values 2, 4, 8, 16, 32, and 64.

    4. Write a Ruby function roll2() that returns a string and simulates a poker die. The 6-sided cube contains the values "Ace", "King", "Queen", "Jack", "Ten", and "Nine". (You should simulate just one die.)

  3. (1 pt) Homer Simpson tries his luck at programming again and writes the following Ruby functions for our simple dice game given in class:

    def roll1()
    	return rand(6) + 1
    def roll2()
    	return rand(6) + 1
    def simple_game()
    	strikes = 0
    	sum = 0
    	while (strikes < 3) do
    		if roll1() == roll2() then
    			strikes = strikes + 1
    			sum = sum + roll1() + roll2()
    	return sum

    Unfortunately, Homer fails again. Explain clearly what is logically wrong with this computation. (Don't just say that he should have written it our way. Instead, say what's wrong with THIS approach.)

  4. (2 pts) Write a Ruby function four_of_a_kind(hand) that take a hand of five playing cards and returns true if the hand of five playing cards represents a "four of a kind", or false otherwise. A "four of a kind" is a hand where four of the cards have the same rank.

    TYPO CORRECTED: HINT: There are only FIVE possibilities where you can have a "four of a kind".

  5. (2 pts) Consider a pseudo random number generator based on the linear congruential method with a = 81, c = 337 and m = 1000.

    1. Using irb and RandomLab, generate a set of 20 random numbers from this generator. Try this with several different seeds. Look at each sequence of numbers you get. What is the pattern in each of the sequences? (HINT: Something about the numbers alternates back and forth as you go from one number to the next. Look at the last digit of each number.)

    2. If you used this random number generator for our simple dice game, our game would not work. Why? Explain clearly.

  6. (2 pts) Recall that when using a one-dimension cellular automaton, we can describe the rule for changing cells from one generation to the next using a number that is related to the change for each of the 8 possibilities from one generation to the next. For example, here is rule 30:

    Consider a one-dimensional cellular automaton starts with a single black square and uses "Rule 250".

    1. Show the replacement rule for Rule 250 following the example shown above and in class. (That is, show each combination of a cell and its two neighbors, and what color it will be set to in the next generation.)

    2. Using a piece of graph paper, show the first 10 stages of this rule. Do you recognize the pattern? (If you need a piece of graph paper, you can print this page: sheet of graph paper.