1
Numerical

### GATE CSE 2016 Set 2

The given diagram shows the flowchart for a recursive function $A(n).$ Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O\left( {{n^\alpha }} \right),$ then the least possible value (accurate up to two decimal positions) of $\alpha$ is ____________ .

Correct answer is between 2.2 and 2.4
2

### GATE CSE 2016 Set 2

Match the following:

GROUP - 1 GROUP - 2
(P) Lexical analysis (i) Leftmost derivation
(Q) Top down parsing (ii) Type checking
(R) Semantic analysis (iii) Regular expressions
(S) Runtime environments (iv) Activation records

A
$P \leftrightarrow i,\,\,Q \leftrightarrow ii,\,\,R \leftrightarrow iv,\,\,S \leftrightarrow iii$
B
$P \leftrightarrow iii,\,\,Q \leftrightarrow i,\,\,R \leftrightarrow ii,\,\,S \leftrightarrow iv$
C
$P \leftrightarrow ii,\,\,Q \leftrightarrow iii,\,\,R \leftrightarrow i,\,\,S \leftrightarrow iv$
D
$P \leftrightarrow iv,\,\,Q \leftrightarrow i,\,\,R \leftrightarrow ii,\,\,S \leftrightarrow iii$
3

### GATE CSE 2016 Set 2

Which one of the following grammars is free from $left$ $recursion$?
A
\eqalign{ & S\,\, \to \,\,AB \cr & A\,\, \to \,\,Aa\,\,|\,\,b \cr & B \to c \cr}
B
\eqalign{ & S\,\, \to \,\,AB\,\,|\,\,Bb\,\,|\,\,c \cr & A\,\, \to \,\,Bd\,\,|\,\,\varepsilon \cr & B \to e \cr}
C
\eqalign{ & S\,\, \to \,\,Aa\,\,|\,\,B\,\,|\,\, \cr & A\,\, \to \,\,Bd\,\,|\,\,Sc\,\,|\,\,\varepsilon \cr & B \to d \cr}
D
\eqalign{ & S\,\, \to \,\,Aa\,\,|\,\,Bb\,\,|\,\,c \cr & A\,\, \to \,\,Bd\,\,|\,\,\varepsilon \cr & B \to Ae\,\,|\,\,\varepsilon \cr}
4

### GATE CSE 2016 Set 2

A student wrote two context-free grammars G1 and G2 for generating a single $C$-like array declaration. The dimension of the array is at least one. For example, $${\mathop{\rm int}} \,\,\,\,\,\,\,a[10]\,\,[3];$$

The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num.

Grammar G1 Grammar G2
D → intL; D → intL;
L → id[E L → idE
E → num E → E[num]
E → num][E E → [num]

Which of the grammars correctly generate the declaration mentioned above?

A
Both G1 and G2
B
Only G1
C
Only G2
D
Neither G1 nor G2

### Paper Analysis of GATE CSE 2016 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization6
Data Structures5
Database Management System4
Digital Logic3
Discrete Mathematics11
Operating Systems3
Theory of Computation6
General Aptitude10