PART B

Candidates should answer any TWO questions from Part B$.$

Question $2$

$($a$)$ Using the Master theorem write the time complexity of the following, making every step clear:

$T(n)=3T(\frac{n}{5})+O(n)$

$[4$ marks$]$

$($b$)$

i$.$ Design a context$-$free grammar that accepts the language of all binary strings in which the number of $0$ s is greater than the number of $1$ s $.$ For example, $0001$ and $10100$ should be accepted while $1010$ and $1100$ should not.

$[4$ marks$]$

ii$.$ Modify your context$-$free grammar to accept the language of all binary strings in which the number of $0$ s is greater than the number of $1$ s AND all $0$ s appear before $1$ s $.$ For example, $0001$ and $001$ should be accepted while $10100$ and $11000$ should not.

$[4$ marks$]$

$($c$)$ Design a Turing Machine for the following language:

$L=\{w{w}^R|win(ab)\}$

$w^R$ means reverse of w$.$ For example, $w=$abb $"$ then $w^R=$bba. So$,$ strings such as "abba" and "bbaabb" should be accepted while strings such as "ababa" and "abab" should not.

$[7$ marks$]$

$($d$)$ Among quick sort, insertion sort, merge sort, and bubble sort, which one can sort a list which is almost sorted faster $($i$.$e$.$ more than $90\%$ of elements are in the right place$)?$ Explain your reasoning.

$[5$ marks$]$

$($e$)$ Design a finite state machine to accept all binary strings containing at least one occurrence of $"101".$ For example, $11011$ and $101$ should be accepted while $010,110,0100$ should not.

$[6$ marks$]$