You have 3 hours for this exam. There are 10 problems. Show your work. And please write legibly.
Use three exam booklets for this test, one for Problems 1 through 3, one for Problems 4 through 6, and one for Problems 7 through 10. Failure to separate your solutions into three booklets in this way may delay your final grade. Be sure that the booklets are numbered and that your name and login ID are printed legibly on the front of each booklet. Write and sign the honor code pledge on the front of the first booklet.
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: (20 points)
Part a: (3 points) What is the decimal value of the 7-bit 2's complement
value 0101011?
Part b: (5 points) What is the fewest number of bits that can be used for a 2's complement representation of the decimal value -27 (negative twenty-seven)? Give the 2's complement representation of -27 in that number of bits.
Part c: (5 points) Give the addition of the following 4-bit 2's complement numbers: 0101 and 1001. Is there overflow error?
Part d: (4 points) What is the decimal representation of the value whose eight-bit floating point representation as presented in Brookshear is 11101101?
Part e: (3 points) The bit sequence 011010010110001101100101 represents an English word in ASCII code. What is that word?
Problem 2: (20 points)
Part a: (10 points) Build a truth table for the Boolean function represented by
the Boolean equation
( !x AND !y AND z ) OR ( x AND (y OR !z) )
Recall that !x denotes NOT(x).
Part b: (10 points) Give a Boolean equation using AND, OR, and NOT for the function whose truth table is:
x y | f(x,y)
-----|-------
0 0 | 1
0 1 | 0
1 0 | 1
1 1 | 1
Problem 3: (15 points)
Execute this machine language program starting at memory location
00. This program is in the machine language described in Appendix C of
Brookshear. To document the execution of the program, indicate which
instruction is being executed in each step and what, if any,
values in registers and memory are changed by the instruction execution.
memory location contents 00 & 01 120C 02 & 03 2001 04 & 05 B20A 06 & 07 5320 08 & 09 330C 0A & 0B C000 0C & 0D 0000
Problem 4: (20 points)
Suppose a computer has 24-bit long memory addresses,
1 Megabyte (= 220 bytes) of physical memory,
and an operating system providing virtual memory.
Each address refers to one byte of memory.
Part a (8 points) Suppose the virtual memory system allows every possible memory address to be used to address a byte. How much virtual memory does the system have?
Part b (12 points) Suppose the operating system is multitasking and has 4 processes
started, each taking one fourth of a Megabyte of memory. Describe
what the memory manager must do when the operating system tries to start a
fifth process by loading its machine code into memory. Assume that none
of the original 4 processes have completed.
Problem 5: (20 points)
Write an algorithm in pseudocode to find the largest divisor,
other than itself,
of a given positive integer, I - i.e. the largest factor of I.
Store the answer in a variable called divisor. If the number
I is prime (has no divisors other than 1 and itself) the algorithm
should set divisor to 1. For example, executing the algorithm with
I=12 should result in divisor=6 at the completion of the algorithm;
executing the algorithm with I=7 should result in divisor=1
at the completion of the algorithm.
You should try to make your pseudocode statements as much like statements in
a real programming language
as possible, but you need not use perfect Java
(or perfect any other programming
language).
Problem 6: (20 points)
Given two arrays, A and B, each with n items, write pseudocode
for a function that compares the arrays item for item
(i.e. A[1] is compared to B[1],
A[2] is compared to B[2], etc. until A[n] is compared to B[n])
and returns the number of items that are the same.
For example, given these arrays A and B, each with 4 integer items,
the returned value would be 2:
A[1]=17 B[1]=32
A[2]=80 B[2]=80
A[3]=61 B[3]=61
A[4]=12 B[4]=79
You should try to make your pseudocode statements as much like statements in
a real programming language
as possible, but you need not use perfect Java
(or perfect any other programming
language). Here is a pseudocode header for your function; the initial
``int'' indicates that the function named ArrayCompare returns an integer.
int ArrayCompare ( array A, array B, int n)
{
your pseudocode
}
Problem 7 (25 points)
Suppose we want to sort
a list of items from lowest magnitude to highest,
and each item is a sequence of b bits.
We are interpreting
each item as a positive binary number (not a 2's complement number), so
that, for example, if b=4, 0000 represents 0 and 1111 represents 15.
With this type of item and the ability to look at each bit in
an item we can do a variation of quick sort that does not require
choosing a pivot element. Instead, in the initial stage, we put all the
items whose first (leftmost) bit is a ``1'' below all the items whose first bit
is a ``0'' using pointers the way quick sort does.
We then proceed recursively on the sublist of items
starting with ``0''s and the sublist of items starting with ``1''s,
but separating on
the value of the second bit. We continue in this fashion until we
have separated on all b bits. At this point the list is sorted.
Pseudocode for the sorting procedure appears on the next page.
Part a: (15 points) Execute BitByBitSort on the list below with start=1, end=6, k=1 and b=4.
List: item number item value [1] 1010 [2] 0111 [3] 0010 [4] 0101 [5] 1000 [6] 0000
Part b: (10 points)
How does the efficiency of BitByBitSort compare to the
efficiency of quick sort? Be as precise as possible in comparing the
efficiencies of BitByBitSort and quick sort.
Hint: Consider that
BitByBitSort works with two size parameters: the length, n, of the list
and the number of bits, b, in each item.
In terms of n and b, what is the efficiency of BitByBitSort? (That is,
how does the number of steps executed by BitByBitSort vary as n and b vary?)
BitByBitSort sorting entries List[start] through List[end] on bit position k of b
{ if (start >= end) {done} //if sorting less than two entries, done
else
{
top_pointer = start;
bottom_pointer = end;
while (top_pointer does not equal bottom_pointer)
{
move bottom_pointer up to the nearest entry (including end)
whose kth bit is a 0, but not beyond top_pointer;
move top_pointer down to the nearest entry (including start)
whose kth bit is a 1 but not beyond bottom_pointer;
if (top_pinter does not equal bottom_pointer)
{interchange List[top_pointer] with List[bottom_pointer]}
} // end while
if (k = b) {done} //if have separated on rightmost bit, done
else
{
// COMMENT: either top_pointer and bottom_pointer both point to
// the last item with a 0 in the kth bit position or
// both point to the first item with a 1 in the kth bit position.
// Adjust them so that top_pointer points to the last item
// with a 0 in the kth bit position (if any) and bottom_pointer
// points to the first item with a 1 in the kth bit position
// (if any) END COMMENT
if (kth bit of List[top_pointer] is a 1 )
{ top_pointer = top_pointer - 1 }
else { bottom_pointer = bottom_pointer + 1 }
if (top_pointer > start )
{ apply BitByBitSort to List[start] through List[top_pointer]
on bit position k+1 of b }
if ( bottom_pointer < end )
{ apply BitByBitSort to List[bottom_pointer] through List[end]
on bit position k+1 of b }
} // end else when k < b
} // end else when start < end
} // end BitByBitSort
Problem 8: (20 points)
Suppose we have two linked lists, referred to by the pointers FirstA and LastA,
giving the front item and the back item of linked list A, and FirstB and LastB,
giving the front item and the back item of linked list B.
Write pseudocode to append linked list B to the back end of linked list A.
As a result of this append operation, linked list A should refer to the resulting
combined list and linked list B should be empty.
Problem 9: (20 points)
Part a: (10 points) Give the values of the nodes examined, in the order examined,
in the binary search tree shown below if the value 20 is being sought.
100
/ \
/ \
/ \
25 130
/ \ / \
/ \ / \
18 60 111 135
/ \ \ / \
3 20 87 131 200
Part b: (10 points) Show where the value 99 would be added to the tree. It
suffices to redraw the part of the tree that changes, including
the added node of value 99.
Problem 10: (20 points)
At the end of Problem 9, we had a binary search tree that stored 13
numbers with values in the range 0 through 200.
An alternative to a binary search tree is to use hashing.
Let us use an array of 11 entries numbered 0 through 10. A value is stored
in the entry corresponding to its remainder when divided by 11. The result
is:
array entry number values stored at that entry (as linked list)
[0] none
[1] 100, 111
[2] 200
[3] 25, 135, 3
[4] none
[5] 60
[6] none
[7] 18
[8] none
[9] 130, 20
[10] 87, 131
Part a: (10 points) Describe how value 20 would be looked up in this array. What other values, if any would need to be examined before finding value 20?
Part b: (10 points) Explain where value 99 would be added to the array and why.
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 final.
The translation was initiated by Andrea LaPaugh on 1/27/1999
Andrea LaPaugh