You have 50 minutes for this exam. There are 4 problems. Show your work.
Use an exam booklet. Be sure that your name is on the front of the booklet and printed legibly. Write and sign the honor code pledge.
Honor Code Pledge: I pledge my honor that I have not violated the honor code during this examination.
Problem 1:(25 points)
In this problem you will write a short program in the machine language
described in Appendix C of
Brookshear to perform the following task:
Add the contents of memory location A3(hexadecimal) to itself 64(decimal) times and store the result in memory location A4(hexadecimal). After storing the result in memory location A4, halt.
Part a (5 points) Write 64 (decimal) as two hexadecimal digits.
Part b (20 points) Write a sequence of machine instructions (in Brookshear machine language represented in hexadecimal notation) to perform the task. Assume the program is in memory starting at location 00.
Note that a copy of the Appendix C page listing the Op-codes has been appended to this exam for your convenience.
Problem 2:(25 points)
In the UNIX operating system, one can ``nice'' a program when one runs it.
``Nicing'' a program is simply telling the operating system
scheduler to give less priority
to the process that is the running program.
Part a (13 points) Suppose Unix has two kinds of priority at which one can start a process: regular priority and low (``niced'') priority. Explain how the scheduler might use this distinction of priority during the course of scheduling processes in a time-sharing system. Be explicit about the steps the scheduler would take each time it gives a different process a ``time slice'' of CPU time.
Part b (12 points) Recall that a process is ``I/O-bound'' if ``it requires a lot of I/O (i.e. input/output) operations'' (Brookshear), and a process is ``compute-bound'' if it ``consists of mostly computations within the CPU/memory system''(Brookshear). For which types of processes, I/O-bound or compute-bound, do you think it is more important for a user to ``nice'' a long-running process in order to be fair to other users? Why?
Problem 3:(25 points)
Consider the insertion sort algorithm as we developed it in class. It
can be summarized as:
If the array is of length 1, do nothing; otherwise:
For i=2 to length of array repeat:
use binary search to find the position among items 1 through i-1 (which
are sorted) in which item i belongs
put item i in its correct sorted postion among items 1 through i-1
by moving down any items as necessary to make room for item i.
After this is done, items in positions 1 through i are sorted.
end repeated instructions
where the items in the array are numbered from 1 through the length of the array. Note that this version from class is slightly different from the insertion sort given in Brookshear or in Lab 7, although the principle is the same.
Part a (13 points) Suppose insertion sort is executed on this array of already sorted names (i.e. the array is given as input to insertion sort already sorted):
1. Ann 2. Bob 3. Diane 4. Fred 5. Jane 6. Mike 7. Paul 8. Rob 9. Sally 10.TinaShow the step-by-step execution of insertion sort on this list starting at the point in the algorithm when the loop begins its repetition for i=9 and continuing until the algorithm finishes execution. Indicate every comparison of names and every repositioning of a name that occurs during this portion of the execution of the algorithm.
Part b (12 points) What is the running time of this version of insertion sort when the array of names given as input is already sorted? (Remember that the algorithm does not know that the array of names is sorted already.) Is this better, worse, or the same as the running time you would expect when the algorithm is executed on an array of names that start out in some arbitrary (random) order? Justify your answers.
Problem 4:(25 points)
Consider the following definition of procedure fillarray
(written in Brookshear-style pseudocode):
procedure fillarray taking as parameters:
parameter 1 is an array called ``A'', parameter 2 is an integer called ``start'',
parameter 3 is an integer called ``end'', parameter 4 is an integer called ``number''
if (start > end) then do nothing -- done
else execute the sequence of instructions:
assign the item at position start in A the value number
execute fillnumber with A for parameter 1, (2*start) for parameter 2,
end for parameter 3, and (number + 1) for parameter 4
execute fillnumber with A for parameter 1, ((2*start)+1) for parameter 2,
end for parameter 3, and (number + 1) for parameter 4
For those of you who like more programming-language style syntax, the same procedure can be written:
procedure fillarray (array A, integer start, integer end, integer number)
{
if (start > end) then do nothing -- done
else execute the sequence of instructions:
{
A[start] = number;
fillnumber(A, (2*start), end, (number + 1));
fillnumber(A, ((2*start)+1), end, (number + 1));
}
}
Part a (20 points) Let ``actualA'' be an array of items numbered starting at 1. Show the step-by-step execution of fillarray(actualA, 1, 7, 0) (i.e. execute fillarray with actualA as the argument for parameter A, 1 as the argument for parameter start, 7 as the argument for parameter end, and 0 as the argument for parameter number). During this execution, indicate each time one of the items in actualA is given a new value by giving the position of the item and its new value.
Part b (5 points) Give an argument to show that any execution of fillarray with positive values for start and end will eventually stop.
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 exam2.
The translation was initiated by Andrea LaPaugh on 1/12/2000