CPS 1 (Ramm)                         Page 1 of 8

2 May              	Spring Semester,  1995			Section _____

CLOSED BOOK                   Final Exam             NAME____________________

A.(4) Below are three examples of networking addresses.  Draw	    (4)
lines between the name and its description. 			    A	_____

  An Ethernet address		teer13.acpub.duke.edu	            (6)
  An IP computer address	b3:fe:13:21:a5:41		    B	_____
  A domain computer address	152.140.9.15 
					 			    (4)
	                       		 			    C	_____
B.(2) Communications packets are 100% efficient in that they
  contain only data. (True/False?)         			    (6)
								    D	_____
  (2) Computers never have more than one Ethernet controller. 	    
  (True/False?)							    (3)     
		                        			    E	_____ 
  (2) Each Ethernet controller in the world has a unique	
  communications address. (True/False)				    (2)
								    F	_____

C. (4) Add the following binary numbers and give their sum in	    (20)
   binary:  							    G	_____
				1 1 0 1 0 1 1 1			  
			      +	1 1 1 1 0 1 0 1			    (5)
				---------------			    H	_____
					
			                       			    (35)
				 				    I	_____
D.(4) Say you are told that a disk has 8 tracks per cylinder,
  100 cylinders, and 10,000 bytes per track, how much data can      (10)
  this disk hold? 						    J	_____
                   ----------					    
								    (10)
  (2) How many recording surfaces would the disk described	    K	_____
  above have?
              ----------					    (5)
								    L	_____

E.(3) An operating system (such as UNIX) can allow multiple users   (5)
to share computing resources.  Circle the items below that an	    M	_____
operating system manages to allow sharing.
								    (25)
    	    keyboard          monitor		memory              N	_____

			cpu	     disk_space			    (20)
								    O	_____
						
								    (15)
F.(2) In proving that the halting problem is non-computable,	    P	_____
we used the following proof technique: (circle one)
								    (15)
induction	contradiction	   deduction     abstraction	    Q	_____

								    (10)
								    R	_____
								    ---------
                                 Final Exam                       Page 2 of 8

G.(5) Below is the first part of a Pascal program.  Assume that it reads in
the numbers shown to the right of the program.  Show the contents of
array t by writing the numbers in the box below representing t in memory.

							DATA
program ara;					|	1.0
type						|	15.0
	t10 = array[1..10] of real;		|	13.0
var						|	8.0
	t: t10;					|	15.0
	i, j, n, num: integer;			|	16.0
	x, total: real;				|	15.0
begin						|	14.0
n := 10;					|	15.0
i := n;	 {NOTE CHANGE!!!}			|	2.0
while i > 0 do					|
	begin					|
	writeln('Enter Data:');			|
	readln(t[i]);
	i := i - 1;  {NOTE CHANGE!!!}
	end;
			   1    2    3    4    5    6    7    8    9   10
			 ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
		    t	|    |    |    |    |    |    |    |    |    |    |
			 ---- ---- ---- ---- ---- ---- ---- ---- ---- ----



     (Note, even if you made an error in F. above, G. will be graded using
     the data you show in the boxes for t.)
(15) Assume that the program above continues with the code that follows.
     What output does it produce?

	i := 0;
	total := 0.0
	x := 15.0;
	num := 0;
	while i < n do
		begin
		i := i + 2;  {NOTE CHANGE!!!}
		if t[i] = x then
			begin
			num := num + 1;
			end;
		total := total + t[i];
		end;
	writeln('sum = ', total:5:1);
	writeln('number of ', x:5:1, ' values = ', num:5);
	readln;
	end.








                                 Final Exam                       Page 3 of 8

H.(5) What OUTPUT will the following program print?

						    OUTPUT 
					---------------------------------
	program one;
	var
		i: integer;
		c: string;
	begin
	i := 2;
	c := 'X';
	while i > 0 do
		begin
		c := c + '##' + c + '**';
		i := i - 1;
		writeln(i, ' ', c);
		end;
	writeln(i);
	end.



I.(35) On the back of the previous page, write a subroutine called ARRAYSTUFF
which counts the number of negative values stored in a real array AND
adds together all of the positive values in that array.

Assume you have declarations such as

	type
		realara=array[1..100] of real;
	var
		data:realara;
		size: integer;
		numneg: integer;
		sumpos: real;

Then invoking your procedure with

	{code to get values into the array named data}
	size := 90;
	arraystuff(data, size, numneg, sumpos);
	writeln(numneg, ' negative numbers');
	writeln('positive numbers adding up to ', sumpos:5:1);

should write out the number of the first 90 elements in the array with
negative values and report on the sum of all of the positive numbers.
Make the order of your parameters match this example.
JUST WRITE THE PROCEDURE, DON'T REPEAT THE DECLARATIONS SHOWN ABOVE (just
use them).  (You do not have to worry how the data got into the array in
the first place.)








                                 Final Exam                       Page 4 of 8

J.(10) Assume that we have a database describing computers owned by writers
with the following entries.  Assume that you are dealing with a program of
the type discussed in the text or covered in the lectures.
	Clarke	Zenith	4Meg	VGA
	Asimov	IBM	2Meg	VGA
	Niven	Zenith	4Meg	CGA
	Hogan	Zenith	4Meg	SVGA
	Anthony	IBM	4Meg	VGA
	Gibson	Zenith	2Meg	SVGA
	Niven	IBM	2Meg	SVGA
Assume that the following query was typed into this program:
?
Zenith
4Meg
?
What (if any) output is produced?


Assume that the following query was typed into this program:
Niven
?
?
VGA
What (if any) output is produced?


K.(10) Say that we run a program for several different amounts of data
(represented by N) and get the following timing results:
	N	t
	10	2000ms
	20     16000ms
	30     54000ms
	40    128000ms
Give the formula that describes the execution time behavior.

	t = _____________________


L.(5) Assume we have another program which we run for several values of N.
We notice that every time we double N, it takes only a bit longer to run.
Circle those of the following terms that we might use to describe the
behavior of the program and it's underlying algorithm.

exponential	polynomial	logarithmic	intractable


M.(5) Say that we run a program for several different amounts of data
(represented by N) and get the following timing results:
	N	t
	20	20s	
	30	200s	
	40	2000s    
	50	20000s   
Circle one of the following terms that we might best use to describe the
behavior of the program and it's underlying algorithm.

exponential	polytheistic	logarithmic	tractorable

                                 Final Exam                       Page 5 of 8

N.(25) Given the following Rules:
--------------------------------------------------------------------------
Name	Syntax				Semantics
--------------------------------------------------------------------------

R1: 	<i>j -> w			M(<i>j) = w
	where w = //a sequence of letters//

R2: 	<e>i -> <i>j			M(<e>i) = M(<i>j)
					code(<e>i) = //nothing//

R3: 	<s>k ->  <i>j := <e>i		code(<s>k) = 	code(<e>i)
							COPY AX,M(<e>i)
							COPY M(<i>j),AX

R5: 	<e>i -> ( <e>j * <e>k )		M(<e>i) = createname
					code(<e>i) = 	code(<e>j)
							code(<e>k)
							COPY AX,M(<e>j)
							MUL  AX,M(<e>k)
							COPY M(<e>i),AX

Use the rules to show the syntactic derivation of Z:=(F * A) while also
creating the semantic rules as was shown in the book.  (Do not complete
the job by using those semantic rules to actually produce code.)
The first two line have been completed below.

-------------------------------------------------------------------------------
Derivation		Rules
-------------------------------------------------------------------------------
(1) <s>1		R3: <s>1 -> <i>2:=<e>3	  code(<s>1) = code(<e>3)
							       COPY AX,M(<e>3)
							       COPY M(<i>2),AX
(2) <i>2:=<e>3		R1: <i>2 -> Z		  M(<i>2) = Z
























                                 Final Exam                       Page 6 of 8

O.(20) Do a trace for the program shown below left using the column headings
shown below center.  Assume that the user enters a 5 then a 2 when input
is requested.
			   st#  CF   AX   P   N        st#   CF   AX   P   N  
			    ?    ?    ?   1   0     |

0	in	ax				    |

1	copy	r, ax				    |
				    
2	in	ax				    |

3	copy	n, ax				    |

4 #L0	cmp	ax, #c1				    |

5	jb	#L1				    |

6	copy	ax, p				    |

7	mul	ax, r				    |

8	copy	p, ax				    |

9	copy	ax, n				    |

10	sub	ax, #c1				    |

11	copy	n, ax				    |

12	jmp	#L0				    |

13 #L1	copy	ax, p				    |

14	out	ax				    |

#c1	1

p	1					    

r	0

n	0		CONTINUE IN RIGHT COLUMN ABOVE















                                 Final Exam                       Page 7 of 8
P.(15) ------------------------------------------------------------------------
Derivation		Rules
-------------------------------------------------------------------------------
(1) <s>1		R3: <s>1 -> <i>2:=<e>3	  code(<s>1) = code(<e>3)
							       COPY AX,M(<e>3)
							       COPY M(<i>2),AX
(2) <i>2:=<e>3		R1: <i>2 -> Z		  M(<i>2) = Z
(3) Z:=<e>3		R2: <e>3 -> <i>4	  M(<e>3) = M(<i>4)
						  code(<e>3) = //nothing//
(4) Z:=<i>4		R1: <i>4 -> F		  M(<i>4) = F
(5) Z:=F
-------------------------------------------------------------------------------
Using the rule instantiations shown above to derive Z := F, generate the
code for <s>1 step-by-step as shown in the text.  

code(<s>1) =					by
		
		









































                                 Final Exam                       Page 8 of 8

Q.(15) The circuit shown is the three bit adder discussed in class (without
the control circuits).  Show its use in adding the binary number 110 in the X
register and 011 in the Y register.
SHOW HOW ALL SWITCH AND RELAY CONTACTS WILL BE SET both by entering the
numbers to be added by way of the switch contacts and by the relay magnets
as a result of these actions.  SHOW THE LIGHTS THAT ARE LIT by marking
an X through them.
	
(Show switch contacts that are closed or are left closed with a circle over
them.  Leave switch contacts that are opened or are left open, unmarked.
It will be assumed that all switch contacts that you do not circle are open.)
	





























R.(5) For the truth table shown below, complete the drawing for the
equivalent circuit to the right showing switches in either the open or
closed position.
	X   Y	Z	L
      --------------------
	0   0	0	0
	0   0	1	0
	0   1	0	0
	0   1	1	1
	1   0	0	0
	1   0	1	1
	1   1	0	1
	1   1	1	1

  (5) Give the equivalent logical (Boolean) expression: