Q$4.($a$)$ Consider a set of randomly generated integer data whose cardinality is high $(2^{20}).$

Justify which algorithm will be appropriate to arrange this data in order with a proper time$-$

complexity analysis. Provide a pseudocode of i$)$ data generation and ii$)$ your algorithm.

$($b$)$ Suppose you want to find out whether an integer is present in the above data. Justify which

algorithm will be appropriate to achieve this goal with a proper time$-$complexity analysis.

Provide a pseudocode of your algorithm.

$($c$)$ Examine whether a non$-$linear data structure can be used to perform the task in $($a$).$ Q$5.$ Construct two strings $x$ and $Y.$ The string $x$ should contain the first three characters of your

firstname followed by "ETCE". The string Y should contain "ETCE" followed by the last three

characters of your lastname. Clearly show $x$ and $Y.$ Find i$)$ a longest common subsequence of $x$

and $Y$ and ii$)$ a longest common substring of $x$ and $Y.$ In both the cases, you should show the

recursive solution and appropriate table. Analyze the time$-$complexity of your solutions.

Showing pseudocode is not compulsory but can be of help for the construction of the tables.Q$3.($a$)$ What is meant by an asymptotic tight bound? Given: $T(n)=T(\frac{3n}{4})+1.$ Find the tight

asymptotic bound for $T().$

$($b$)$ Find the complexity of $T(n)=4T(\frac{n}{2})+cn$ using the recurslon tree approach.

$($c$)$ Prove that if $f(n)=O(g(n))$ and $g(n)=O(h(n)),$ then $f(n)=O(h(n)).$

$($d$)$ Let $f(ri),g(n)$ be asymptotically nomegative. Show that max

$g(n).$