$6\mathrm{.}3$ Many computer applications involve searching through a set of data and

sorting the data. A number of efficient searching and sorting algorithms have been

devised in order to reduce the runtime of these tedious tasks. In this problem we

will consider how best to parallelize these tasks.

$6\mathrm{.}3\mathrm{.}1[10]$$$6\mathrm{.}2>$ Consider the following binary search algorithm $($a classic

divide and conquer algorithm$)$ that searches for a value $x$ in a sorted $N-$element

array A and returns the index of matched entry:

Assume that you have Y cores on a multi$-$core processor to run BinarySearch.

Assuming that $Y$ is much smaller than $N,$ express the speed$-$up factor you might

expect to obtain for values of $Y$ and $N.$ Plot these on a graph.

$6\mathrm{.}3\mathrm{.}2[5]$$$6\mathrm{.}2$: Next, assume that $Y$ is equal to $N.$ How would this affect your

conclusions in your previous answer? If you were tasked with obtaining the best

speed$-$up factor possible $($i$.$e$.,$ strong scaling$),$ explain how you might change this

code to obtain it$.$