$(25$ points$)$ Let $A[1..n]$ be an array of $n$ elements. One can compare in

$O(1)$ time two elements of $A$ to see if they are equal or not; however,

the order relations $$ and $>$ do not make sense. That is$,$ one can check

whether $A[i]=A[j]$ in $O(1)$ time, but the relations $A[i]>A[j]O(nlogn)Akin[1..n]A[1..n]kA\frac{n}{k}n=30$kkkkA$[1..n]O(nlogn)A[1..n]A[1..n]O(nlogn)A[i]=A[j]O(1)A[i]>A[j]A[1..n]A[1..n]A[p..q]p,$qin$[1..n]A[p..q]A[p..q]A[p..q]A[1..n]A[1..n]A[p..q]T(n)T(n)=O(nlogn)A[i]$ and

$A[i]>A[j]$ are undefined and cannot $be$ computed.

Write your algorithm $in$ documented pseudocode. Also, $ex-$

plain $in$ text what your pseudocode does. Explain the cor$-$

rectness $of$ your algorithm.

Since your algorithm uses the divide$-$and$-$conquer principle, $it$ should

$be$ recursive $in$ nature. That $is,it$ should work $onA[1..n]in$ the

first call $to$ return all $10-$major elements $ofA[1..n],$ and $in$ subsequent

recursive calls, $it$ may recurse $on$ many subarrays $A[p..q]$ for some

$p,$qin$[1..n]to$ return all $10-$major elements $ofA[p..q].$

Given a particular subarray $A[p..q],a10-$major element $ofA[p..q]is$

not necessarily $a10-$major element $ofA[1..n].$ Conversely, $a10-$major

element $ofA[1..n]is$ not necessarily $a10-$major element $ofA[p..q].$

$(c)(6$ points$)$ Derive a recurrence relation that describes the running time

$T(n)of$ your algorithm. Explain your reasoning. State the boundary

condition$(s).$

$(d)(2$ points$)$ Solve your recurrence from scratch $to$ show that $T(n)=$

$O(nlogn).A[i]$ and

$A[i]>A[j]$ are undefined and cannot $be$ determined.

$In$ the tutorial you developed $anO(nlogn)-$time divide$-$and$-$conquer algo$-$

rithm for finding a majority element $ofAif$ one exists. $In$ this assignment

you need $to$ generalize this problem.

Let kin$[1..n]be$ a fixed integer. $An$ element $ofA[1..n]isak-$major

element $if$ its number $of$ occurrences $inAis$ greater than$\frac{n}{k}.$ For example,

$ifn=30,$ then $a10-$major element should occur greater than $3$ times

$(i.e.,at$ least $4$ times$).$ Note that $itis$ possible that $nok-$major exists for

a particular $k$; $itis$ also possible that there are multiple $k-$major elements

for a particular $k.$

This problem concerns with designing a divide$-$and$-$conquer algorithm for

finding all $10-$major elements $inA[1..n]inO(nlogn)$ time; $if$ there $isno$

$10-$major element, report $so.$ Answer the following questions.

$(a)(2$ points$)$ What $is$ the maximum number $of10-$major elements $in$

$A[1..n]?$ Explain.

$(b)(15$ points$)$ Design a divide$-$and$-$conquer algorithm that finds all $10-$

major elements $inA[1..n]inO(nlogn)$ time; $if$ there $isno10-$major

element, your algorithm should report $so.$ Recall that one can check

whether $A[i]=A[j]inO(1)$ time, but the relations $A[i]$ and

$A[i]>A[j]$ are undefined and cannot $be$ computed.

Write your algorithm $in$ documented pseudocode. Also, $ex-$

plain $in$ text what your pseudocode does. Explain the cor$-$

rectness $of$ your algorithm.

Since your algorithm uses the divide$-$and$-$conquer principle, $it$ should

$be$ recursive $in$ nature. That $is,it$ should work $onA[1..n]in$ the

first call $to$ return all $10-$major elements $ofA[1..n],$ and $in$ subsequent

recursive calls, $it$ may recurse $on$ many subarrays $A[p..q]$ for some

$p,$qin$[1..n]to$ return all $10-$major elements $ofA[p..q].$

Given a particular subarray $A[p..q],a10-$major element $ofA[p..q]is$

not necessarily $a10-$major element $ofA[1..n].$ Conversely, $a10-$major

element $ofA[1..n]is$ not necessarily $a10-$major element $ofA[p..q].$

$(c)(6$ points$)$ Derive a recurrence relation that describes the running time

$T(n)of$ your algorithm. Explain your reasoning. State the boundary

condition$(s).$

$(d)(2$ points$)$ Solve your recurrence from scratch $to$ show that $T(n)=$

$O(nlogn).$