S A M P L E 

				  Quiz #12

Name ___________________   Honor Code________________________    Section _____

								  ---------
A. True/False?

(1) The operating system (OS) help you share computer resources. 
   [true]
(2) The disk platter spin rate is controlled by the I/O system of the OS.
   [false]
(3) Multiprogramming means that, in effect, more than one program is running.
   [true]
(4) Cache memory is one of the slower components of the memory hiearchy.
   [false]
(5) Virtual memory is always smaller than main memory.
   [false]
possibly a few more ...

B. Say that a program's execution time behavior can be expressed by

         2
t = C * N

where t is the execution time, C is some constant, and N is the number of
data objects dealt with.

If the program takes 3 seconds to deal with 200 objects, how much time
should it take to deal with 600 objects?
                                                [27 s]
                                              -------

C. Say that we run another program for several different amounts of data
(represented by N) and get the following timing results:

N	t
-----------
10	13 s
20	26 s
30	39 s
40	52 s

Give the formula that describes the execution time behavior.


	t =  [ A * N  for partial credit  = 1.3 * N for full credit]

What will the time be for N = 100?    [130 s]
                                    ----------


D. Assume we have yet another program which we run for several small values
of N.  We notice that every time we increase N by one, it takes 10 times
as long to run.  Circle those of the following terms that we might reasonably
use to describe the behavior of the program and it's underlying algorithm.

polynomial     (exponentia)	(intractable)	logarithmic
                
	(difficult-for-computers)		made-for-computers	



E. Assume the information in a telephone book has been placed in a computer
memory, alphabetized like in a real phone book.  Which algorithmic behavior
could we expect from a well written search program using a binary search?
(N is the number of entries in the phone book.)

  [X]	1)  Logarithmic time (t = C * log N)

	                             2
	2)  Quadratic time (t = C * N )


	3)  Linear time (t = C * N)