Problem $1$

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.$ What is the maximum number of comparisons your algorithm

makes if the lengths of the two given lists are m and n$,$ respectively?

Problem $2$:

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

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.

Problem $3$:

$1.$ For each of the following algorithms, in

$2.$ dicate $($i$)$ a natural size metric for its

inputs, $($ii$)$ its basic operation, and $($iii$)$ whether the basic operation count can

be different for inputs of the same size:

a$.$ computing the sum of n numbers

b$.$ computing n$!$

c$.$ finding the largest element in a list of n numbers

d$.$ Euclid$$s algorithm

e$.$ sieve of Eratosthenes

f$.$ pen$-$and$-$pencil algorithm for multiplying two n$-$digit decimal integers

Problem $4$

$2.$ a$.$ Consider the definition$-$based algorithm for adding two n $\backslash$times n matrices.

What is its basic operation? How many times is it performed as a function

of the matrix order n$?$ As a function of the total number of elements in the

input matrices?

b$.$ Answer the same questions for the definition$-$based algorithm for matrix

multiplication.

Problem $5$

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$.$ n$^3$

f$.2^$n

Problem $6$:

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 ln n

d$.$ log$22$ n and log $2$ n$2$

e$.2$n$1$ and $2$n

f$.($n $1)!$ and n$!$