Let $A[1,$dots,$m]$ and $B[1,$dots,$n]$ be two sorted arrays each containing distinct elements. Let $mn$ and

$n$ is a multiple of $m.$ The problem is to determine if the two arrays are disjointed or not. Two arrays are

said to be disjointed if their intersection is $\frac{O}{?}.$

Let us assume that A and $B$ are disjoint. We define $C$ as the sorted combination of A and $B,$ i$.$e$.,$

$C=AB$ and $C$ is sorted. Clearly, $|C|=m+n$ because $AB=\frac{O}{?}.$ Define $D$ of length $m+n$

where $D[i]=1$ if $C[i]inA$ and $0$ otherwise. Give a count of the number of such possible arrays $D.$

Justify your answer.

Solution: INSERT YOUR SOLUTION HERE

We go back to the original problem $-$ we do not know whether $A,B$ are disjoint. Let us assume that

A contains $1$ element, and $B$ contains $2$ elements.

Draw a comparison$-$based decision tree for this problem.

You will also present a modification of the above tree where you will change the label of every

leaf node marked as true with a corresponding array $D.$

You will ensure that your decision tree makes the least number of comparisons possible and has the

shortest height possible. The internal node will be of the form $(i,j)$ which indicates that you are

comparing $A[i]$ and $B[j].$ Now, each such internal node will have three children $-$ one corresponding

to $A[i]=B[j]A[i]>B[j]A,Bm,nDDD(mlog(1+\frac{n}{m}))(\frac{a}{b})(\frac{a}{b}{)}^{b}A[i],$ one corresponding $toA[i]=B[j],$ and one corresponding $toA[i]>B[j].$ The leaf

nodes will contain the values true, false where true indicates that $A,B$ are disjoint and false

indicates the opposite.

Solution: INSERT YOUR SOLUTION HERE

Now $we$ look $at$ the general problem, $i.e.,$ for any $m,n.It$ can $be$ shown $(and$ you will give a proof

$in$ part $(f)$ for extra credit$)$ that the decision tree for this general problem will have every leaf node

labeled true correspond with a distinct array $D,as$ defined $in$ part $(a).$ This $isin$ fact a bijective

mapping, $i.e.,$ every leaf node labeled true has a corresponding array $D$ and every array $D$ has

a corresponding leaf node labeled true Now, using this and your answer from part $(a),$ show that

problem has a worst$-$case lower bound $of(mlog(1+\frac{n}{m})).(Hint$: Use: $(\frac{a}{b})(\frac{a}{b}{)}^b.)$