Comp 150 Midterm Study Guide Answers

Chapter 2

#6: 1110011+11001 = 10001100

#7: 1010101 + 10101 = 1101010

#8: 1111111+11111 =10011110

#26
binary
 octal
 decimal
1011
 13
 11
1100
 14
 12
1101
 15
 13
1110
 16
 14
1111
 17
 15
10000
 20
 16

#29 4 bits of binary convert to a single hex digit
    1010 1001 = A9
    1110 0111 = E7

#30 The easiest way to convert hex to octal is to convert to binary, and then take the bits three at a time:
A9 = 1010 1001 = 10 101 001 = 251octal
E7 = 1110 0111 = 11 100 111 = 347octal
6E = 0110 1110 = 01 101 110 = 156octal

Chapter 3


#40: To form the 2's-complement, flip all the bits and add 1. Note that implicit in this action is a set limit on the total number of bits, in this case 8. Addition is as usual; to subtract you form the 2's complement of the number being subtracted and add.
a: sum is 0000 0000 (with an overflow (carry) bit).
b: B-complement is 11111101; adding 1 gives -B = 1111 1110; A-B = A+(-B) = 1111 1011 (again with an overflow bit)
c: A-complement is 0000 0001; -A is thus 0000 0010; B-A = B+(-A) = 2+2 = 0000 0100
d: -B is as in (b)
e: -(-A) = A, both under arithmetic as usual and under 2's complement. You can verify that, though: -A = 0000 0010; -A-complement is thus 1111 1101, and adding 1 gives 1111 1110, which is A again.


#44
(a). 0.5 = 1/2 = .10000
(b). The short-cut here is to notice that .26 = .25 + .01. The former is 1/4, which is exactly .01000 in binary, and the latter is less than 1/64 = .00000 1, so to five places the answer is .01000.

The long (normal) way is to do binary long division of 26/100 = 13/50 = 1101/110010. Zeros "brought down" are in bold.
           .01000001
       __________________
110010|1101.000000000000000
       1100 10
       -------
       0000 1000000
             110010
            -------
            0001110
      
(c). I just did this the long way; this is 1/10 (decimal) = 1/1010. To five binary digits, the answer is .00011 = 1/16 + 1/32
      .00011001
     __________________
1010|1.000000000000000
       1010
       ----
       01100
        1010
        ----
          10000
           1010

Chapter 4


#43 The Boolean expression is just ABC (or (AB)C if you require that the AND operation be strictly binary). The truth table is
A  B  C  |    ABC
0  0  0  |     0
0  0  1  |     0
0  1  0  |     0
0  1  1  |     0
1  0  0  |     0
1  0  1  |     0
1  1  0  |     0
1  1  1  |     1

#55  A+B means A, B are inputs to an OR gate; (A+B)(B+C) means that the outputs of the OR gates for A+B and B+C are the inputs to an AND gate.

Note that there should be no "thinking" involved here; the circuit is really just the "parse tree" for the expression. That is, converting a Boolean expression to a circuit is just a matter of starting with the "innermost" operations and working outwards. (Converting a truth table to a circuit, at least an efficient circuit, can be a lot more work.)

A-----+
      OR----+
   +--+     |
B--+        AND----
   +--+     |
      OR----+
C-----+

#56 First we put A and B into an AND gate to get AB, then OR with C to get AB+C, and then the output of that goes into an AND gate with D to get (AB+C)D.

A---+
B---+AND--+
C---------+OR---+
D---------------+AND---

#57  (note 9 should be '; that is; A'B + (B+C)' )

I'll do this one descriptively, thinking of the gates as organized into left-to-right columns. In the first column, there is a NOT gate with input A and output I'll call T1. There is also an OR gate with inputs B and C, with output T2.

In the second column there is an AND gate with inputs T1 (=A') and B, with output T3, and a NOT gate with input T2=B+C and output T4.

In the final third column there's a single OR gate with inputs T3 = A'B and T4=(B+C)'. The output of that final gate is the output of the circuit.


#59 In this table, T1 is the output of the AND gate (blue), and T2 is the output of the first OR gate. In these kinds of problems, it is often easier to keep track of what you're doing if you write down these intermediate columns. Note that the output is identical to that of a single OR gate.

A
 B
 T1
 T2
 OUT
0
 0
 0
 0
 0
0
 1
 0
 1
 1
1
 0
 0
 1
 1
1
 1
 1
 1
 1


#60 T1 = A' is the output of the NOT gate, and T2 = AB is the output of the AND gate. These are the inputs to the final XOR gate.

A
 B
 T1
 T2
 OUT
0
 0
 1
 0
 1
0
 1
 1
 0
 1
1
 0
 0
 0
 0
1
 1
 0
 1
 1

Questions in the guide itself


#1 Find s after executing
n=1
s=1
while n<7:
   s = s + n*n
   n = n+2

Here's a tabular approach: row K contains the values of n and s after the loop has executed K times. Row 0 contains the initial values.
K
 n
 s
0
 1
 1
1
 3
 2
2
 5
 11
3
 7
 36


#2 What is the value of L after execution of the following python code?  Note L is a list. (This one is harder than #1)
 
n = 0
L = []
while n < 5:
    L = L + [2*n]
    n = n + 1
 
Each time through we add 2*n to the end of the list L. We start at n=0, and proceed through n=1,2,3,4. The final list is thus
    L = [0, 2, 4, 6, 8]

#3What is printed by the following:
 
for i in range(1,5):
    print range(0,i)
   
Each print statement gets its own output line. The values for i are 1,2,3,4, so there are four lines. Each line is a list of numbers, starting at 0 and going up to but not including i:
    [0]
    [0, 1]
    [0, 1, 2]
    [0, 1, 2, 3]


#4. What is string t after the following?
t = ""
s = "foobar"
for i in range(len(s)):
    t = t + s[i]

i ranges through 0,1,2,3,4,5. We add successive letters of s to the end of t, which leaves us with the same string!
    t = "foobar"

#5 Write PIP code to calculate 1+A*(2+B*(3+C))

There are several ways to do tihs, but here is a way that doesn't require any TEMP variables, by starting at the right end. It does make use of the fact that order does not matter for multiplication or addition. This is true even for computer multiplication and addition, but perhaps not entirely obvious.

    LOD   C
    ADD #3
    MUL B
    ADD #2
    MUL A
    ADD #1

#6 Suppose the following PIP code is run. What will be in the accumulator at the end? (Hint: A is decremented by 1 each time through; B is increased by 2*A each time through.)

            LOD #5
            STO A
            LOD #10
            STO B        
;; at this point, A=5 and B=10. At the top of the loop, the accumulator will always contain the value of B (since it does when the loop is first started, and since the last thing done in the loop before branching back to the top is to reload B into the accumulator)..

LOOP: ADD A
             ADD A    ;; yes, twice
             STO B         ;; now B = B+2*A
             LOD A
             SUB #1
             STO A         ;; now A = A-1
             JMZ DONE   ;; if A==0, quit
             LOD B
             JMP LOOP
DONE:  HLT
    
Here's a table like the one above for Problem 1; one line per time through the loop. K counts how many times we've gone through the loop; the values of A and B are as of the end of that round (when K=0, they represent the initial values).

K
 A
 B
0
 5
 10
1
 4
 20
2
 3
 28
3
 2
 34
4
 1
 38
5
 0
 40

Another way to look at B is that it's 10 + 2*5 + 2*4 + 2*3 + 2*2 + 2*1.

#7 Give the output of the following for all inputs.
 
x----+------+ 
     | NAND |--+
y----+------+  |
               +----+------+
                    | NAND |--output
z-------------------+------+
 
 
x  y  z  |  1st output    final output
0  0  0  |       1             1
0  0  1  |       1             0
0  1  0  |       1             1
0  1  1  |       1             0
1  0  0  |       1             1
1  0  1  |       1             0
1  1  0  |       0             1
1  1  1  |       0             1
 
Note that I added an intermediate column; you should too, if it makes it easier to do the problem.
    

#8Write a python function to multiply all the numbers in a list L:
 
def mulnums(L):
    prod = 1
    for x in L:
        prod = prod * x
    return prod

#9 (We never did get to an example like this in class; I'd intended to). Suppose we define
    def isOdd(n):
       if n % 2 == 1: return True
       else: return False

    def filter(L):         # L is a list of numbers
       res = [ ]
       for x in L:
          if isOdd(x): res = res + [x]
       return res

What is returned by filter([1, 2, 4, 5, 7, 12, 16, 17])?

Filter keeps x in the list if isOdd(x) was true; that is, if x was odd; the evens are not included in the output. The output is:
    [1, 5, 7, 17]