15110 Spring 2012 [Cortina/von Ronne]

Problem Set 9 - due Friday, April 6 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, lab section (A-N), and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(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) Assume that the random number generator rand(n) is uniformly distributed. This means that the probability of generating any number between 0 and n-1 is the same.
Suppose that Alice simulates the roll of a pair of dice by defining the roll function below, calling it twice:
```
def roll()
    return rand(6) + 1
end
```
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 rand(11) + 2
end
```
Are these equivalent in terms of their behavior over time as we generate roll after roll? Why or why not?
(1 pt) Consider three programs running simultaneously, each wanting access to the same three databases. When a program accesses one database, it locks it so another program cannot use it. Once the program is done using the database, it unlocks the database. If a program tries to access a database and it is locked, it waits until it is unlocked. Explain how deadlock can occur for these three programs.
(2 pts) An operating system is a program that controls the operation of a computational device (computer, cell phone, game console, etc.).
1. An operating system contains a component called the kernel as shown below.
  
  (http://en.wikipedia.org/wiki/File:Kernel_Layout.svg)
  What role does the kernel play? (You may look this up online and quote any reliable source you find, citing where you got the information. But if you quote from a website, you should still summarize what you quoted in your own words. Don't just copy someone else's words without thinking about what they mean.)
2. Briefly explain how the operating system uses the principle of multitasking to run a number of programs "concurrently" on a device with a single processor.
(1 pt) An image is simply an array of arrays of arrays 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 Ruby:
```
def remove_red(image)
  num_rows = image.length
  num_columns = image[0].length
  for row in 0..num_rows-1 do
    for column in 0..num_columns-1 do
      green = image[row][column][1]
      blue = image[row][column][2]
      image[row][column] = [0, green, blue]
    end
  end
  return nil
end
```
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) 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.