Q$1($a$)$ Define a stack and mention its two primitive operations. $($a$)$ Define a queus and mention its two primitive operations.

$($b$)$ Discuss a fixed memory implementation of queuc.

$($c$)$ Define a circular queue Justify its effectiveness.

$($d$)$ Show how a queue can be used to model traffic control at a turning point Show using

pseudocodes implementation of entry and exit of uatfic. $($a$)$ Define $O,Q,$ notations.

$($b$)$ Prove or disprove: $3n^2+4n^{2}logn+5n+2=d(n^{3}logn)$

$($c$)$ Find the solution to the recumrence relation $T(n)=2T(\sqrt[\phantom{2}]{n})+1$ using the Eubstiution

method.

$($b$)$ Show how a stack can be implemenited using linked lists.

$($c$)$ What is a postfix expression? Use a stack to cyaluate the following postfix expression:

$6\mathrm{.}2,3$;$+,-3,8,2,1,+,n,3,{?}^{{?}^{?}},2,+,$$

Here, $\text{'}$S$\text{'}$ marks end of input and $\text{'}$AN denotes exponentiation. Shovy your steps.

G$($d$)$ Briefly explain two different applications of a stack for data processing.