What topics are covered on Page 2 of GATE 2016 CS/IT Set 2?

Page 2 contains Questions 14 to 26. It covers language closure properties and regular grammars, C programming and loop invariants, processor pipelining, functional units, instruction formats, compiler phases, Selective Repeat ARQ, CSMA/CD, IEEE 802.11 and the DNS-TCP-HTTP sequence used when accessing a web page.

What invariant is maintained by the exponentiation C program in GATE 2016?

The loop maintains the invariant X^Y = res multiplied by a^b while repeatedly reducing the exponent b.

How are compiler phases matched in the GATE 2016 Set 2 question?

Lexical analysis is associated with regular expressions, top-down parsing with leftmost derivation, semantic analysis with type checking and runtime environments with activation records.

What is the purpose of Selective Repeat ARQ?

Selective Repeat allows multiple frames to be outstanding and retransmits only frames that are lost or received incorrectly, rather than resending an entire window.

Which IEEE 802.11 statements are correct in GATE 2016 Set 2?

The protocol provides multiple non-overlapping channels and acknowledges unicast frames. RTS-CTS helps address the hidden-terminal problem; it is not a collision-detection mechanism.

What packet sequence occurs when a restarted host opens a remote web page?

The host first performs DNS resolution, then establishes the TCP connection using a SYN, and only after that sends the HTTP GET request.

CS and IT Gate 2016 Set-2 Questions with Answer

1 2 3 4 5

Ques 14 Gate 2016 Set-2

Consider the following types of languages:

L1 Regular,
L2: Context-free,
L3: Recursive,
L4: Recursively enumerable.

Which of the following is/are TRUE?

I. L3' U L4 is recursively enumerable
II. L2 U L3 is recursive
III. L1* U L2 is context-free
IV. L1 U L2' is context-free

I only

I and III only

I and IV only

I, II and III only

(L) is the correct answer.

Given:
L₁ is a Regular language.
L₂ is a Context-free language.
L₃ is a Recursive language.
L₄ is a Recursively enumerable language.
To find:
Which of the given statements (I, II, III, IV) is/are TRUE.
Solution:
Let me check statement I: L₃' ∪ L₄ is recursively enumerable.
L₃ is recursive, and recursive languages are closed under complementation.
So, L₃' is also recursive.
Every recursive language is also recursively enumerable, so L₃' is recursively enumerable.
Since recursively enumerable languages are closed under union, L₃' ∪ L₄ must be recursively enumerable.
So, statement I is TRUE.
Now let me check statement II: L₂ ∪ L₃ is recursive.
L₂ is context-free, and every context-free language is recursive.
L₃ is already given as recursive.
Since recursive languages are closed under union, the union of two recursive languages is recursive.
So, statement II is TRUE.
Next, let me check statement III: L₁* ∪ L₂ is context-free.
L₁ is regular, and regular languages are closed under Kleene star.
So, L₁* is regular.
Every regular language is context-free, which means L₁* is also context-free.
Since context-free languages are closed under union, L₁* ∪ L₂ is context-free.
So, statement III is TRUE.
Now let me check statement IV: L₁ ∪ L₂' is context-free.
Context-free languages are not closed under complementation, so L₂' need not be context-free.
Therefore, L₁ ∪ L₂' is not necessarily context-free.
So, statement IV is FALSE.
Thus, statements I, II, and III are TRUE.
Answer:
(D) I, II and III only

Ques 15 Gate 2016 Set-2

Language L1 is defined by the grammar:
S1 -> aS1b | ε
Language L2 is defined by the grammar:
S2 -> abS2 | ε
Consider the following statements:

P: L1 is regular
Q: L2 is regular

Which one of the following is TRUE?

Both P and Q are true

P is true and Q is false

P is false and Q is true

Both P and Q are false

(R) is the correct answer.

Given:
Language L₁ grammar: S₁ → aS₁b | ε
Language L₂ grammar: S₂ → abS₂ | ε
Statements:
P: L₁ is regular
Q: L₂ is regular
To find:
Which statement is TRUE among the given options.
Solution:
First, let me look at the language L₁.
Starting from S₁, applying S₁ → aS₁b repeatedly gives strings like ε, ab, aabb, aaabbb, and so on.
So, L₁ = {aⁿbⁿ | n ≥ 0}.
A finite automaton cannot keep track of an arbitrary number of a's to match with b's because it has finite memory.
By the pumping lemma, this is a standard non-regular language.
So L₁ is not regular, which means statement P is false.
Now let me analyze language L₂.
Starting from S₂, the production S₂ → abS₂ generates repeated copies of "ab".
When it terminates with ε, the strings generated are ε, ab, abab, ababab, and so on.
So, L₂ = {(ab)ⁿ | n ≥ 0}.
I can write the regular expression for this directly as (ab)*.
Since it has a valid regular expression and can easily be recognized by a simple DFA with two states, L₂ is regular.
This means statement Q is true.
Hence, P is false and Q is true.
Answer: (C) P is false and Q is true

Ques 16 Gate 2016 Set-2

Consider the following program:

int f(int *p, int n)
{
if (n <= 1) return 0;
else return max(f(p+1,n-1),p[0]-p[1]);
}
int main()
{
int a[] = {3,5,2,6,4};
printf("%d", f(a,5));
}

Note: max(x,y) returns the maximum of x and y.

The value printed by this program is_________-

(a) is the correct answer.

Ques 17 Gate 2016 Set-2

The value printed by the following program is____________

void f(int* p, int m)
{
m = m + 5;
*p = *p + m;
return;
}
void main()
{
int i=5, j=10;
f(&i, j);
printf("%d", i+j);
}

(a) is the correct answer.

Ques 18 Gate 2016 Set-2

The following function computes XY for positive integers X and Y.

int exp(int X, int Y)
{
int res = 1, a = X, b = Y;
while ( b != 0 )
{
if ( b%2 == 0)
{
a = a*a;
b = b/2;
}
else
{
res = res*a;
b = b-1;
}
}
return res;
}

Which one of the following conditions is TRUE before every iteration of the loop

X^Y= a^b

(res ∗ a) ^Y = (res ∗ X) ^b

X^Y = res ∗ a^b

X^Y= (res ∗ a) ^b

(C Code) is the correct answer.

PROCESSED

Ques 19 Gate 2016 Set-2

Consider a 3 GHz (gigahertz) processor with a three-stage pipeline and stage latencies τ₁, τ₂, and τ₃ such that τ₁ = 3τ₂/4 = 2τ₃. If the longest pipeline stage is split into two pipeline stages of equal latency, the new frequency is _________ GHz, ignoring delays in the pipeline registers.

(a) is the correct answer.

Ques 20 Gate 2016 Set-2

Suppose the functions F and G can be computed in 5 and 3 nanoseconds by functional units U_F and U_G , respectively. Given two instances of U_F and two instances of U_G , it is required to implement the computation F(G(X_i )) for 1 <= i <= 10. ignoring all other delays, the minimum time required to complete this computation is ________________ nanoseconds

(a) is the correct answer.

Ques 21 Gate 2016 Set-2

A processor has 40 distinct instructions and 24 general purpose registers. A 32-bit instruction word has an opcode, two register operands and an immediate operand. The number of bits available for the immediate operand field is ____________

(a) is the correct answer.

Ques 22 Gate 2016 Set-2

Match the following

(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

P ↔ i, Q ↔ ii, R ↔ iv, S ↔ iii

P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv

P ↔ ii, Q ↔ iii, R ↔ i, S ↔ iv

P ↔ iv, Q ↔ i, R ↔ ii, S ↔ iii

(Phase of Compiler) is the correct answer.

To match the concepts related to compiler design and runtime environments, let us analyze each item individually.
Analyze each matching pair:
• (P) Lexical analysis: This is the first phase of a compiler where the input source code is broken down into a stream of tokens. The patterns for these tokens (like keywords, identifiers, operators) are typically defined using regular expressions. Finite automata, derived from regular expressions, are used to implement lexical analyzers (scanners).     Therefore, (P) Lexical analysis matches with (iii) Regular expressions.

• (Q) Top down parsing: Top-down parsing is a parsing strategy that starts from the start symbol of the grammar and tries to derive the input string by applying production rules. This process corresponds to constructing a parse tree from the root downwards. A key characteristic of top-down parsers is that they typically produce a leftmost derivation of the input string.     Therefore, (Q) Top down parsing matches with (i) Leftmost derivation.

• (R) Semantic analysis: This phase of the compiler checks for the semantic correctness of the program, ensuring that the code adheres to the language's rules beyond just syntax. A primary task of semantic analysis is type checking, which verifies that operations are applied to compatible data types (e.g., ensuring an integer is not added to a string without proper conversion).     Therefore, (R) Semantic analysis matches with (ii) Type checking.

• (S) Runtime environments: A runtime environment refers to the state of a program during its execution, including memory organization, variable storage, and function call management. Activation records (also known as stack frames) are data structures used to manage information for each active function call. They are pushed onto the call stack when a function is invoked and contain local variables, parameters, return addresses, etc.     Therefore, (S) Runtime environments matches with (iv) Activation records.

Consolidate the matches:
• P ↔ iii
• Q ↔ i
• R ↔ ii
• S ↔ iv

Comparing these matches with the given options, option B aligns perfectly with our findings.

Ques 23 Gate 2016 Set-2

Consider a 128×103 bits/second satellite communication link with one-way propagation delay of 150 milliseconds. Selective retransmission (repeat) protocol is used on this link to send data with a frame size of 1 kilobyte. Neglect the transmission time of acknowledgment. The minimum number of bits required for the sequence number field to achieve 100% utilization is ___________

(a) is the correct answer.

Ques 24 Gate 2016 Set-2

A network has a data transmission bandwidth of 20 × 106 bits per second. It uses CSMA/CD in the MAC layer. The maximum signal propagation time from one node to another node is 40 microseconds. The minimum size of a frame in the network is _________

(a) is the correct answer.

Ques 25 Gate 2016 Set-2

For the IEEE 802.11 MAC protocol for wireless communication, which of the following statements is/are TRUE?

I. At least three non-overlapping channels are available for transmissions.
II. The RTS-CTS mechanism is used for collision detection.
III. Unicast frames are ACKed.

All I, II, and III

I and III only

II and III only

II only

(Computer Network) is the correct answer.

PROCESSED

Ques 26 Gate 2016 Set-2

Identify the correct sequence in which the following packets are transmitted on the network by a host when a browser requests a webpage from a remote server, assuming that the host has just been restarted.

HTTP GET request, DNS query, TCP SYN

DNS query, HTTP GET request, TCP SYN

DNS query, TCP SYN, HTTP GET request

TCP SYN, DNS query, HTTP GET request

(Computer Network) is the correct answer.

PROCESSED

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2016 Set-2 Questions with Answer

Question Options

Sign in to ExamPrev