Question $3$

$($a$)$ Consider the following list

A$.13,1,16,8,2,0,4,5$

Using Bubbte sort, show ${?}^{{?}^{?}}$ after one iteration $($in ascending order$)$ Show A after the second parsing$/$iteration$.$

$[2$ markes

ii$.$ Use the Merge sort to sort array A in ascending order. Show your work step by step.

$[4$ marks$]$

$($b$)$ Design a Context$-$free Grammar for the following languages:

i$.L=\{a^{n}c{b}^{2n}|n>0\}$

$[4$ marks$]$

ii$.L=\{w|win(ab{)}^{**},N_a(w)>N_b(w)\},N_a(w)$ shows the number of $a\text{'}$s in $w.$ This language contains all strings in which the number of a$\text{'}$s is greater than the number of $b\text{'}$s$.$ For example, strings "abbaaa" and "babaaab" belong to this language while "bbaa" and "abbbabb" do not.

$[5$ marks$]$

$($c$)$ Write the asymptotic function of the following. Prove your claim: if you claim $f(n)=O(g(n))$ you need to show there exist $c,k$ such that $f(n)c*g(n)$ for all $n>k.$

i$.f(n)=2n^3+nlogn+1000$

$[3$ marks$]$

ii$.h(n)=10n+4nlogn+120$

$[3$ marks$]$

$($d$)$ Design a Turing Machine that accepts the following language:

$L=\{a^n{c}^c{b}^n|n>0\}$

marks