Comp 150 exam 1 study guide   Dordal, Feb 17, 2006    Exam is Wed, Feb 22

PRELIMINARY VERSION

Sections of Analytical Engine:
Section 6.2:
    Binary representation of numbers
        ASCII representation of characters
    Encoding instructions
    PIPPIN Assembler - first look
        Some PIPPIN programs
Section 6.3: omit
Section 6.4:
    Parsing, and building parse trees
    Generating code from expressions
    
Topics:
    binary numbers
    PIPPIN code (you will be given the summary below)
    Logic & Gates
    
    
    
Review questions, p 271: #5

End-of-chapter exercises, p 272:
1	convert binary to decimal
2	convert decimal to binary
5	binary numbers that are all 1's: eg 1111, 11111111111
6	Adding a 0 to a binary number: 1101 -> 11010, etc
10	PIPPIN tasks: (a) swap, (b) compare
11	PIPPIN: X = X/2
14revised: Python terminates def, while, for, if lines with ":". 
What would happen if we eliminated these colons from python?
15	Draw parse trees
16	describe code generation

Section 7.2: 
	Logic, p 280; truth-tables
	Gates, p 283
Section 7.3: 
	more complex circuits (none will appear directly on the exam)
Section 7.4:

End-of-chapter exercises, p 308:
6	find logic table. that is, for inputs 
	(a,b) = (0,0), (0,1), (1,0), (1,1), find respective output x
8	three-input AND, three-input OR
9	majority circuit: 3 inputs: output is 1 <===> at least 2 inputs are 1
15	pipelining

    


Sections of Python:

There will be NO python functions to write on the exam.
You will, however, be asked to describe the OUTPUT of some simple
python functions. 

The same rule applies to PIPPIN Assembler code: you won't be asked to write
anything more complicated than code for an expression like x*(y+z).
However, you might have to describe the result of executing something
more complicated.

=======================================================================

1. What is the value of s after execution of the following python code:

n=1
s=1
while n<7:
   s = s + n*n
   n = n+2



2. What is the value of L after execution of the following python code:
Note L is a list.

n = 0
L = []
while n < 5:
    L = L + [2*n]
    n = n + 1



3. What is printed by the following:

for i in range(1,5):
    print range(0,i)



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

LOD X		Load the contents of memory location X into A
STO X		Store A at memory location X

JMP Y		Jump to the instruction at address Y
JMZ Y		Jump to Y if A=0; otherwise go on to the next instruction

NOP		Do nothing
HLT		Halt completely

In the following, X alone means to use the contents of the memory location 
at address X; #X means to use the number X itself without referring to memory
ADD X/#X	Add X to A 
SUB X/#X	Subtract X from A 
MUL X/#X	Multiply A by X
DIV X/#X	Divide A by X
AND X/#X	Put into A the logical AND of A and X 


NOT		If A!=0, set A=0. If A=0, set A=1.

CPZ X		if the contents of memory location X is 0, set A=1; otherwise A=0.
CPL X		if the contents of mem loc X is negative, set A=1; otherwise A=0.


5. Give a parse tree for the following expression, and write PIPPIN instructions 
to leave the value of the expression in the accumulator;

    (X+Y)/2


6  Give a parse tree for the following expression, and write PIPPIN instructions 
to leave the value of the following expression in the accumulator. 
Hint: Store (X+Y) in the temporary location T1.
Unlike the previous example, this one cannot be done without temporary storage.

    12/(X+Y)	


7. Give parse trees for each of the following expressions.
    (X+Y)*(X+2)
    X*Y + 3*Z*(W+1)

8. Assume that the location P is initially 1, and N is initially 5.
Give the value in P at the end.

	LOD N
START:	JMZ END		# jump to END if Acc == 0
	MUL P		# multiply Acc by P
	STO P
	LOD N		# load the original N again
	SUB #1
	STO N
	JMP START
END:	HLT


8. Give the output of the following for all inputs.

x----+------+ 
     | NAND |--+
y----+------+  |
               +----+------+
                    | NAND |--output
z-------------------+------+


x  y  z  |  output
0  0  0  |  
0  0  1  |  
0  1  0  |  
0  1  1  |  
1  0  0  |  
1  0  1  |  
1  1  0  |  
1  1  1  |  

The table for one NAND gate is as follows:

x  y  output
0  0   1
0  1   1
1  0   1
0  0   0