$(8$ points$)$ Answer the following $\frac{T}{F}$ questions

$($a$)$ The sequential search algorithm can only be applied to a previously sorted list

$($b$)AO(n^2)$ grows at a faster rate than a $O(100n)$ algorithm

$($c$)$ The binary search algorithm is in the worst case $O(n^2)$

$($d$)$ The cache memory is a high$-$speed relatively small memory

$($e$)$ The Hamiltonian circuit problem has a polynomial$-$time solution

$($f$)$ An exponential algorithm is faster than a linear algorithm for all input sizes

$($g$)$ Converging pointers algorithm is fast but does not preserve the order of the list

$($h$)$ The instruction LOAD $5$ puts the integer $5$ into register $R$

$(10$ points$)$

$($a$)$ What is the largest positive number one can represent in an $8-$bit $2\text{'}$s complement

binary notation? Explain your methodology to get the result and write your result

in binary and decimal.

$($b$)$ What is the greatest magnitude negative number one can represent in an $8-$bit

$2\text{'}$s complement binary notation? Explain your methodology to get the result and

write your result in binary and decimal.

$($c$)$ Convert the following $2\text{'}$s complement binary numbers to decimal.

i$.11010101=$

ii$.01101111=$

$(8$ points$)$

$($a$)$ Convert $1111\mathrm{.}111_2$ to decimal $($show all your work$).$

$($b$)$ Convert the decimal number $-{29\mathrm{.}1875}_{10}$ to binary, stored in scientific $($exponen$-$

tial$)$ notation with a $10-$bit sign$/$magnitude mantissa and a $6-$bit sign$/$magnitude

exponent $($show all your work$).$

$(8$ points$)$ Using the decimal representation scheme described in the previous exercise

$($item $($b$)),$ give the decimal value of each of the following $16-$bit binary strings. Show

all the details of your work.

$($a$)0111000001001001$

$($b$)1100010000100011$

$(12$ points$)$

$($a$)$ Draw the circuit corresponding to the following boolean expression:

$P=(a+b)*(\frac{?}{\text{b}\text{a}\text{r}}(c*(\frac{?}{\text{b}\text{a}\text{r}}(c+b))))$

$($b$)$ For the circuit above, draw the truth table for the output of each gate.

$($c$)$ Show using Boolean logic properties $($truth table method will not be accepted$)$

that $P($the Boolean expression above$)$ is equivalent to the Boolean expression

$Q=a+b$

and draw the corresponding circuit.

$(12$ points$)$

$($a$)$ Suppose a memory is composed of $512$ locations, each containing $16$ bits. How

many bits does it contain in total? What is the size of its MDR $($memory data

register$)$ and its MAR $($memory address register$).$

$($b$)$ Assume now we are dealing with a memory where each cell or location contains

exactly $8$ bits. In each of the following three cases, how big does the MAR have

to be$?$ How many bits of the MAR must be sent to the row decoder? To the

column decoder? How many output lines would these decoders have?

i$.64$ Kylobytes:

ii$.512$ Megabytes:

iii. $4$ Gigabytes :

$($c$)$ If the average access time of this memory is $25$ nsec and the average access time

for cache memory is $10nsec,$ what is the overall average access time if our cache

rate hit is $80\%?$

$($d$)$ What would the cache hit rate have to be to reduce the average access time to $12$

nsec$?$

$(10$ points$)$ Using the instruction set shown in Figure $1,$ translate the following algo$-$

rithmic primitives into assembly language code. Show all necessary $.$DATA pseudo$-$ops.