Sunday, December 16, 2012

CS 151 hw solutions



https://docs.google.com/folder/d/0Bx7eKFQAo1e-bTNDcDRWN2NVQ2c/edit


(a) Prove that if n is an integer and 3n + 2 is even then n is even, using a proof by:........


As you well know, I have a perfectly rectangular back yard.
First it all had only grass growing in it. I have decided to get creative and plant some
flowers in half of it. So I split my back yard exactly in half (cutting the long edge
in half) and planted flowers on one half, leaving the other with grass. I liked it, so
I decided I wanted tomatoes and maybe cucumbers, and perhaps some peppers. To
create new plots, I always split the grass plot in half, always cutting the long edge. Let
pn be the number of plots in my back yard after n splits.
.........................

Say precisely what’s wrong with each of the following proofs by identifying
the first sentence that does not follow from previous statements. (I’m looking for an
answer like “2+3 is not 4” and not “you didn’t say what variable you were doing
induction on”—you should explain why the proof is wrong, not why it’s badly written,

The cases in the inductive case aren’t exhaustive. When n = 5, the (n − 1)-cent
stamp pile is just a single four-cent stamp (so it doesn’t include either a three-cent
stamp or two four-cent stamps). If you....etc

(b) Suppose you are searching through k websites w1 , w2 , w3 , ..., wk , and each website
contains many pages: site wi contains pi pages. For example, the website www.cs.
uic.edu contains

A cellular automaton is a formalism that’s sometimes used to model complex systems—
like the spatial distribution of populations, for example. Here is the model, in its
simplest form. We start from an n-by-n toroidal lattice of cells: a two-dimensional
grid, that “wraps around” so that that there’s no edge. (Think of a donut.) Each cell
is connected to its eight immediate neighbors.


Suppose a code is needed to encode 30,000 items. A codeword is a string of characters
from an alphabet of 5 letters. If all codewords are the same length, what is the smallest
length those codewords can be? Explain.
https://docs.google.com/folder/d/0Bx7eKFQAo1e-bTNDcDRWN2NVQ2c/edit



logic and computer design quiz 2



Given the following diagram, what's the maximum number of states represented by this sequential diagram.

Correct Answer:      4


Number (10101010)2 is in signed-magnitude representation. What is this number on signed 2s complement representation?

 Answer: 11010110



What is the result of the following subtraction:
-69-15
Assume 8-bit signed 2s complement numbers.
 Answer: c. 10101100


The following truth table represents the formulation of a circuit to convert 3-bit gray code to binary code. What are the inputs for the dual 4-to-1 MUX implementation of outputs Y and Z as seen below? (listed in order from D00 to D03).
Gray Binary
A B C X Y Z
0 0 0 0 0 0
1 0 0 0 0 1
1 1 0 0 1 0
0 1 0 0 1 1
0 1 1 1 0 0
1 1 1 1 0 1
1 0 1 1 1 0
0 0 1 1 1 1
 Answer:     c. Y Mux: C, ~C, C, ~C Z Mux: C,~C,~C,C


Which of the following options result in overflow (in 2s complement with 8-bit).
 Answer: b. 10111010 + 10110001




Given the following circuit what is the correct equation for D A?



Answer:     b. DA=XB+YA



For a one bit full-adder, X and Y are two bits to be added, and Z is the carry in from the previous lower significant position. What's the equation for carry cout Cout?
Answer
Selected Answer: d. Cout(X, Y, Z) = Σm(3, 5, 6, 7)


Given a half adder whose sum is expressed as a sum bit S and a carry bit C, which of the following is an incorrect equation for the half adder?
Answer
Answer: e. S= (~X+Y)+(X+Y) C=XY



  Given that a state diagram has 2 inputs and 6 states (outputs can be ignored), what is the largest number of arcs that will appear in the entire diagram (not just on one state)?
Answer
 Answer: b. 24




What is the minimum number of flip-flops that you may need for the sequential circuit that may have 209 different states?
Answer
Correct Answer: 8


Given the following function F and don't care conditions, what's the simplification form of F?
F(A ,B, C, D) = Σm(3, 4, 13, 15)
d(A, B, C, D) = Σm(2, 5, 8, 10, 12, 14)
Answer
Answer: c. B~C + AB + ~A~BC


What is the minimum number of outputs that encoder with 145 inputs should have?
Answer
 Answer: 8
Answer range +/- 0 (8 - 8)



What is the indication of overflow when adding two 2s complement encoded numbers?
Answer
Answer: a. the carry into the sign bit position and the carry out of the sign bit postion are not equal


Which of the following hexadecimal numbers are representable by 8-bit 2s complement.
Answer
 Answers: b. -80



With signed numbers, overflow cannot occur for an addition of two negative numbers.
Answer
Answer: False


 How many different signed integers can be represented with 16 bits using 2s complement representation?
Answer
Answer: a. 216


 What is the literal cost of the following equation:
F = (AB) + (CD~E) + (~A~B~C)
Answer
Answer: c. 8

How many D flip-flops at least do you need to construct a sequential circuit with 5 states, 3 inputs and 1 output?
Answer
 Answer: b. 3







logic and computer design quiz 1


 Question 1
Convert Binary (10111001010110.0111)2 to Octal.
Answer
Selected Answer: 27126.34
Correct Answer: 27126.34
Answer range +/- 0.00 (27126.34 - 27126.34)



 Question 2
In BCD Addition, if the sum is greater than 1001, we add ____ to obtain the correct BCD digit sum and carry.
Answer
Selected Answer: d. 0110
Correct Answer: d. 0110



 Question 3


Choose the correct output of a three-state buffer given the following inputs.
Note: in case if you see 2 images discard one.
Answer
Question Correct Match Selected Match
AB = 11 b. 1 b. 1
AB = 10 a. Hi-Z c. 0
AB = 01 c. 0 b. 1
AB = 00 a. Hi-Z a. Hi-Z




Question 4

Find the complement of the following expression:
A(~B)C+(~A)B
Note: ~ denotes NOT.
Answer
Selected Answer: a. (~A+B+~C)(A+~B)
Correct Answer: a. (~A+B+~C)(A+~B)



Question 5
0 out of 5 points
The dual of the expression is obtained by :
Answer
Selected Answers: a. interchanging OR and AND operations and replacing 1s by 0s and 0s by 1s.
d. replacing 1s by 0s and 0s by 1s

Correct Answers: a. interchanging OR and AND operations and replacing 1s by 0s and 0s by 1s.
d. replacing 1s by 0s and 0s by 1s




Question 6
5 out of 5 points
Multiply Binary 101 X 010. Answer in binary.
Answer
Selected Answer: 1010
Correct Answer: 1010



Question 7
5 out of 5 points
How many bits are required to represent decimal 187 as an unsigned integer.
Answer
Selected Answer: b. 8
Correct Answer: b. 8



Question 8
5 out of 5 points
Determine the radix r in the following equation:
(765) r = (1893) 10
Answer
Selected Answer: 16
Correct Answer: 16



Question 9
5 out of 5 points
What is the gate input cost of the following function (assume complemented and uncomplemented literals are available):
F = (AB) + (CD~E) + (~A~B~C)
Answer
Selected Answer: 11
Correct Answer: 11
Answer range +/- 0 (11 - 11)



Question 10
5 out of 5 points
Simplify: AC+(~A)C+B(~C)+(~B)(~C)
Answer
Selected Answer: 1
Correct Answer: 1
Answer range +/- 0 (1 - 1)



Question 11
5 out of 5 points
The following truth table is that of which logic-gate type.
A B F
0 0 1
0 1 1
1 0 1
1 1 0
Answer
Selected Answer: NAND
Correct Answer: NAND



Question 12
5 out of 5 points
What is the standard form of the following function:
F = AB + ~B~C
Note: ~ denotes NOT
Answer
Selected Answer: d. ~A~B~C+A~B~C+AB~C+ABC
Correct Answer: d. ~A~B~C+A~B~C+AB~C+ABC



Question 13
5 out of 5 points
What is the result of Binary addition:
101001
+ 1101111
Answer
Selected Answer: 10011000
Correct Answer: 10011000
Answer range +/- 0 (10011000 - 10011000)



Question 14
5 out of 5 points
An Inverter
Answer
Selected Answer: d. All of them
Correct Answer: d. All of them



Question 15
5 out of 5 points
Optimize the following Boolean function F by using a three-variable K-map:
X Y Z F
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
Answer
Selected Answer: c. ~Z
Correct Answer: c. ~Z



Question 16
5 out of 5 points
Given the following function F and don't care conditions, what's the simplification form of F F (A,B,C,D) = Σm(1, 3, 7, 11, 15) d(A,B,C,D) = Σm(0, 5)
Answer
Selected Answer: a. ~AD + CD
Correct Answer: a. ~AD + CD



Question 17
5 out of 5 points
How many error bits could there be in the following data with even parity?
data: 1010
parity: 0
Answer
Selected Answers: b. 4
d. 2
e. 0

Correct Answers: b. 4
d. 2
e. 0




Question 18
5 out of 5 points
How many entries are there in a truth table of 5 variables?
Answer
Selected Answer: 32
Correct Answer: 32



Question 19
5 out of 5 points
The function E(x,y,z) = Σm(1, 2, 4, 5). What are the minterms of complement of E?
Answer
Selected Answer: Σm(0, 3, 6, 7)
Correct Answer: Σm(0, 3, 6, 7)



Question 20
5 out of 5 points
Convert Binary 1101001.011 to Decimal.
Answer
Selected Answer: 105.375
Correct Answer: 105.375
Answer range +/- 0.000 (105.375 - 105.375)




Sunday, December 16, 2012 12:21:37 PM CST