CPS 1 (Ramm) Page 1 of 10 30 April Spring Semester, 1996 Section _____ CLOSED BOOK 90 min Final Exam NAME_____________________ Note, if there is any chance that your notes and work might be confused for the answer, circle your answers. If it's ambiguous, it's wrong. (3) (5) A _____ M _____ (6) (5) B _____ N _____ (4) (20) C _____ O _____ (10) (20) D _____ P _____ (3) (15) E _____ Q _____ (4) (9) F _____ R _____ (5) (2) G _____ S _____ (10) (9) H _____ T _____ (5) (3) I _____ U _____ (35) (6) J _____ V _____ (5) (3) K _____ W _____ (10) (3) L _____ X _____ ------------- ----------------------------------------------------------------------------- HONOR CODE I have not received or given any improper help on this exam. (your signature) CPS 1 Final Exam Page 2 of 10 A.(3) Below are three examples of networking addresses. Draw lines between the name and its description. An IP computer address b3:fe:13:21:a5:41 A domain computer address 152.3.184.15 An Ethernet address teer13.acpub.duke.edu B.(2) Communications packets are 100% efficient in that they contain only data. (True/False?) (2) You can use either a domain address or an IP address when using FTP. (True/False?) (2) Each Ethernet controller in the world is supposed to have a unique communications address. (True/False) C.(4) "http://www.cs.duke.edu" is an example of a (circle one): URL HTML FTP DNS D.(5) Give the output of the following program for an input value of 3. OUTPUT program skip; ------------------------ var x:integer; begin readln(x); while x > 1 do begin if (x div 2) * 2 = x then x := x div 2 else x := 3 * x + 1; writeln(x); end; end. (5) What unusual property of this program brought about its use in the text? E.(3) (True/False) When we showed that there were functions that could not be computed, we argued that there were an uncountable infinity of possible programs. F.(4) In doing the proof regarding the feasibility of solving the halting problem, we (select one:) 1) assumed the halting problem was solved. 2) showed that all programs eventually halt. 3) identified programs that do not halt. CPS 1 Final Exam Page 3 of 10 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; | 2.0 type | -1.0 t10 = array[1..10] of real; | 2.0 var | 3.0 t: t10; | 2.0 i, n: integer; | -1.0 wt, x, total: real; | 5.0 begin | 3.0 n := 10; | -1.0 i := n; | 6.0 while i > 0 do | begin | writeln('Enter Data:'); | readln(t[i]); i := i - 1; end; 1 2 3 4 5 6 7 8 9 10 ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- t | | | | | | | | | | | ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- (Note, even if you made an error in G. above, H. will be graded using the data you show in the boxes for t.) H.(10) Assume that the program above continues with the code that follows. What output does it produce? (You may want to trace this. It's a little different.) i := 0; total := 0.0 x := -1.0; wt := 1.0; while i < n do begin i := i + 1; if t[i] = x then wt := wt + 1.0 else total := total + wt * t[i]; end; writeln('wtd-sum = ', total:5:1, ' current wt = ', wt:4:1); readln; end. CPS 1 Final Exam Page 4 of 10 I.(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 + '*' + c; writeln(i, ' ', c); i := i - 1; end; writeln(i); end. J.(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 also adds together all of the negative values stored in that array. Assume you have declarations such as type realara=array[1..100] of real; var data:realara; size: integer; numneg: integer; sumneg: real; Then if you were to invoke your procedure with {code to get values into the array named data} size := 90; arraystuff(sumneg, numneg, data, size); writeln(numneg, ' negative numbers'); writeln('negative numbers adding up to ', sumneg:5:1); it 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 negative 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.) CPS 1 Final Exam Page 5 of 10 K.(5) 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 and covered in the lectures. Herbert Gateway 8Meg Word Asimov IBM 4Meg Word Niven Gateway 8Meg Troff Hogan Gateway 4Meg WordPerfect Smith IBM 8Meg Word Gibson Gateway 8Meg WordPerfect Niven IBM 4Meg WordPerfect Assume that the following query was typed into this program: ? Gateway 8Meg ? What (if any) output is produced? L.(10) Say that we run a program for several different amounts of data (represented by N) and get the following timing results: N t 100 1000ms 200 8000ms 300 27000ms 400 64000ms Give the formula that describes the execution time behavior. t = _____________________ M.(5) Assume we have another program which we run for several values of N. We notice that every time we add one to N, it takes three times as long to run. Circle one or more of the following terms that we could use to describe the behavior of the program and it's underlying algorithm. exponential polynomial logarithmic intractable N.(5) Say that we run a program for several different amounts of data (represented by N) and get the following timing results: N t 200 4s 400 5s 800 6s 1600 7s Circle one or more of the following terms that we might best use to describe the behavior of the program and it's underlying algorithm. exponential intractable logarithmic tractable CPS 1 Final Exam Page 6 of 10 O.(20) Given the following Rules: -------------------------------------------------------------------------- Name Syntax Semantics -------------------------------------------------------------------------- R1: j -> w M(j) = w where w = //a sequence of letters// R2: i -> j M(i) = M(j) code(i) = //nothing// R3: k -> j := i code(k) = code(i) COPY AX,M(i) COPY M(j),AX R5: i -> ( j * k ) M(i) = createname code(i) = code(j) code(k) COPY AX,M(j) MUL AX,M(k) COPY M(i),AX Use the rules to show the syntactic derivation of Z:=(R * S) 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. (Continue on the back of the previous page if needed.) ------------------------------------------------------------------------------- Derivation Syntax Rules Semantic Rules ------------------------------------------------------------------------------- (1) 1 R3: 1 -> 2:=3 code(1) = code(3) COPY AX,M(3) COPY M(2),AX (2) 2:=3 R1: 2 -> Z M(2) = Z CPS 1 Final Exam Page 7 of 10 P.(20) Do a trace for the program shown below left using the column headings shown below. Assume that the user enters the numbers 33, 15, 44, and -1 when input is requested. st# CF AX S st# CF AX S | ? ? ? ? | 0 copy ax, #c0 | | 1 copy s, ax | | 2 in ax | | 3 #L0 cmp ax, #c0 | | 4 jb #L1 | | 5 add ax, s | | 6 copy s, ax | | 7 in ax | | 8 jmp #L0 | | 9 #L1 copy ax, s | | 10 out ax | | 11 halt | | 12 #c0 0 | | 13 s 0 | | | | | | | | | | | | | | | | | | | | | | | | CONTINUE IN RIGHT COLUMN ABOVE CPS 1 Final Exam Page 8 of 10 Q.(15) ------------------------------------------------------------------------ Derivation Rules ------------------------------------------------------------------------------- (1) 1 R3: 1 -> 2:=3 code(1) = code(3) COPY AX,M(3) COPY M(2),AX (2) 2:=3 R1: 2 -> Z M(2) = Z (3) Z:=3 R2: 3 -> 4 M(3) = M(4) code(3) = //nothing// (4) Z:=4 R1: 4 -> G M(4) = G (5) Z:=G ------------------------------------------------------------------------------- Using the rule instantiations shown above to derive Z := G, generate the code for 1 step-by-step as shown in the text. code(1) = by CPS 1 Final Exam Page 9 of 10 R.(9) The circuit shown is the three bit adder discussed in class (without the control circuits). Show its use in adding the binary number 011 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.) S. (2) Add the following binary numbers and give their sum in binary: 1 1 0 1 0 1 1 1 + 1 0 1 1 0 1 1 1 --------------- CPS 1 Final Exam Page 10 of 10 T.(6) For the truth table shown below, drawing an equivalent circuit to the right showing switches in either the open or closed position. Show the appropriate battery and light. Label the switches correctly. 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 0 1 1 1 1 (3) Give the equivalent logical (Boolean) expression: U.(3) Cache memory is an extra fast memory that tries to keep the most frequently used information (circle one); 1) near the CPU. 2) on the disk. 3) in a register. V. (2) (T/F) Virtual Memory is a method for extending disk space. (2) (T/F) Multiprogramming is the technique where multiple computers cooperate in solving a common task. (2) (T/F) Early operating systems put their primary efforts into more efficient utilization of I/O devices such as printers. W.(3) The success of systems features like virtual memory and cache memory depend on a program execution property called (circle one): locality sequencing dead-lock X.(3) An operating system (such as UNIX) is designed to allow multiple users to share computing resources. Circle the items below that an operating system normally manages to allow sharing. keyboard monitor memory cpu disk_space