15110 Spring 2013 [Kaynar/Gunawardena]

Problem Set 8 - due Friday, March 29 in class

Reading Assignment

Read Chapter 9 of the textbook Explorations in Computing.

Instructions

  1. (2 pts) The laws of Boolean algebra, presented in the lecture slides for Unit 8 can be used to show that two formulae are equivalent by transforming one into the other. For example, here is the proof that P ∧ (Q ∧ P) is equivalent to P ∧ Q:
    Step   FormulaJustification (Rule)
    1.P ∧ (Q ∧ P)
    Commutative
    2.P ∧ (P ∧ Q)
    Associative
    3.(P ∧ P) ∧ Q    
    Idempotence
    4.P ∧ Q
    The commutative rule lets us switch the order of two terms, while the associative rule lets us move parentheses around (or add or remove them) when the connectives are all the same. The above table shows that step 2 was derived from step 1 via the commutative rule, step 3 was derived from step 2 via the associative rule, and step 4 was derived from step 3 via the idempotence rule.

    We can also use DeMorgan's law to transform expressions. Here is the proof that ¬(P ∧ Q) ∨ ¬ R is equivalent to ¬ P ∨ ¬ (Q ∧ R):

    Step   FormulaJustification (Rule)
    1.¬(P ∧ Q) ∨ ¬ R
    DeMorgan's Law
    2.(¬ P ∨ ¬ Q) ∨ ¬ R    
    Associative
    3.¬ P ∨ (¬ Q ∨ ¬ R)
    DeMorgan's Law
    4.¬ P ∨ ¬ (Q ∧ R)
    Similarly. here is the proof that (A ∨ (B ∧ C)) ∧ ¬(A ∨ C) is false, i.e., equivalent to 0:
    Step   FormulaJustification (Rule)
    1.[A ∨ (B ∧ C)] ∧ ¬(A ∨ C)
    Distributive
    2.[(A ∨ B) ∧ (A ∨ C)] ∧ ¬(A ∨ C)   
    Associative
    3.(A ∨ B) ∧ [(A ∨ C) ∧ ¬(A ∨ C)]
    Complement: x ∧ ¬ x
    4.(A ∨ B) ∧ 0
    Dominance: x ∧ 0
    5.0
    For each of the following proofs, fill in the missing elements.
    1. First problem:
      StepFormulaRule
      1.A ∧ (A ∨ B)
      ?
      2.(A ∨ 0) ∧ (A ∨ B)    
      ?
      3.A ∨ (0 ∧ B)
      ?
      4.A ∨ 0
      Identity
      5.?

    2. Second problem:
      StepFormulaRule
      1.¬ A ∨ ¬ B ∨ ¬ C
      ?
      2.(¬ A ∨ ¬ B) ∨ ¬ C    
      DeMorgan's Law
      3.¬(A ∧ B) ∨ ¬ C
      ?
      4.¬ ((A ∧ B) ∧ C)
      Associative
      5.¬ (A ∧ B ∧ C)

  2. (2 pts) Random number generation.

    1. A linear congruential random number generator is created with a = 5, 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. Now suppose that c = 23 instead of 7. What do you observe? Then try c = 39. What can you conclude from your observations?

    3. Consider a linear congruential random number generator with a = 1 and m = 2 32, with a seed of 0. Can you think of a setting for c that would make the linear congruential random number generator have a period of 2 32 ? Is having a long period sufficient for a sequence to look random?

  3. (3 pts) Random distributions.

    We can simulate rolling a conventional six-sided die by using the built-in random number generator rand(n). The function roll below shows how to do this. 

      def roll()
    return rand(6) + 1
end

    1. Use the RandomLab module in Ruby and the roll function above to study the distribution of rolls by drawing a histogram, rolling the die 1000 times. Is the outcome (almost) uniformly distributed? Note that uniformly distributed means that the probability of generating any number from 1 to 6 is the same. You can include the graphical output of your experiment in your submission, or draw what you see on screen by hand. What matters is how you interpret what you observe.

    2. Suppose we want to simulate rolling a pair of dice by calling the roll function twice. Use the RandomLab module in Ruby to draw a histogram by rolling two dice 1000 times. The histogram should have a bin for every possible sum. The possible sums for rolling two dice are 1 + 1 = 2, 2 + 1 = 3, 2 + 2 = 4, ..., 6 + 6 = 12. Make a histogram of the outcomes and describe the distribution you observe.

    3. Now consider doing the same experiment but this time defining the roll12 function as given below. Instead of calling the rand function twice, the roll12 function calls it only once and generates a number between 2 and 12: 
      def roll12()
    return rand(11) + 2
end

      Repeat the experiment from part (b) using the roll12 function defined in this part. What kind of a distribution do you observe in the histogram? How does it compare to the distribution from part (b)?

    4. Is the simulation method from part (c) equivalent to the one from part (b)? Why or why not? If they are not equivalent then which one is correct?

  4. (1 pt) Consider the following code written for a simple dice game. In this game, if the player does not roll "doubles", then the player adds the sum of the dice to their total. If the player rolls "doubles", the player's total gets reset back to 0. At the end of the game, the player wins the number of total points accumulated after 10 rolls. There is a logical error in the program below. Explain what is wrong in this computation below and show how to correct it. 

    def roll1()
        return rand(6) + 1     # simulate a roll of a six-sided die
end

def roll2()
        return rand(6) + 1     # simulate a roll of a six-sided die
end

def simple_game()
        total = 0
	for i in 1..10 do
                if roll1() != roll2() then
                        total = total + roll1() + roll2()
                else
                        total = 0
                end
        end
        return total
end

  5. (2 pts) Print out a copy of the Cellular Automata worksheet.

    1. Complete the templates at the top of the worksheet to represent Rule 102.

    2. Starting with a first generation with only one black cell in the middle of the first row, draw the next 15 generations of the cellular automaton based on Rule 102.

    3. If you look down the middle column of the resulting figure, could you use this binary sequence as a random number generator? Why or why not?

    4. Would you classify the resulting figure as a fractal? Why or why not?