15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 9 - due Monday, November 5 in class

Reading Assignment

Read Chapter 9 of the textbook Explorations in Computing.

Instructions

Part I

  1. (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?

  2. (2 pt) 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?

  3. (1 pt) Consider a 1D binary cellular automaton with the "standard" initial state: a single black square in the middle of the row. Suppose with each generation we want this black square to move one place to the right. This means successive generation will still have a single black square (until it runs off the right edge of the grid), but in a different location. Design a rule to make this happen.

    1. Verify your rule's correctness using the cellular automaton simulator that was demonstrated in lecture. You can download the program from here. To test your rule, write ca1d(____,61,30).

    2. Show the graphical notation for your rule using the eight T-shaped figures you saw in the OLI module and again in the lecture.

      Write down the eight bit binary code for your rule and the equivalent decimal rule number.

  4. (2 pts) Try out rule 122 by writing ca1d(122,61,20). This pattern is very regular and doesn't look too interesting, given the standard initial state.

    1. Draw the graphical representation of this rule as eight T-shapes.

    2. Let's consider a different initial state. Instead of a single black square, we'll have two adjacent black squares in the middle of the row. If you read the source code for the ca1d method you'll see that it accepts an optional argument called initial_positions to specify a different initial state if you don't want the default one. Since the specified width is 61, the default value of initial_positions is the list [30]. Figure out the correct value to supply for this argument, and run the rule for 28 iterations by writing ca1d(122,61,28,_____). Fill in the blank.

    3. What does the resulting shape look like?

    4. We haven't exhausted all that this rule can do given our modified initial state. If we run it longer, new behavior emerges. Let's run it for 50 iterations, and specify a smaller scale parameter (5 instead of the default 10) so the plot still fits on the screen: ca1d(122,61,50,____,5). This new pattern will eventually repeat. How many generations does it take for the pattern to repeat? You will have to run the rule for more iterations to answer this question.

    Part II

  5. (3 pts) For part II of this assignment, you will work on a module in the Online Learning Initiative at CMU that will teach you about a new topic called encryption. This module will help you learn the basics about encryption before we cover this topic in class next week. The module is designed so we can focus in class on the parts of the topic that you find more difficult, which in turn will hopefully maximize your learning for this topic.

    In order to get credit for this part, you must complete the module by the deadline for the problem set. We will not be grading you on how many questions you get right in the module. Instead, we will be grading you on whether you completed the module on time or not.

    To access the Encryption module:

    1. Go to this URL: https://oli.web.cmu.edu/ and click on the "Sign in" link in the upper right.

      We assume that you have registered before. If you have not, please revisit the instructions in Part II of Programming Assignment 7.

    2. Follow the instructions on the My Courses page to get started on Module 2: Encryption.

    3. You don't have to do then entire module in one sitting; you can leave the web site and resume work on it later. But you must complete the module by the submission deadline for this assignment.