15110 Fall 2012 [Touretzky/Kaynar]
Problem Set 9 - due Monday, November 5 in class
Read Chapter 9 of the textbook Explorations in
Type or neatly write the answers to the following problems.
Please STAPLE your homework before you hand it in.
On the first page of your homework, include your name,
andrew ID, lab section (A-N), and the assignment number.
You must hand in your homework at the start of class on the given due date.
- (2 pts) Random number generation.
- 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.
- Now suppose that c = 23 instead of 7. What do you observe? Then
try c = 39. What can you conclude from your observations?
- 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 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.
return rand(6) + 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
- 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
- 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:
return rand(11) + 2
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
- 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
- (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
- 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).
- Show the graphical notation for your rule using the eight
T-shaped figures you saw in the OLI module and again in the
Write down the eight bit binary code for your rule and the
equivalent decimal rule number.
- (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.
- Draw the graphical representation of this rule as eight T-shapes.
- 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 . 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.
- What does the resulting shape look like?
- 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.
- (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:
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.
Follow the instructions on the My Courses page to get started
on Module 2: Encryption.
- 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.