15110 SUMMER SESSION TWO - 2014

Problem Set 9 - due Monday, July 28 at 9:00AM in class

Reading Assignment

Read chapter 4 of the book Blown To Bits, pages 109-137. (Feel free to read the whole chapter if the material interests you.)

Instructions

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, and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(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.
```
from random import *

def roll1():
    return randint(1,6)     # simulate a roll of a six-sided die

def roll2():
    return randint(1,6)     # simulate a roll of a six-sided die

def simple_game():
    total = 0
    for i in range(1,11):
        if roll1() != roll2():
            total = total + roll1() + roll2()
        else:
            total = 0
    return total
```
(1 pt) Assume that the random number generator randint(m,n) is uniformly distributed. This means that the probability of generating any number between m and n is the same.
Suppose that Alice simulates the roll of a pair of dice by defining the roll function below, calling it twice and adding the results:
```
def roll():
    return randint(1,6)
```
Bob realizes that the roll of a pair of dice results in a sum of 2 through 12, inclusive, so he simulates the roll of a pair of dice by defining the roll function below, calling it only once:
```
def roll():
    return randint(2,12)
```
Are these equivalent in terms of their behavior over time as we generate roll after roll? Why or why not?
(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?
(1 pt) An image is simply a list of lists of lists of RGB values. For example, here is a 3 X 2 image consisting of a red and green pixel in the top row, a blue and white pixel in the middle row, and two black pixels in the bottom row:
```
[ [ [255,0,0] , [0,255,0] ],[ [0,0,255] , [255,255,255] ],[ [0,0,0] , [0,0,0] ] ]
```
We can remove the red components of an image using the following function in Python:
```
def remove_red(image):
    num_rows = len(image)
    num_columns = len(image[0])
    for row in range(0,num_rows):
        for column in range(0,num_columns):
            green = image[row][column][1]
            blue = image[row][column][2]
            image[row][column] = [0, green, blue]
    return None
```
It is possible to accelerate the performance for the remove_red function by modifying it to perform the work on the different pixels concurrently instead of following the ordering given by the loops. Could the same be done for the problem of implementing a function that returns an array of n pseudorandom numbers generated using a linear congruential generator? Why or why not?
(2 pts) A sorting network can also be drawn as a wire diagram, as shown below for a 6-element sorting network. Data enter from the left along the 6 horizontal lines and exit toward the right. Each vertical line represents a comparator with its inputs coming in from the left and outputs being sent out to the right. When two data values reach a comparator, they swap positions if the top value of the comparator is greater than the bottom value of the comparator.
1. Trace the operation of this sorting network on the inputs 8, 2, 9, 3, 0, 7 (from top to bottom). For each comparator write down the two numbers that leave the comparator to the right of the comparator, one per wire. For example, for the first comparator, it compares the 8 and 2 (which need to be swapped), sending out 2 along the top wire and 8 along the bottom wire. For the second comparator, it compares 8 and 9, sending out the 8 along the top wire and 9 along the bottom wire. Complete the rest of the wire diagram to show that this network sorts these 6 values.
2. In general, which comparisons in this diagram can be performed concurrently?
3. How many steps does it take to sort concurrently? How does this compare to the number of steps needed if we did each comparison sequentially (i.e. one at a time, non-concurrently)?
4. Do you recognize the sorting algorithm? What is it?
(1 pt) At a university, a student club wants to send out an individualized invitation letter to 1000 faculty for an upcoming donor event. Each letter requires the following steps, in order:
```
1. Write a personal message to the faculty member on the inside of a card 
   (10 minutes).
2. Hand draw a scene with the club logo on the cover of the card with 
   colored pencils. (15 minutes)
3. Cut out and form a special envelope for the card out of a sheet of 
   premium paper. (3 minutes) 
4. Seal the card in the envelope with glue, look up and write the address 
   of the faculty member, and put a stamp on the card. (2 minutes)
```
1. If the club utilized the principle of pipelining and had four work stations, one for each step above, and one person to work at each workstation, how many minutes would it take to complete the 1000 invitations? How does this compare to one person completing the entire task? Show your work.
2. Can this task be completed even faster with four people concurrently? If so, explain how and compute the total amount of time needed to complete the task. If not, explain why.
(1 pt) Consider the following sorting network you saw in class:

Assume each comparator (i.e. the circles) takes time t to compare its two elements and output its results and that the time for a data value to go from one comparator to the next negligible. We wish to sort 1000 sets of 6 integers each.
1. If we sort one set of 6 integers completely before starting the next set, how long will it take to sort the 1000 sets in terms of t? Explain your answer. (Remember that some of the comparators are operating concurrently.)
2. If we use the principle of pipelining, how long will it take to sort the 1000 sets in terms of t? Explain your answer. (NOTE: To simplify the problem, assume there are some dummy comparators inserted into the network as shown below so that all results arrive at the output terminals at the same time.)
(1 pt) In the Blown To Bits reading, you learned how Google handles a search query for the World Wide Web. Describe one way how Google uses concurrency (parallelism) based on your reading. Be specific.