$1.(10$ points$)$ Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists $2,5,5,5$ and $2,2,3,5,5,7,$ the output should be $2,5,5.$

a$.(5$ points$)$ Algorithm design, pseudo code only.

b$.(5$ points$)$ What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n$,$ respectively?

$2.(16$ points$)$ Consider the following algorithm for finding the distance between the two closest elements in an array of numbers.

ALGORITHM MinDistance$($A$[0..$n $1])$

$//$Input: Array A$[0..$n $1]$ of numbers

$//$Output: Minimum distance between two of its elements

dmin$\backslash$infty

for i $0$ to n $1$ do

for j $0$ to n $1$ do

if i$!=$j and $|$A$[$i$]$ A$[$j $]|<$ dmin

dmin $|$A$[$i$]$ A$[$j $]|$

return dmin

a$.(4$ points$)$ What is its basic operation?

b$.(4$ points$)$ How many times is it performed as a function of the matrix order n$?$

c$.(8$ points$)$ Make as many improvements as you can in this algorithmic solution to the problem. If you need to$,$ you may change the algorithm altogether; if not, improve the implementation given.

$3.(7$ points$)$ Consider the definition$-$based algorithm for adding two n $\backslash$times n matrices.

a$.(3$ points$)$ What is its basic operation?

b$.(4$ points$)$ How many times is it performed as a function of the matrix order n$?$

$4.(7$ points$)$ Consider the definition$-$based algorithm for matrix multiplication.

a$.(3$ points$)$ What is its basic operation?

b$.(4$ points$)$ How many times is it performed as a function of the matrix order n$?$

$5.(10$ points$)$ For each of the following functions, indicate how much the function$$s value will change if its argument is increased fourfold?

a$.$ log$\_2$n;

b$.$n;

c$.$ n;

d$.$ n$^2$;

e$.2^$n

$6.(10$ points$)$ For each of the following pairs of functions, indicate whether the first function of each of the following pairs has a lower, same, or higher order of growth $($to within a constant multiple$)$ than the second function.

a$.$ n$($n$+1)$ and $2000$n$^2$;

b$.100$n$^2$ and $0\mathrm{.}01$n$^3$

c$.$ log$\_2$n and lnn

d$.2^($n$-1)$ and $2^$n

e$.($n$-1)!$ and n$!$

$7.(10$ points$)$ Use the informal definitions of O$,\backslash$Theta $,$ and $\backslash$Omega to determine whether the following assertions are true or false.

a$.$ n$($n$+1)/2$ in O$($n$^3)$

b$.$ n$($n$+1)/2$ in O$($n$^2)$

c$.$ n$($n$+1)/2$ in $\backslash$Theta $($n$^3)$

d$.$ n$($n$+1)/2$ in $\backslash$Omega $($n$)$

e$.$ n$($n$+1)/2$ in $\backslash$Omega $($n$^2)$

$8.(15$ points$)$ Consider the following algorithm.

ALGORITHM Mystery$($n$)$

$//$Input: A nonnegative integer n

S $0$

for i $1$ to n do

S $$S $+$ i $$ i

return S

a$.(3$ points$)$ What does this algorithm compute?

b$.(3$ points$)$ What is its basic operation?

c$.(6$ points$)$ How many times is the basic operation executed? You need to compute C$($n$).$

d$.(3$ points$)$ What is the efficiency class of this algorithm?

$9.(15$ points$)$ Consider the following algorithm.

ALGORITHM Enigma$($A$[0..$n $1,0..$n $1])($A is a matrix$)$

$//$Input: A matrix A$[0..$n $1,0..$n $1]$ of real numbers

for i $0$ to n $2$ do

for j $$i $+1$ to n $1$ do

if A$[$i$,$ j $]!=$A$[$j$,$ i$]$

return false

return true

a$.(3$ points$)$ What does this algorithm compute?

b$.(3$ points$)$ What is its basic operation?

c$.(6$ points$)$ How many times is the basic operation executed? You need to compute C$($n$).$

d$.(3$ points$)$ What is the efficiency class of this algorithm?

$10.(10$ points, bonus$)$ Consider the following recursive algorithm.

ALGORITHM Q$($n$)$

$//$Input: A positive integer n

if n $=1$ return $1$

else return Q$($n $1)+2$ n $1$

a$.(5$ points$)$ Set up a recurrence relation for this function$$s values and solve it to determine what this algorithm computes.

b$.(5$ points$)$ Set up a recurrence relation for the number of multiplications made by this algorithm and solve it$.$