CPS 1 (Ramm)                       Page 1 of 11


30 April                 Spring Semester, 1999			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.

		(6)			(5)
		A	_____	 	N    _____

		(6)			(10)
		B	_____	 	O    _____

		(4)			(5)
		C	_____	 	P    _____
DISCLAIMER!!!!!!!!!!!!!!
		(4)			(5)
		D	_____	 	Q    _____
This is a sample final used previously.  You can use it to see the
		(4)			(5)
		E	_____	 	R    _____
kind of questions you might find.  Absence of items on this final
		(4)			(15)
		F	_____	 	S    _____
(e.g., the adder circuit) doesn't mean they won't be on this year's
		(4)			(20)
		G	_____	 	T    _____
final.  Also, each semester is a little bit different, so not every one
		(4)			(20)
		H	_____	 	U    _____
of the questions on this sample would be appropriate or fair this year.
		(6)			(2)
		I	_____	 	V    _____

		(4)			(9)
		J	_____	 	W    _____
Answers have been inserted or marked.
		(10)			(12)
		K	_____	 	X    _____

		(10)			(10)
		L	_____	 	Y    _____

		(5)			(12)
		M	_____	 	Z    _____

					-------------
		

-----------------------------------------------------------------------------
HONOR CODE

I have not received or given any improper help on this exam.


					(your signature)
CPS 1                            Final Exam                     Page 2 of 11

A(6) Two programs were defined as being equivalent if, given the same input
they always produced the same output.  

Assume the core of program One consists of

	int x = inputField.getInt();
	x = 2 * x * x + 1;
	x = x / 2 + 1;
	outputField.setInt(x);

Assume the core of program Two consists of

	int x = inputField.getInt();
	x = x * x + 1;
	outputField.setInt(x);

Are these two programs equivalent (ignoring implementation problems like
integers getting too large to be stored in a register, etc)?
  >A) They are equivalent.
   b) They not are equivalent.
   c) The second program doesn't work for negative numbers.
   d) The first program can't handle input of zero.


B(6) Given the Java program fragment:

	int x, k, a, c = 0;
	a = inputField.getInt();
        k = 0;
	while (k < 10)
	{
	    x = inputField.getInt();
	    if (x == a)
	    {
		c = c + 1;
	    }
	    k = k + 1;
	}
	outputField.setInt(c);

The program above accepts 11 integers entered by the user of the program.
It outputs a single value contained in c.  What is the significance of the
value of c in relation to the numbers read in?
   A) It is the number of times the logical expression in the if was true.
   b) It is the number of times the loop body was executed.
   C) It is the number of times the first number read in matches later numbers.
  >D) It is both a) and c) but not b).


C(4) A program is left running on a workstation collecting passwords (as
described when computer security was discussed).  This kind of program was
described as
   a) a Three-headed Greek dog.
  >B) a Trojan horse
   c) a virus detector
   d) a security audit tool


CPS 1                            Final Exam                     Page 3 of 11

D(4) If one were foolish enough to try to actually writing a program
"halts(p, d)" to solve the halting problem, a naive start might be to
look for the absence of which one Java statement to assure that it stops?
   a) if
  >B) while
   c) return
   d) int

E(4) For large industrial programming efforts, the number of lines of code
produced per day (on average) is quite different from productivity on
a small or class program.  For large projects the figure is
  >A) less than 50 lines a day.
   b) more than a) but less than 100 lines per day.
   c) more than a) or b) but less than 150 lines per day.
   d) more than 150 lines per day.


F(4) In the early days of computing with primitive operating systems
a system was called a "batch" system because: (pick one)
   a) It was a constructive blend of hardware and software.
  >B) Many programs were placed on one tape and all had to be processed before
      getting any back.
   c) The collection of programs put on a tape were merged together to
      cooperatively produce a better program. (multi-programming)
   d) None of the above.


G(4) If we were to define sum(N) recursively for positive integers by:
	1. sum(N) = N + sum(N-1);  2. sum(0) = 0;
Which one of the following statements is FALSE?
   a) 2. is the base or halting case.
   b) An algorithm for adding the numbers from 1 to N is described.
   c) It is restricted to positive numbers so that the base case can be reached.
  >D) A more descriptive name for the function sum(N) is factorial.

H(4) Which of the following statements best indicates what is necessary to
avoid writing an infinite while loop?
   a) The body of the loop must contain an if statement.
   b) At least one function/method must be called in the body of the loop.
  >C) Something in the body of the loop must cause the value of the logical
     expression following the "while" to change.
   d) The statement k = k - 1; must always be present.


I(6) Arrays make it easier to solve certain programming problems.  Others
don't need arrays at all.  Check off the following to indicate whether or
not arrays are need.
   (need)(NOT NEED) a) Find the larger of two numbers.
   (NEED)(not need) b) Sort a list of names.
   (NEED)(not need) c) Create a "Used Car" database.
   (need)(NOT NEED) d) Decide whether a number is odd or even.
   (need)(NOT NEED) e) Count the number of data points read.

J(4) We proved in class that a solution to the halting problem can not
exist.  Is this an isolated result?  (Mark each line below as True/False)
 F a) Fortunately, this seems to be the only program that can't be solved.
 F b) Another example is programs that check the syntax of other programs.
 F c) Scientists think there are other problems, but none have been identified.
CPS 1                            Final Exam                     Page 4 of 11

K(10)  Below is part of a Java program.  Show what the array "data" will
contain after this code is executed by filling in the boxes below.
  
    int size = 10;
    int data[] = new int[size];
    int k = 0;
    int m = 3;
    int x = 0;

    while (k < size)
    {
        data[k] = x;
        if (x > m)
        {
            x = 0;
        }
        else
        {
            x = x + 1;
        }
        k = k + 1;
    }


          0     1     2     3     4     5     6     7     8     9
        ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
data:  |  0  |  1  |  2  |  3  |  4  |  0  |  1  |  2  |  3  |  4  |
        ----- ----- ----- ----- ----- ----- ----- ----- ----- -----


L(10)  Assume that the program above continues with the code that follows
and that the numbers you just wrote into data are still there.
Show what will be displayed in the StringField "output" after this
code runs.

    k = 10;
    int max = data[0];
    int min = data[0];
    while (k > 0)
    {
        k = k - 1;
        if (data[k] < min)
        {
            min = data[k];
        }
        if (data[k] > max)
        {
            max = data[k];
        }
    }
    output.setString("Stats: max = " + max + ", min = " + min);

   ----------------------------------------------------------------------
  |
  | Stats:_max_=_4,_min_=_0
   ----------------------------------------------------------------------


CPS 1                            Final Exam                     Page 5 of 11

For the next two questions, assume that we have a database on used cars
with the following entries.  (These would be stored in 5 arrays.)
Assume that you are dealing with a program of the type discussed in
the text and covered in the lectures.
    
Ford    1997    blue    rv      22500
Chevy   1995    green   sedan   7000
Ford    1995    white   truck   7450
Chevy   1996    blue    sedan   1800
Chevy   1995    white   truck   7500
Toyota  1997    red     truck   23995
Ford    1995    green   truck   8590

M(5) Assume that the following query was typed into this program:

    --------  --------  ---------  ---------  ---------
   |        ||        || red     || sedan   ||         |
    --------  --------  ---------  ---------  ---------
where a blank TextField implies a wild-card entry.
What output, if any (write NONE if appropriate) is produced?
   ----------------------------------------------------------------------
  |NONE
  |
  |
   ----------------------------------------------------------------------


N(5) Now assume we've EXTENDED the system so that by putting a less-than
(<) in front of a query word, it would mean take entries where is field
is less than specified.  For example, <10000 would mean select the record
only if the price is less than 10000.

    --------  --------  ---------  ---------  ---------
   |        || <1996  ||         || truck   ||         |
    --------  --------  ---------  ---------  ---------
What output, if any (write NONE if appropriate) is produced?
   ----------------------------------------------------------------------
  |Ford    1995    white   truck   7450
  |Chevy   1995    white   truck   7500
  |Ford    1995    green   truck   8590
   ----------------------------------------------------------------------



O.1.(6) Say that we run a program for several different amounts of data
(represented by N) and get the following timing results:
	N	 t
	1000    1s
	2000    8s
	3000   27s
	4000   64s
Give the formula that describes the execution time behavior.
                   3
	t = A * __N_________
                                   -9
  2.(4) Compute the value of A: _10__________  or 0.000000001


CPS 1                            Final Exam                     Page 6 of 11

P(5) Assume we have another program which we have run for several moderate
test values of N (say 50) and it finishes in a second or two.  Now we want
to put the program into production with its full load of 500 cases.
We notice that program keeps churning away, giving no signs of completing.
After eight hours we go home.  The next morning it's still grinding
away.  We stop the program to consider what's gone wrong.  What would
you suggest has happened.  (Mark all that seem plausible at this point.)
 X a) The program uses an exponential algorithm. 
   b) The logarithmic algorithm being used has finally caught up with us.
   c) It's an example of being too tractable.
 X d) There's a bug in the program and it has gotten into an infinite loop.


Q(5) Say that we run a program for several different amounts of data
(represented by N) and get the following timing results:
	N	t
	2000	3s	
	4000	4s	
	8000	5s    
       16000	6s   
Circle one or more of the following problems that might have produced
the kind of data shown above.
  >A) N searches for keys in a sorted list (e.g. telephone book)
   b) sorting a list of N addresses
   c) solving the "traveling salesman" for N cities
   d) doing the "towers of Hanoi" for N disks
   e) searching the text of an N word book for the number of "and"s.


R(5) Assume you are writing a program to play checkers.  Checkers is a
board game like chess in which players alternate moving pieces around
on the board and attempting to capture opposing pieces. Assume that you
are going to solve this by considering all possible moves by one side,
then considering all possible responses by the other player, back, and
forth, etc.   We'll use simple, average figures to make this simple:

Assume that for each turn a player has, on average, 8 possible moves.
Assume that there will be 44 total moves, 22 for each side before
one side wins.  How many total moves must the computer consider to
play a perfect game (one in which all possible moves and responses
have been considered)?

Show how you would calculate the answer.  The exact numeric answer is
not important.  A single numeric answer will give you no credit unless
you hit it exactly.  However, you can get full credit by showing
what numbers you plan to manipulate.  A very brief explanation can
also help you if you mess up some other detail.

                   44
                  8








CPS 1                            Final Exam                     Page 7 of 11

S(15) Given the following Rules:
--------------------------------------------------------------------------
Name	Syntax Rules
--------------------------------------------------------------------------

R1: 	<n>j -> w, where w = //a sequence of one or more letters//

R2: 	<e>i -> <n>j

R3: 	<s>i ->  <n>j = <e>k;

R4: 	<e>i ->  ( <e>j + <e>k )	

R5: 	<e>i -> ( <e>j * <e>k )	

Use the rules to show the syntactic derivation of S = (( X * Y) + Z );
Do not worry about semantic rules for this problem.
Steps one and two have been carried out for you.
-------------------------------------------------------------------------------
Derivation			Syntax Rule Used
-------------------------------------------------------------------------------
(1) <s>1			R3: <s>1 -> <n>2=<e>3;
					
(2) <n>2 = <e>3;		R1: <n>2 -> S	
--------------------------------------------
(3) S = <e>3;			R4: <e>3 ->  ( <e>4 + <e>5 )	

(4) S = (<e>4+<e>5);		R2: <e>5 -> <n>6

(5) S = (<e>4+<n>6);		R1: <n6> -> Z

(6) S = (<e>4+Z);		R5: <e>4 -> ( <e>7 * <e>8 )	

(7) S = ((<e>7*<e>8)+Z);	R2: <e>7 -> <n>9

(8) S = ((<n>9*<e>8)+Z);	R1: <n)9 -> X

(9) S = ((X*<e>8)+Z);		R2: <e>8 -> <n>10

(10) S = ((X*<n>10)+Z);		R1: <n>1- -> Y

(11) S = ((X*Y)+Z);
















CPS 1                            Final Exam                     Page 8 of 11

T(20) Do a trace for the program shown below left using the column headings
shown below.  Assume that the user enters the numbers 3, 2, 5, and 1
when input is requested.  Then answer the questions below.  The grade will
be based mostly on your answers to the questions, not the trace.
                            st#  CF   AX    p    c    st#  CF   AX    p    c
0       in      ax        |  0         3            |  6         1

1       copy    n, ax     |  1                      |  7        10    

2       copy    ax, #c0   |  2         0            |  8             10

3       copy    c, ax     |  3                   0  |  9         2

4	copy	ax, #c1	  |  4         1	    | 10         3

5       copy    p, ax     |  5              1       | 11                   3

6 #L0   in      ax        |  6         2            | 12   NB

7       mul     ax, p     |  7         2            | 13

8       copy    p, ax     |  8              2       | 14        10

9       copy    ax, c     |  9         0            | 15

10      add     ax, #c1   | 10         1            | 16

11      copy    c, ax     | 11                   1  |

12      cmp     ax, n     | 12    B                 |

13      jb      #L0       | 13                      |

14      copy    ax, p     |  6         5            |

15      out     ax        |  7        10            |

16      halt              |  8             10       |

17 #c0         0          |  9         1            |

18 #c1         1          | 10         2            |

19 p           0          | 11                   2  |

20 n           0          | 12    B                 |

21 c           0          | 13                      |
 			CONTINUE IN RIGHT COLUMN ABOVE
(3) This program uses 1 as a sentinel (value on which to stop). (True/False?)

(3) The looping programmed here depends on a count read in at the beginning
which tells how many times we repeat the loop. (TRUE/False?)

(4) What are the line numbers for the nine statements executed exactly once,
regardless of the data?__0, 1, 2, 3, 4, 5, 14, 15, 16_______

(10) The output produced by the program is ______10____________________
CPS 1                            Final Exam                     Page 9 of 11

U(20) Use the syntactic and semantic rules shown below to generate the code
for R = (S * T);
Use the methods shown in lecture and the textbook.  The first four steps
have been completed.  Finish the job on the back of the previous page.
--------------------------------------------------------------------------------
Syntax Rules                Semantic Rules
--------------------------------------------------------------------------------
R1: <n>j -> W               M(<n>j) = W

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

R3: <s>k -> <n>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) = CN1
		            code(<e>i) = code(<e>j)
					 code(<e>k)
					 COPY AX, M(<e>j)
					 MUL  AX, M(<e>k)
					 COPY M(<e>i),AX
--------------------------------------------------------------------------------
Derivation	      Rules
--------------------------------------------------------------------------------
(1) <s>1	      R3:  <s>1 -> <n>2 =<e>3	  code(<s>1) = code(<e>3)
							       COPY AX,M(<e>3)
							       COPY M(<n>2),AX
	    MEANING   code(<s>1) = code(<e>3)
			           COPY AX,M(<e>3)
			           COPY M(<n>2),AX
(2) <n>2 = <e>3;      R1:  <n>2 -> R		  M(<n>2) = R

	    MEANING   code(<s>1) = code(<e>3)
			           COPY AX,M(<e>3)
			           COPY R,AX
(3) R = <e>3;	      R5: <e>3 -> (<e>4 * <e>5)   M(<e>3) = CN1
						  code(<e>3) = code(<e>4)
						               code(<e>5)
						               COPY AX, M(<e>4)
						               MUL  AX, M(<e>5)
						               COPY M(<e>3),AX
	    MEANING   code(<s>1) = code(<e>4)
			           code(<e>5)
			           COPY AX, M(<e>4)
			           MUL  AX, M(<e>5)
			           COPY CN1,AX
			           COPY AX,CN1
			           COPY R,AX
(4) R =(<e>4 * <e>5); R2: <e>4 -> <n>6	  	  M(<e>4) = M(<n>6)
						  code(<e>4) = //nothing//
	    MEANING   code(<s>1) = //nothing//
			           code(<e>5)
			           COPY AX, M(<n>6)
			           MUL  AX, M(<e>5)
			           COPY CN1,AX
			           COPY AX,CN1
			           COPY R,AX
------------------------------------------------------------------------------
(back of previous page :-)

(5) R =(<n>6 * <e>5); R1: <n>6 -> S	  	  M(<n>6) = S

	    MEANING   code(<s>1) = code(<e>5) 
			           COPY AX, S
			           MUL  AX, M(<e>5)
			           COPY CN1,AX
			           COPY AX,CN1
			           COPY R,AX

(6) R =(S * <e>5);    R2: <e>5 -> <n>7	  	  M(<e>5) = M(<n>7)
						  code(<e>5) = //nothing//
	    MEANING   code(<s>1) = //nothing//
			           COPY AX, S
			           MUL  AX, M(<n>7)
			           COPY CN1,AX
			           COPY AX,CN1
			           COPY R,AX

(7) R =(S * <n>7);    R1: <n>7 -> T	  	  M(<n>7) = T

	    MEANING   code(<s>1) = COPY AX, S
			           MUL  AX, T
			           COPY CN1,AX
			           COPY AX,CN1
			           COPY R,AX

(8) R =(S * T); 































CPS 1                            Final Exam                    Page 10 of 11

V(2) Add the following binary numbers and give their sum in binary:  							 
				0 1 0 1 1 1 1 1			  
			      +	1 0 1 0 1 1 0 1			
				---------------		
                              1 0 0 0 0 1 1 0 0



W 1.(6) For the truth table shown below, draw 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     1              |          /           |
  0  0	1     0       *------*---*__*--*  *--*__*---*-----*
  0  1	0     1       |      |    /           /     |     |    L
  0  1	1     0     -----    *---*  *--*__*--*  *---*     *--
  1  0	0     0      ===     |    /     /     /     |        (&)
  1  0	1     1     -----    *---*  *--*  *--*  *---*     *--
  1  1	0     0      ===          X     Y     Z           |
  1  1	1     1       |                                   |
                      *-----------------------------------*

  2. (3) Give the equivalent logical (Boolean) expression:


  L = X'Y'Z' + Z'Y Z' + X Y'Z + X Y Z

X(12) True/False?

T(1) A computer program that aids in plant identification by using rules
given to it by a expert botanists is a good example of an expert system.

F(2) Computers are not nearly as good as humans when it comes to activities
like translation of computer languages. 

T(3) Semantic networks are used in artificial intelligence  programs to
organize information about an object.

F(4) Artificial Intelligence avoids the hard problems and focuses on the
easy ones such as fast sorting.

T(5) Computer game playing is considered to be a branch of artificial
intelligence.

T(6) Based on recent tournaments, the best human chess players are almost
as good as the best computer chess programs.










CPS 1                            Final Exam                    Page 11 of 11

Y(10) True/False?

T(1) Light travels about one foot in a nanosecond.

T(2) Relays produce a lot of heat for the function they perform.

T(3) The mean time to failure is greater for transistors than for relays.

T(4) Vacuum tube technology is still used in many computer displays.

T(5) Integrated circuits can have over one million transistors on one chip.




Z(12) True/False?

T(1) Many of the modern user interface ideas originally came from Xerox.

T(2) Deadlocks can occur when computer resources are shared.

F(3) Most modern operating systems no longer support multi-programming.
                                                                  
T(4) Virtual memory is a way of simulating extra memory by using disks.

T(5) Cache is used to keep frequently used information closer to the CPU.

F(6) The earliest operating systems tried to provide a good graphical user 
interface (now called a GUI).