Consider the following algorithm that takes two sorted lists of

integers $(A[1],$dots,$A[n])$ and $(B[1],..B[m]),$ and tests whether there

are elements $A[i]$ and $B[j]$ so that $|A[i]-B[j]|3.$

For example if the input is: $A[1.\mathrm{.}6]=(40,72,75,101,123,184)$ and

$B[1.\mathrm{.}6]=(13,17,33,38,94,142),$ the algorithm returns True

because $|40-38|3.$

procedure CloseMatch $($A$[1],..,$ A$[$n$]$ ; B$[1],..,$ B$[$m$])$ :

$J=1$;$I=1$;

$.$ While $Jm$ and $In$ do:

$IF|A[I]-B[J]|3$ Return True.

ELSEJ$=J+11in1jm|A[i]-B[j]|3IiJ$jIJt$+1(I_t,J_t,I_{t+1},J_{t+1})|A[I_t]-B[J_t]|3A[I_t]>B[J_t]+3A[I_t]>B[J_t]+3I_t+1J_t+1A[I_t]>B[J_t]+3vnm{J}_t.$

$Q1\mathrm{.}5$

Induction step: For the case $A[I_t]>B[J_t]+3,$ what are

the values $of{I}_t+1$ and $J_t+1?$

$Q1\mathrm{.}6$

Induction step: Show that the invariant holds for the

case $A[I_t]>B[J_t]+3.$ You can use what you proved $in$

$iv.$ and $v.$

$Q1\mathrm{.}7$

Use the invariant $to$ prove that the algorithm $is$ correct.

$(Youdo$ not need $tore-$prove the invariant here, just use

$it.)$

$Q1\mathrm{.}8$

Give a time analysis for this algorithm $upto$ order $in$

terms $ofn$ and $m.$ Explain your answer referring $to$ the

algorithm.IFA$[I]$

ELSEJ$=J+1$

$6.$ Return False.

This algorithm has the following loop invariant: Assume

there are $1in$ and $1jmso$ that $|A[i]-B[j]|3.$

Then $if$ CloseMatch hasn't terminated, $I$i and $Jj.$

Below, you'll give most $of$ the proof $of$ this loop invariant.

We've omitted one case $in$ the interest $of$ time.

$Q1\mathrm{.}1$

Base case: What are the initial values $of$ the relevant

variables and why $do$ these satisfy the invariant?

$Q1\mathrm{.}2$

State the induction hypothesis and goal $of$ the

induction step $in$ terms $of$ the values $of$ the variables $I$

and $J$ before and after the $t+1\text{'}st$ iteration

$(I_t,J_t,I_{t+1},J_{t+1})$

$Q1\mathrm{.}3$

Induction step: For the case $|A[I_t]-B[J_t]|3,$ show

that the invariant remains true $by$ explaining what

happens $in$ the next iteration.

$Q1\mathrm{.}4$

Induction step: For the case $A[I_t]>B[J_t]+3,$ show

that $J_t.$

$Q1\mathrm{.}5$

Induction step: For the case $A[I_t]>B[J_t]+3,$ what are

the values $of{I}_t+1$ and $J_t+1?$

$Q1\mathrm{.}6$

Induction step: Show that the invariant holds for the

case $A[I_t]>B[J_t]+3.$ You can use what you proved $in$

$iv.$ and $v.$

$Q1\mathrm{.}7$

Use the invariant $to$ prove that the algorithm $is$ correct.

$(Youdo$ not need $tore-$prove the invariant here, just use

$it.)$

$Q1\mathrm{.}8$

Give a time analysis for this algorithm $upto$ order $in$

terms $ofn$ and $m.$ Explain your answer referring $to$ the

algorithm.