15110 SUMMER SESSION TWO - 2014

Problem Set 8 - due Wednesday, July 23 at 9:00AM in class

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)
1. For the following Boolean expression, write a truth table that shows the value of the function for each possible combination of assignments to the boolean variables X, Y, and Z. Use 1 for true and 0 for false.
```
(X and Y) or (Y and (not Z))
```
2. The programming language Ruby also has a while loop that works similarly to the one in Python.
```
i = 0
sum = 0
while i != 10 do
    sum = sum + i
    i = i + 1
end
```
  Ruby has another loop called an until loop that runs until a particular condition is true. For example, the loop above can be written equivalently by negating the loop condition and using until instead of while:
```
i = 0
sum = 0
until i == 10 do
    sum = sum + i
    i = i + 1
end
```
  Use DeMorgan's Law to convert the following Ruby while loop to an equivalent until loop.
```
while (x >= 40) and (x < 68) do
   ...
end
```
(2 pts) Another way to represent unsigned integers is to use a representation called Binary Coded Decimal. In this representation, each decimal digit of an integer is represented using 4 bits as follows:
```
0     1     2     3     4     5     6     7     8     9
0000  0001  0010  0011  0100  0101  0110  0111  1000  1001
```
Let ABCD represent a 4-bit binary-coded decimal number as described above. For example, the decimal digit 7 is represented in binary-coded decimal as 0111, so in this case, A = 0, B = 1, C = 1, and D = 1.
A seven-degment display can be used to display each of the ten decimal digits as shown below.

We can define a circuit abstractly below that requires four Boolean inputs A, B, C, and D represent a decimal digit encoded in binary-coded decimal format, and seven Boolean outputs s₁, s₂, ..., s₇ to control each segment of the display:

A segment s_i is lit if s_i is 1 (true) and not lit if s_i is 0 (false).
1. Derive a Boolean formula for s₅ that is true (1) if and only if segment s₅ is lit.
  Your answer should be of the following form:
  s₅ = (________) ∨ (________) ∨ (________) ∨ ...
  where each missing section is a boolean expression with all 4 input variables that is true when ABCD represents a decimal digit that results in the segment s₅ of the display being lit. To help you get started, the digit 0 (binary 0000) will light segment s₅, so the first expression in the formula above would be
  (¬A ∧ ¬B ∧ ¬C ∧ ¬D)
  since s₅ would be true (i.e. 1) if A = 0, B = 0, C = 0, and D = 0. You will need to find all of the other missing expressions for s₅.
2. Derive a simple Boolean expression for s₆ that is true (i.e. 1) if and only if the segment s₆ is lit. (HINT: Segment s₆ is lit for all digits except when the digit is the number 2.)
(2 pts) A simpler adder is called a half adder which only adds 2 bits (X and Y) to produce a sum bit (S) and a carry_out (C) bit, as shown in the following truth table:
```
 X  Y  |  C  S
---------------
 0  0  |  0  0
 0  1  |  0  1
 1  0  |  0  1
 1  1  |  1  0
```
This adder can be represented abstractly using the following diagram:
1. Give Boolean formulas for C and S as functions of X and Y.
2. Using two half-adders represented abstractly as boxes and one OR gate, show how to build a full-adder as defined in class. Your picture should have three inputs, X, Y, and Carry_In and two outputs, S and Carry_Out.
(1 pt) When a programmer writes a program in a high-level language (e.g. Python), we need an interpreter or a compiler in order to execute the program on a computer. Explain why.
(2 pts) This question deals with generating random numbers using a linear congruential generator.
1. A linear congruential random number generator is created with a = 5, c = 9, 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. Consider a pseudo random number generator based on the linear congruential method with a = 81, c = 337 and m = 1000. Using python3 and RandomLab, generate a set of 20 random numbers from this generator. Try this with several different seeds. Look at each sequence of numbers you get. What is the pattern in each of the sequences that would make you question whether you want to use this generator? (HINT: For each sequence, look at the last digit of each number in the sequence.)
(2 pts) Use the Python random randint(0,x) function with two parameters, the first always set to 0, to solve each of the following tasks. Do NOT use any other random number functions in your solutions.
1. Write a Python function spin1() that returns an integer and simulates the wheel spinner from the Milton Bradley game of Life. The wheel contains the numbers from 1 to 10.
2. Write a Python function spin2() that returns an integer and simulates the Showcase Showdown wheel from the Price Is Right game show. The wheel contains the multiples of 5 from 5 to 100.
3. Write a Python function roll1() that returns an integer and simulates a backgammon doubling cube. The 6-sided cube contains the values 2, 4, 8, 16, 32, and 64.
4. Write a Python function roll2() that returns a string and simulates a poker die. The 6-sided cube contains the values "A", "K", "Q", "J", "10", and "9". (You should simulate just one die.)