, n log n or n? Explain your answer. Hint: compare the work done by merge sort to the work done by other sorting algorithms we have studied. Look at the organization of merge sort in comparison to the organization of the other algorithms.
Instructions: This exam is open-book. You may use your personal notes and problem set submissions, copies of any of the course Web pages, copies of the problem set solutions, and Computer Science: An Overview by Brookshear. No other materials are allowed. You have 3 hours. There are 12 problems.
Use one or more exam booklets for problems 1 through 6 and a second set of exam booklets for problems 7 through 12. Failure to use a separate booklet or booklets for problems 7 through 12 may delay your final grade. Be sure that your name is on the front of each booklet and printed legibly.
Show your work.
Write and sign the honor code pledge.
Note: You will need the table of the ASCII code appearing as Appendix A in Brookshear and the table of operations of the Brookshear machine of Appendix C. To save you time and in case you have not brought your text, these have been reproduced for you and appended to this exam.
Honor Code Pledge: I pledge my honor that I have not violated the honor code during this examination.
Problem 1:(11 points)
Part a(2 points): Give the binary representation of decimal 19.
Part b(2 points): Give the 6-bit two's complement representation of decimal -28.
Part c(2 points): Give the ASCII representation of the string 97.
Part d(3 points): Give the eight-bit floating point representation presented in Brookshear of the negative fraction -17/32. (Recall that Brookshear uses one bit for sign, three bits for exponent, and four bits for mantissa.) Is there round-off error? If so, why, and how much accuracy is lost?
Part e(2 points): Consider this string of seven bits: 1011001. We want the eighth bit to be the odd parity bit. What is that bit? How did you calculate it, i. e. what is the definition of an odd parity bit? One-bit answers will not receive credit, even if the bit is correct.
Problem 2:(8 points)
Consider the circuit of AND, OR and NOT (inverter) gates shown below.
Part a(4 points) Give the truth table for the function f of inputs x, y, and z computed by the circuit. (The truth table is the table of values of f for each possible input triple.)
Part b(4 points) Give a Boolean equation using operations AND, OR, and NOT for the function f computed by the circuit.
circuit.eps
Problem 3:(6 points)
Suppose a computer is built with one gigabyte of main memory. (``giga'' is billion.) How many bits must each memory address be, assuming each byte is addressed?
Problem 4:(10 points)
For the following piece of Java-like pseudocode, give the sequence of machine operations that must be performed by a CPU to do the computation. Assume x, y, and z are integers.
if ((x == y) OR (x == z))
{ x = 0;}
else { x = y + z;}
You need to write the sequence of operations at the machine-code level but you do not need to use actual machine code. Use the basic operations of the Brookshear machine in Appendix C: LOAD, LOAD CONSTANT, STORE, MOVE, ADD two's complement, ADD floating-point, OR, AND, EXCLUSIVE OR, ROTATE, JUMP if equal Reg0, and HALT. Refer to them by name (not by op-code number). Refer to registers as Reg0, Reg1, etc. Assume x, y, and z are stored in memory locations, which you can refer to as ``MEM LOC of x'', ``MEM LOC of y'', ``MEM LOC of z''. Your first instruction might be:
LOAD Reg0 from MEM LOC of xYou need to write the rest of the instructions that must be given to a Brookshear machine to perform the desired computation.
Problem 5:(7 points)
Write Java-like pseudocode that takes two arrays of integers, A and B, sums each pair of corresponding elements and puts the sum in the corresponding element of a third array C. For example if we are given A, and B, each with four elements:
first element of A = 10 second element of A = 20 third element of A = 30 fourth element of A = 40 first element of B = 2 second element of B = 4 third element of B = 6 fourth element of B = 8The resulting C would be:
first element of C = 12 second element of C = 24 third element of C = 36 fourth element of C = 48For your pseudocode, assume that A, B, and C each have n elements, where n is a variable.
Problem 6:(6 points)
In this problem we will be using the following Java method (function).
public int aFunction (int x)
{ int y;
y = 1;
while (y < x)
{ y = y * 2;}
return y;
}
For each of the three uses of the type keyword int in the method, explain what information is being given the compiler and how the compiler uses the information. That is, of what use to the compiler is each piece of information about type? Be sure to explain each one. Do not give some general statement about the purpose of declarations.
STOP.
USE A NEW EXAM BOOKLET
FOR PROBLEMS 7 through 12
Problem 7:(8 points)
Consider this Java-like pseudocode for a function:
int DoWhat(int x, int y)
{ if (y <= 0)
{return 1};
if (y == 1)
{return x};
if (y > 1)
{ temp = DoWhat(x, y/2);
temptoo = DoWhat(x, y-(y/2) );
answer = temp*temptoo;
return answer;
}
Execute DoWhat(5, 3). What is returned? Show your work!
Caution: ``/'' is integer division - round halves down! e.g. 7/2 = 3.
Problem 8:(8 points)
Execute the first stage of quick sort on this list of numbers. By the first stage, I mean the first loop in quick sort that moves pointers up and down the list, exchanging items, and ends by putting the pivot item in its correct position - everything up to but not including the recursive calls to quick sort. Show each comparison and each item movement. Indicate which parts of the list would be used in the recursive calls to quick sort, but do not execute the recursive calls.
33
20
45
8
10
Problem 9:(8 points)
Explain how to find the middle item in a linked list of items. You may explain in English or use pseudocode. By ``middle item'', I mean the item that is half way between the first and last items in the linked order of the list, not the item whose value is the median value of all the items. (It may be helpful to draw one or two pictures of a linked list to illustrate your algorithm.)
Problem 10:(8 points)
Suppose we have a queue data structure, i.e. items can be added to the end of the queue and are removed from the beginning of the queue. In addition we are able to examine the value of the first item of the queue without removing it.
Queue operations:
Write pseudocode using the above queue operations to take two queues of sorted items (smallest first) and merge them into a new queue of sorted items. The two original queues should end up empty, and the new queue should end up with all the items from the original queues. The new queue should be sorted.
Hint: the first item in the new queue is the smaller of the two first items in the original queues.
Problem 11:(8 points)
If one does not worry about using a lot of extra space, there are other ways to sort a list of items in addition to those we have examined this semester. One is called merge sort. Merge sort can be expressed in pseudocode as follows:
MergeSort(L,n) /*sort a list L of n items, numbered 0 through n-1*/
{
if ( n equals 0 or 1 )
{nothing needs to be done}
else
{ copy items 0 through (n/2)-1 to list A;
copy items (n/2) through n-1 to list B;
MergeSort(A, n/2);
MergeSort(B, n-(n/2) );
merge sorted lists A and B into list L;
}
}
Here ``/'' is integer division (round halves down). The last step,
to ``merge'' the sorted lists, can be done by treating the lists as queues
and using the procedure you have designed in Problem 10.
However, to do this problem
you do not need to have completed Problem 10.
You only need to know that
merging can be executed in time proportional to the number of items
in list L.
Part a(6 points): What is the average execution time of merge sort -
proportional to , n log n or n? Explain your answer.
Hint: compare the work done by merge sort to the work done by other sorting
algorithms we have studied. Look at the organization of merge sort in
comparison to the organization of the other algorithms.
Part b(2 points): If list L starts out sorted, does merge sort work faster than on average, slower than on average, or the same. Why?
Problem 12:(12 points)
Part a (4 points) Give the values of the nodes examined, in the order examined, in the binary search tree shown below if the value 160 is being sought.
177
/ \
/ \
/ \
125 230
/ \ / \
/ \ / \
80 160 189 254
/ \ / \
4 120 240 280
\
300
Part b (5 points) Design a new binary search tree that is more balanced for the same set of numbers. It should be necessary to examine no more than four nodes to find any value in the new tree. Draw the new tree.
Part c (3 points) Where would the value 310 be placed if it is inserted in your new tree after the tree is built? Does the tree stay as balanced?
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 draft_new_short.
The translation was initiated by Andrea LaPaugh on Thu Dec 3 00:11:03 EST 1998