Computer Science, Paper I

(a) For analyzing an Algorithm theoretically & asymptotically, give a detailed note on Input size, unit of time & order of growth. Support your answer with appropriate mathematical equations.

(b) Briefly describe the four types of analysis we may perform to evaluate the asymptotic behavior of an algorithm.

(c) Evaluate order of growth of the functions given below. Compare & write down which one has higher, same or lower order of growth than the other one:

I. $n(n+1)$ and $2000n^2$

II. $100n^2$ and $0.01n^3$

III. $\text{Log}^2 n$ and $\ln n$

IV. $2^{n-1}$ and $2^n$

V. $(n-1)!$ and $n!$

(a) Design and draw a finite automaton to recognize the regular language of all strings that contain the string ‘001’ as a substring.

(b) Consider the following state diagram and extract the standard information, i.e., Q, $\Sigma$, $q_0$, F and $\delta$.

[figure]

(c) How would you optimize a loop? Describe the techniques briefly.

(a) Discuss the role of Syntax Tree in representing formal text structure. Develop a Syntax Tree structure for the following piece of code:

while b $\neq$ 0

if a > b

a = a - b;

else

b = b - a;

return a;

(b) Describe your understanding on Constant Folding using a brief pseudo code.

(c) What is an Optimization problem? What are its 02 general categories? Write down mathematical representation of a standard optimization problem.