GATE CS 2016 Official Paper: Shift 2 (Previous Year Paper)

The sentence is talking about the Municipal Commissioner’s previous profession. There cannot be only one security guard at the University. Thus, the indefinite article should precede the security guard. Since the location where he used to work is specific, definite article ‘the’ needs to precede it. Hence the correct option satisfying this criteria is option 2.

The sentence is speaking about the problem that the Indian cricket team will face in Australia. Thus, the best phrase to replace is ‘put up with’.

The correct answer is praise

Key Points

• The words ‘deride’, ‘mock’, ‘jeer’ are synonyms that are negative words meaning to ridicule or make fun of.
• The other word ‘praise’ is a positive word that means to ‘express admiration’. Hence it is the odd one out.

Option D is generating different pattern and hence it is the odd man out

\(\begin{array}{l}
\frac{{{\alpha ^n} + {\beta ^n}}}{{{\alpha ^{ - n}} + {\beta ^{ - n}}}} = \frac{{{\alpha ^n} + {\beta ^n}}}{{\frac{1}{{{\alpha ^n}}} + \frac{1}{{{\beta ^n}}}}}\
= \frac{{\left( {{\alpha ^n}{\beta ^n}} \right)\left( {{\alpha ^n} + {\beta ^n}} \right)}}{{{\alpha ^n} + {\beta ^n}}}\
= {\left( {\alpha \beta } \right)^n} = {4^n}
\end{array}\)

No of members only on Facebook \(= x\)

No of members only on Whatsapp \(= z\)

No. of members on both \(= y\)

No of members on neither \(= w\)

\(\begin{array}{l}
x + y + z + w = 150\
x + y = 55\
y + z = 85,;w = 30\
x + y + z = 120\
x = 120-85;\
x = 35
\end{array}\)

The passage states how computers have taken over the world today. The last line of the passage helps us infer that though the author understands how the new developments like computers have helped us, he is dubious as to whether these developments are actually beneficial or required.

The first inference does not hold.

The second inference does not hold because the passage clearly states that many people feel that the internet is an unintended invention.

Let us look at the inferences one by one.

Since all hill stations have lakes and Ooty has two lakes, then Ooty must be a hill station.

The second inference does not follow because there can be no fixed rule as to how many lakes must a hill station have.

Thus none of the inferences follow.

Data:

number of rows = n = 2

number of columns = m = 4

Formula:

\(number ;of ;rectangles =( \frac{n×(n+1)}{2})×(\frac{m×(m+1)}{2} )\)

Calculation:

\(number ;of ;rectangles =( \frac{2×(2+1)}{2})×(\frac{4×(4+1)}{2} )\)

number of rectangles = 3 × 10 = 30

Putting the values shown is graph, option (C) matches.

Concept:

P ⇒ Q means P̅ ∨ Q

Explanation:

P ∧ (P ⇒ Q) = P ∧ (P̅ ∨ Q) = P ∧ Q

Let us consider P.Q as A.

We have to find which of the given expression is implied by A, that is, (A => )

Construct the truth table for each option separately

Let A ≡ P ∧ (P ⇒ Q)

Consider all options one by one:

(i) False

Here, all are not true. So, this option is incorrect.

(ii) Q

This option is implied by P ∧ (P ⇒ Q).

iii) True

iv) P ∨ Q

This is a tautology. So, option is correct.

v) –Q ∨ P

This is also a tautology.

So, total 4 are implied by the given expression.

Given that, degree of (f(x) + f(– x)) is 10.

Consider f(x) polynomial as a¹⁰.

f(x) + f(– x) = a¹⁰ + (– a)¹⁰

= a¹⁰ + a¹⁰ = a²⁰

g(x) – g(– x) = 10a⁹ – (– 10a⁹) [given that g(x) = f’(x) ]

= 20 a⁹

From this, degree of g(x) – g(–x) is 9.

Concept:

A planar graph is a graph in which no two edges cross each other. A vertex coloring of a graph is an assignment of colors to the vertices of graph such that adjacent vertices have different colors.

Explanation:

According to the property of planar graph and four colour theorems. Maximum number of colours that are needed to vertex-colour any planar graph is 4.

Example:

In this graph, only 3 colours are enough to colour this planar graph.

But if in this graph, there is an edge from a to d also, then three colours are not enough to vertex-colour this graph.

In this graph, 4 colours are needed to vertex- colour this graph.

Statement I:

If m < n, then all such systems have a solution [incorrect]

Let us suppose m = 2, n = 3

x + y + z = 3

x + y + z = 5

here, this will not give any solution. Because, when we have 2 equations with 3 variables, we can’t find the solution for this.

Statement II:

If m > n, then none of these systems has a solution [incorrect]

Consider, m = 3, n = 2

System of equation will be like:

x + 2y = 2

x + y = 1

2x + 5y = 5

But here we can easily find the value of x and y.

Statement III:

If m = n, then there exists a system which has a solution [Correct]

Consider m = 2, n = 2

System of equation will be like:

x + 2y = 3

2x + 4y = 4

Here, x and y can be calculated. These systems of equations have a solution.

Data:

P (LED is of type 1) = P(T₁) = ½ = 0.5

P (LED is of type 2) = P(_T2) = ½ = 0.5

\({\rm{P;}}\left( {\frac{{{\rm{LED;lasting;more;than;}}100{\rm{;hours}}}}{{{\rm{LED;is;of;type;}}1}}} \right) = {\rm{P;}}\left( {\frac{{\rm{H}}}{{{{\rm{T}}_1}}}} \right) = 0.7\) 

\({\rm{P}}\left( {\frac{{{\rm{LED;lasting;more;than;}}100{\rm{;hours}}}}{{{\rm{LED;is;of;type;}}2}}} \right) = {\rm{P;}}\left( {\frac{{\rm{H}}}{{{{\rm{T}}_2}}}} \right) = 0.4\) 

Formula:

\({\rm{P}}\left( {\rm{H}} \right) = {\rm{P}}\left( {{{\rm{T}}_1}} \right) \times {\rm{P;}}\left( {\frac{{\rm{H}}}{{{{\rm{T}}_1}}}} \right) + {\rm{P}}\left( {{{\rm{T}}_2}} \right) \times {\rm{P;}}\left( {\frac{{\rm{H}}}{{{{\rm{T}}_2}}}} \right)\)

Calculation:

P(H)= 0.5 × 0.7 + 0.5 × 0.4 = 0.55

Therefore, the probability that an LED bulb chosen uniformly at random lasts more than 100 hours is 0.55

Concept:

Determinant of a matrix is the product of its eigenvalues.

Determinant of a matrix is same as its transpose.

Determinant of a matrix is reciprocal to its inverse.

Calculation:

Eigenvalues of matrix A are 1, 2 and 4.

Determinant of matrix A = 1 × 2 × 4 = 8

Determinant of inverse of A = det (A^-1) = \(\frac{1}{{{\rm{det}}\left( A \right)}} = ;\frac{1}{8} = 0.125\)

det (A-1) = det (A-1)^T = 0.125

Concept:

Longest latency for the sum to stabilize is the maximum time or delay a ripple carry adder take to add A and B.

Explanation:

Given A = 1 in decimal form,

In 2’s complement form, binary representation of A in binary form = 0000 0001.

In case of ripple carry adder, for sum we need 2 XOR gates.

For the longest latency, we must have C_in = 1 at every stage of the ripple carry adder.

Here, we have to find the value of B such that we get C_in= 1 at every stage and C_out = 1 at the last stage.

Maximum delay is when we take B = -1 in decimal (1111 1111 – in binary)

On adding A + B, we get a carry up to the carry flag i.e. longest latency.

Concept:

XOR gate is a gate that gives a true output when the number of true inputs is odd.

Explanation:

Given, x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0

Where, x₁, x₂, x₃, x₄ are Boolean variables, and ⊕ is the XOR operator

Consider x₁ = 1, x₂ =1, x₃ =1 and x₄= 1

1 ⊕ 1 ⊕ 1 ⊕ 1 = 0

Now, consider all the options one by one.

1. x₁x₂x₃x₄ = 0 [Incorrect]

Here, put the value of x₁,x₂, x₃, x₄ as 1

So, 1.1.1.1 = 1

2. x₁x₃ + x₂ = 0 [Incorrect]

1.1 + 1 =1

3. x̅₁ ⊕ x̅₃ = x̅₂ ⊕ x̅₄ [Correct]

Here, x̅₁ = x̅₃ = x̅₂ = x̅₄ = 0,

So, 0 ⊕ 0 = 0 ⊕ 0,

0 = 0

4. x₁ + x₂ + x₃ + x₄ = 0 [Incorrect]

As, 1+1+1+1 = 1

2's Complement Representation 

The range of n-bit 2's complement numbers is -2^n-1 to 2^n-1-1.

For example, if n=2, then -2, -1, 0, 1 belong to the range (which are distinct).

In general, 2n distinct integers are possible with n-bit 2's complement number → X

Sign Magnitude Representation

The range of n-bit sign magnitude numbers is - (2^n-1 - 1) to (2^n-1 -1)

For example, if n=2, then -1, -0, +0, +1 belong to the range in which -0 = +0 and both represent zero.

In general, 2ⁿ-1 distinct integers are possible with n-bit sign magnitude representation → Y

X - Y = 2n - 2n-1=1.

Hence, the correct answer is 1.

40 distinct instructions → log₂40 = 6 bits are needed for opcode.

24 general purpose registers → log₂ 24 = 5 bits for register operand.

As, two register operands are required so, total 10 bits are needed for register operand field.

Suppose for immediate operand we require x bits.

Opcode + Register operand + Immediate operand = 32

6 + 10 + x = 32

∴ x = 16

Number of bits available for the immediate operand field (x) is 16 bits.

At a distance four from the root, tree will be like:

In this tree, maximum possible value of n at a distance 4 from the root is 31.

Alternate solution:

A tree with height h has maximum number of nodes = 2^h+1 – 1

Here it is given that t is the nth vertex at a distance 4. We have to find the maximum value of n.

Here height = 4

Maximum value of n = 2⁴⁺¹ – 1 = 31

Code Explanation:

In this code, address of i is passed to the function and value of j is passed.

Given i =5, j= 10

void f (int* p, int m) { //here p points to address of i and m contains 5

            m = m + 5; // m becomes 15

            *p = *p + m; // p becomes 20

            return;

}

When call returns back to the main function, i value changes to 20 but j will remain same.

So, printf (‘’%d’’, i + j); // 20 + 10 = 30 is printed

Input is already in ascending order, means it is the worst-case situation.

Option 1:

Quicksort runs in Θ (n²) time

In quick sort worst case, first or last element is selected at the pivot element.

For a quicksort, in worst case recurrence relation will become T(n) = T(n-1) + T (1) + n

Which gives T(n) = Θ (n²)

So, it is correct.

Option 2:

Bubble sort runs in Θ (n²) time

If array is already sorted in ascending order, then at that time there will be no swap after the completion of inner for loop of bubble sort. In this way, bubble sort will take Θ (n) time complexity.

Option 3:

Merge sort runs in Θ (n) time

Merge sort uses the divide and conquer policy to sort the elements. As elements are already sorted in ascending order. Recurrence relation for merge sort; T(n) = 2 T (n/2) + n

This will give Θ (nlogn) time complexity.                        

Option 4:

Insertion sort runs in Θ (n) time

When a new element which is greater than all the elements of the array is added, then there will be no swap but only a single comparison. In n -1 swaps, only 0 swaps and n-1 comparisons are there.

Total time complexity in this case will be Θ (n).

Floyd Warshall algorithm is based on dynamic programming paradigm.

It finds the all pair shortest paths:

Consider for every pair (i, j), there are two possible cases:

1. k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.

2. k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][j] + dist[.k][j]

This diagram shows it:

While using dynamic programming paradigm, we computer all pair shortest path time complexity is O(V³).

Here, it is given that pointer is provided to the record on which the decrease key operation is to be performed. So, time complexity of decrease key operation is Θ (1)

For insert – Θ (N), we need to insert the element at the end of the sorted list.

For delete – Θ (1) time is needed, as pointer is directly given

For decrease key – Θ (N), because after decreasing the key value, all the elements must be sorted again.

Now combining all the operations together:

For delete = Θ (N)* Θ (1) [because Θ(N) delete operations ]

For insert = Θ (log N)*Θ (N) [because Θ(logN insert operations are given)]

For find = Θ (log N)*Θ (N)

For decrease-key = Θ (N)* Θ (N)

So, overall complexity = Θ (N)* Θ (1 ) + Θ (logN)* Θ (N) + Θ (logN)* Θ (N)+ Θ (N)* Θ (N)

Time complexity of all these operations put together = Θ (N²)

Given regular expression: (0 + 1)(0 + 1)(0 + 1)

In this, there is atleast one appearance of (0 + 1).

It generates strings of type {0, 1, 00, 01, 10, 11, 000, 001, 011, ……. }

DFA for the given expression is:

Number of states in minimum sized DFA for this regular expression = 2

Suppose grammar G1:

S₁ → aS₁b|ϵ

It generates language in which number of a’s are equal to number of b’s and all a’s are followed by b’s

L₁ = { aⁿ bⁿ | n ≥ 0}.

It is deterministic context free language. Extra memory is required for this. So, it can’t be accepted by finite state automata. L₁ is not a regular language.

Now, another grammar let G2: S₂ → abS₂|ϵ

This grammar also generates language in which number of a’s are equal to number of b’s. But it generates language L₂ = { (ab)ⁿ | n ≥ 0 }

Regular expression for this = (ab)*

It doesn’t require any extra memory to remember the last string. It can be accepted by finite state automata. So, L₂ is regular.

L₁: Regular

L₂: Context-free

L₃: Recursive

L₄: Recursively enumerable

Statement I: TRUE

 L̅₃ ∪ L₄ is recursively enumerable

As L₃ is recursive language and complement of a recursive language is also recursive.

L₄ is recursive enumerable. So, L̅₃ ∪ L₄ is recursive enumerable.

Statement II: TRUE

II. L̅₂ ∪ L₃ is recursive

L₂ is context free language. Context free languages are not closed under complementation. Complement of a context free language is context sensitive also recursive. L₃ is recursive.

So, union of two recursive languages is recursive.

Statement III: TRUE

III. L₁^* ∩ L₂ is context-free 

Kleen closure of regular language is regular. Intersection of a regular language and context free language is context free.

Example:

Regular language = \(L^*_1 = (a + b)^*\)

L₂ = aⁿ bⁿ

The intersection of \(L^*_1 \cap L_2 = a^nb^n\) is a context-free language 

Statement IV: FALSE

L₁ ∪ L̅₂ is context-free

Complement of L₂ is not context free.  L₁ ∪ L̅₂ may or may not be context free.

Therefore, the statement I, II and III are correct.

Lexical analysis: Lexical analysis is the first phase of a compiler. It takes the modified source code from language pre-processors that are written in the form of sentences.  Lexical analyser breaks these syntaxes into a series of tokens. Lexical analysis uses regular expression to recognize identifiers.

Top down parsing: Top down parsing technique parses the input by starts constructing a parse tree from the root node moving down to the leaf nodes. Top down parser uses the left most derivation to generate the string.

Semantic analysis: Semantic analysis is the task of ensuring that declarations and statements of a program are semantically correct. For this, it uses type casting.

Run time environments: Run time environment is a state of the target machine, which may include software libraries, environment variables etc. to provide services to the processes running in the system. Activation records of a function are loaded into stack at runtime.

Concept:

Belady’s anomaly is the phenomenon in which increasing the number of page frame results in  increase in the number of page faults.

Explanation:

FIFO replacement algorithm results in page faults by increasing the number of page frames.

Consider the example:

Frame = 3

String = 0 1 5 3 0 1 4 0 1 5 3 4

Number of page faults = 9

Take number of frames = 4

Number of page faults = 10

B+ Tree is an extension of B tree which allows efficient insertion, deletion and search operations.

In a B+ Tree, records (data) can only be stored on the leaf nodes while internal nodes can only store the key values. Leaf nodes of a B+ Tree are linked together in form of linked list to make the search operation efficient.

In a B+ Tree, all leaves are at the same level. In both B Tree and B+ Tree, length of root to leaf nodes is same. In B+ Tree, insertion is done in a way such that if we increase height of tree after insertion, we increase height from the root. While in BST, height of tree after insertion increased from leaf nodes.

Similarly, if we have to decrease the height of the tree after deletion, we move the root one level down.

So, this will make sure that depth of leaf nodes are same and B+ Tree are balanced trees.

Insertion example:

Insert 195,

Final, B+ Tree will be:

Deletion example:

Delete 200 from above tree

Now, 120 is the single element violating the property of B+ tree so, merge it and height of tree will be decreased by 1.

Serial schedule is possible only when precedence graph doesn’t contain cycle. If precedence graph contains a cycle, it means schedule is not conflict serializable.

Breadth first search and Depth first search of a graph are possible even if graph contains cycle.

Topological sort in a graph will not work if graph contains a cycle.

Consider a directed acyclic graph:

Here Two orders possible: V2, V3, V1, V4, V5, V6 OR V3, V2, V1, V4, V5, V6.

In case of ascending order of transaction indices, two non-conflicting schedules can occur simultaneously.

Concept:

Digital signature is a cryptographic value that is calculated from the data and a secret key known only by the signer. In real world, the receiver of message needs assurance that the message belongs to the sender and he should not be able to repudiate the origination of that message.

In Digital signature:

Encryption is done by sender’s private key and decryption is done by sender’s public key.

Here, it is given that Anarkali digitally signs the message and sends it to the Salim. As, Anarkali signs the message with her private key and Salim (receiver ) uses the Anarkali’s public key to verify the signature.

Ethernet is a way of connecting computers together in a local area network (LAN). Ethernet operates in two layers of OSI model, physical and data link layer. In order to handle the collision in Ethernet, access control mechanism used is CSMA/CD.

1. A station stops to sense the channel once it starts transmitting a frame.

In Ethernet, a station need not stop sensing the channel once it starts transmitting a frame. So, it is false

2. The purpose of the jamming signal is to pad the frames that are smaller than the minimum frame size.

Jamming signal in Ethernet is signal that carries 32-bit binary pattern sent by a data station to inform other stations of the collision. It is not true that the purpose of jamming signal is to pad the frames that are smaller than the minimum frame size.

3. A station continues to transmit the packet even after the collision is detected. Once the collision has occurred, jam signal will be sent and after that station will stop transmitting the packet. So, it is incorrect.

4. The exponential back-off mechanism reduces the probability of collision on retransmissions.

Exponential back off algorithm is used to space out repeated retransmissions of the same block of data to avoid network congestion. It is a collision resolution mechanism which is used in random access MAC protocols. So, it is correct.

During packet transmission, first step is to make the DNS query.

Whenever client makes a query, server identify the DNS. DNS (domain name server) query is used to identify the address of DNS.

After this, a TCP connection is to be established for further communication. TCP connection will be established by sending TCP SYN message.

After connection establishment, HTTP GET request to the server to retrieve the webpage it should display. After the server has sent the response, it closes the TCP connection.

Concept:

Reflexive relation: Reflexive relation on a set is a binary element in which every element is related to itself. Let A be a set and R be the relation defined in it. R is set to be reflexive, if (a,a) ϵ R for all a ϵ A i.e. every element of A is related to itself.

Transitive relation: A binary relation R on a set A is transitive if whenever an element ‘a’ is related to an element ‘b’ and ‘b’ in turn is related to an element ‘c’, then a is also related to ‘c’.

For all, a, b, c ϵ A if aRb and bRc then aRc.

Explanation:

Here, it is given that:

(a, b)R(c, d) if a ≤ c or b ≤ d

Statement P: R is reflexive → TRUE

For R to be reflexive (a, b) R (a, b) should hold true.

Here, a ≤ a or b ≤ b

So, (a, b) R (a, b) holds true. R is reflexive.

Statement Q: R is transitive → FALSE

Consider the elements as (4, 5), (5, 1), (1, 1)

As, (4, 5) R (5, 1) so, 4 ≤ 5 or 5 ≤ 1

And (5, 1) R (1, 1) so, 1 ≤ 1

But here, (4, 5) R (1, 1) where, 4 ≥ 1 and 5 ≥ 1

For this, relation doesn’t hold true,

So, Relation R is not transitive.

Concept:

p ⇒ q means ¬p ∨ q

It means that p is true, and q is false, in that case this implication fails.

Explanation:

Consider, p(x) = x is a prime number

q(x) = x is a non-prime number

Option 1:

(∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬ p(x) ∨ ∀x q(x))   

In this, case after implication it becomes true and in case implication if there is true after implication then that predicate is valid. (∃x ¬ p(x) ∨ ∀x q(x)), this will become true by the example.

Option 2:

(∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x))   

This implication is also valid. In this, before implication it will become false. So, it is valid.

Option 3:

∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))  

There exists a number x, which is both prime and non-prime which is false. A false statement can imply either true or false. So, it is valid.

Option 4:

∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x))  

Here, before implication, for all x, x is either prime or non-prime which is true.

After implication, for all x, x is prime or for all x, x is non-prime which is false. So, here a true statement implies a false statement which results in false. So, it is not valid.

Here, it is given that U contains 23 different compounds i.e U= 23

S is the subset of U i.e. S= 9

U\S = 23 – 9 = 14

Consider this as a graph where U is the vertex set of graph G and S is the subset of vertices in G.

Now, it is given that S reacts with exactly 3 compounds of U. It means degree of every vertex is 3.

Sum of degree of every node of S = 9 × 3 = 27

U\S contains even number of compounds.

Statement I: Each compound in U\S reacts with an odd number of compounds.

Here, if each compound in U\S reacts with odd number of compounds, the sum of degree of all the nodes in U\S will be even and sum of degree of all nodes in graph G will be odd as sum of degree of all nodes in S is odd. This is not possible using handshaking lemma. So, Statement I is false.

Statement II: At least one compound in U\S reacts with an odd number of compounds.

To satisfy the handshaking lemma for graph, sum of degree of all nodes U\S must be odd. To make this happen, we require atleast one node of U\S with an odd degree. We can assign it in such a way that sum of degree of all nodes in U\S will be odd. So, it is true.

Statement III: Each compound in U\S reacts with an even number of compounds.

If each compound in U\S reacts with an even number of compounds, sum of degree of all nodes in U\S will become even and sum of degree of all nodes in graph will become odd as sum of degree of all nodes in S is odd. And an odd number added with an even number of results in an odd number. To satisfy the handshaking lemma, sum of degree of all nodes in the graph must be even. So, it is false.

Generate the cyclic patter

13¹ (mod17) ≡ 13

13² (mod17) ≡ 16

13³ (mod17) ≡ 4

13⁴ (mod17) ≡ 1

13⁵ (mod17) ≡ 13

13⁶ (mod17) ≡ 16

13⁷ (mod17) ≡ 4

Pattern → (13, 16, 4, 1)

13⁹⁹ (mod 17) = 13^{4×24 + 3} (mod 17) ≡ 13³ (mod 17) ≡ 4

Alternate Method:

13⁹⁹ (mod 17)

= (-4)⁹⁹ mod 17

= [(-4) × ((-4)²)⁴⁹] mod 17

= [ (-4) × (16)⁴⁹] mod 17

= (-4) mod 17 × (16)⁴⁹ mod 17

= (-4) × (-1)⁴⁹ mod 17

= (-4) × (-1) = 4

Concept:

Pipeline is an implementation technique where multiple instructions are overlapped in execution. Pipeline increases the throughput.

Two instances of U_F and two instances of U_G and hence two instruction can be executed in parallel manner, also consider G should be 1^st stage and F be the 2^nd stage since computation is implemented as F(G(X))

Calculation:

The minimum time required to complete this computation is 28 nanoseconds

Data:

Number of registers = 64

Number of bits to address register = 6

Number of instructions = 12

Opcode size = 4 bit

Two source registers require 12 bits (6 + 6)

Calculation

Total bits per instruction = 4 + 6 + 6 + 6 + 12 = 34 bits

In terms of bytes= 34/ 8 = 4.25 bytes

Here, given that each instruction must be stored in byte aligned manner so we will take 5 bytes instead of 4.25 bytes.

Total instructions = 100

Total size = 100 × 5 = 500 bytes

Data:

Physical address (PA) = 40 bits

Cache Memory Size (CS) = 512 KB = 2¹⁹ B

Block Size (BO) = 2^x B

Set associativity = 8

Formula:

Formula to find number of bits in tag in set associative mapping

PA = tag + set + BO

\({\rm{number;of;set}} = \frac{{{\rm{CS}}}}{{{\rm{S}} \times {\rm{BO}}}}\)

Calculation:

\({\rm{number;of;set}} = \frac{{{2^{19}}}}{{{2^3} \times {2^{\rm{x}}}}} = {2^{19 - 3 - x}}\)

PA = tag + set + BO

40 = tag + 19 – 3 – x 

∴ tag = 24 bits

Important Points:

Assume: Memory is byte addressable

Data:

3- stage pipeline with 3 GHz processor

τ₁ = 3τ₂/4 = 2τ₃

Calculation:

put, τ₂ = 8x

So, τ₁ = 6x and τ₃ = 3x

As, cycle time = max (all stage delays)

maximum stage delay = 8x

\({\rm{frequency}} = \frac{1}{{{\rm{cycle;time}}}}\)

\({\rm{frequency}} = \frac{1}{{8{\rm{x}}}}\)

\(3GHz = ;\frac{1}{{8x}};\)

\(\frac{1}{x} = 24GHz;\)

Now, longest pipeline, that is, 8x is split into two equal latency stages: 4x and 4x

Now, maximum stage delay become 6x

\({\rm{New;frequency}} = \frac{1}{{6{\rm{x;}}}} = \frac{{{\rm{;}}1}}{6} \times \frac{1}{{\rm{x}}} = \frac{1}{6} \times 24 = 4{\rm{;GHz}}\)

Concept:

Min- heap is a binary tree such that data contained in each nodes is less than (or equal to ) the data in that node’s children.

We have to consider the integers in the range [1, 1023].

It is also given that root is at depth 0. As it is a min heap so integer 1 has to be at root only.

Tree will become:

Now, once we place 1 – 9 then remaining elements can be placed easily to fill the min-heap.

Here, the maximum depth at which integer 9 can appear is 8.

Consider X = 2, Y = 5,

Before iteration 1: res =1, a = 2, b = 5, X = 2, Y = 5

For these values all options are true.

After iteration 1 and before iteration 2:

if (b%2 == 0) {a = a*a; b = b/2;}

else                 { res = res*a; b = b-1; }                       // res = 2, b= 4

      }

So, res = 2, a= 2, b= 4, X = 2, Y = 5

After iteration 2 and before iteration 3:

if (b%2 == 0) {a = a*a; b = b/2;}                           // a = 4, b =4/2 =2

else                 { res = res*a; b = b-1; }                      

    }

Res = 2, a= 4, b= 2, X = 2, Y =5

After iteration 3 and before iteration 4:

if (b%2 == 0) {a = a*a; b = b/2;}                           // a = 16, b =2/2 = 1

else                 { res = res*a; b = b-1; }                      

   }

res = 2, a= 16, b = 1, X = 2, Y = 5

After iteration 4 and before iteration 5 :

 if (b%2 == 0) {a = a*a; b = b/2;}                          

else                 { res = res*a; b = b-1; }                       // res = 32, b = 0

}

After this, while condition becomes false

Before all these iterations, only option c will be true for these values, All other become false before iteration 2.

In case of reverse polish notation, we follow the:

1. visit left subtree

2. visit right subtree

3. visit root

New order strategy is given as:

1. visit root

2. visit right subtree

3. visit left subtree

It is the reverse of reverse- polish notation.

So, for finding the new order traversal of given reverse polish notation just reverse that:

Reverse polish traversal: 3 4 * 5 – 2 ^ 6 7 * 1 + -

New order traversal:  – + 1 * 7 6 ^ 2 – 5 * 4 3

Alternate solution:

Convert the given reverse polish notation in IN- order

3 4 * 5 – 2 ^ 6 7 * 1 + -

(3 * 4) 5 – 2 ^ 6 7 * 1 + -

((3*4) - 5) 2 ^ 6 7 * 1 + -

(((3*4) - 5)^ 2) 6 7 * 1 + -

(((3*4) - 5)^ 2) (6 * 7) 1 + -

(((3*4) - 5)^ 2) ((6 * 7) + 1)

(((3*4) - 5)^ 2) - ((6 * 7) + 1)

Now, from this inorder traversal, find the new order traversal;

(((3*4) - 5)^ 2) - ((6 * 7) + 1)

• ((6 * 7) + 1) (((3*4) - 5)^ 2)
• • 1 (6 * 7) (((3*4) - 5)^ 2)
• • 1 * 7 6 (((3*4) - 5)^ 2)
• • 1 * 7 6 ^ 2 ((3*4) - 5)
• • 1 * 7 6 ^ 2 - 5 (3*4)
• • 1 * 7 6 ^ 2 - 5 * 4 3

Hence option 3 is correct.

Consider the base address as 100 and integer takes 4 bytes so, address will increment in terms of 4 bytes.

Final output: 3

Concept:

If we multiply two matrices of order l × m and m × n,

then number of scalar multiplications required = l × m × n

Data:

A₁ = 10 × 5, A₂ = 5× 20, A₃ = 20 × 10, A₄ = 10 × 5

Calculation:

There are 5 ways in which we can multiply these 4 matrices.

(A₁A₂)(A₃A₄) , A₁A₂(A₃A₄), A₁ ((A₂A₃) A₄) , (A₁(A₂A₃))A₄, ((A₁A₂)A₃)A₄

Minimum number of scalar multiplication can be find out using A₁ ((A₂A₃)A₄)

For A₂A₃ (order will become 5 ×10) = 5 × 20 × 10 = 1000

For (A₂A₃)A₄ (order will become 5 × 5) = 5 × 10 × 5 = 250

For A₁ ((A₂A₃)A₄) [Order will become 10 × 5] = 10×  5 × 5 = 250

Minimum number of scalar multiplication required = 1000 + 250 + 250 = 1500

In all other cases, scalar multiplication are more than 1500.

To find the worst-case time complexity of the function.

Worst case happens in case of recursive. So, find out the recursive calls on the longer route.

There are 5 such recursive calls to A (n/2).

So, recurrence relation will become like:

A (n) = 5A (n/2) + O(1)

where O(1) is constant

By using master’s theorem,

a = 5, b =2

\({\rm{O}}\left( {{{\rm{n}}^{{{\log }_2}5}}} \right) = {\rm{;O}}({{\rm{n}}^{2.32}})\)

\({\rm{O}}({{\rm{n}}^{\rm{\alpha }}}) = {\rm{O}}({{\rm{n}}^{2.32}}){\rm{;}}\)

α = 2.32

Resulting tree must have height = 6

So, root must be either 1 or 7

For node 1 (also for node 7):

Possible permutations are = \(\frac{{6!}}{{6!0!}} = 1\) 

For node 2 (also for node 6):

Possible permutations are = \(\frac{{6!}}{{5!1!}} = 6\)

For node 3(also for node 5):

Possible permutations are = \(\frac{{6!}}{{4!2!}} = 15\)

For node 4:

Possible permutations are = \(\frac{{6!}}{{3!3!}} = 20\)

Number of ways in which nodes are inserted to get height 6 = 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64

We perform a BFS here. Suppose 1 is adjacent to 2 hence 2 is also adjacent to 1, in adjacency list we create one node in linked list for a vertex if it is adjacent. So, 1 and 2 are twins. Linked list of 1 will have entry for 2 and linked list of 2 will have entry for 1. In this way, we can have pointers for all twins in O (m + n) time. Level order traversal is required here.

Graph:

Adjacency list:

Also, extra field is there for storing number of linked lists for each vertex which is extra space. (But here memory size is not a constraint).

Overall time complexity to set the twin pointer in each entry in adjacency list is O(m + n).

Statement I:

If all states of an NFA are accepting states, then the language accepted by the NFA is ∑*. (FALSE)

If we have an NFA with one state and on it, we did not define any transition then it accepts only null not ∑*.

Also, while converting an NFA to DFA, a dead state may be there. So even though all the final states of DFA have all transition, a few transitions may go to a dead state. Hence, that string will not be accepted.

If the string is b then is not accepted by the given NFA and b ⊂ ∑*

Here, in this, it is not accepting string b or strings that start with b. So, it is not accepting ∑*.

Statement II:

There exists a regular language A such that for all languages B, A ∩ B is regular. (TRUE)

There exists a regular language A= Ø, such that Ø ∩ B = Ø which is a regular language.

So, this statement is true.

Statement I: L₁ = {aⁿ b^m c^{n + m}: m, n ≥ 1}

L₁ can be accepted easily by single stack. First, push a’s into stack, then push b’s into stack then read c’s and pop b’s, when no b’s left on stack, then keep reading c’s and pop a’s. When no c’s left in input and stack is empty then accepted by only one stack. Hence L₁ is a context free language.

Statement II: L₂ = {aⁿbⁿc²ⁿ: n ≥ 1}

This language can’t be accepted by a single stack. When we push a’s into stack and pop them with b’s then it satisfies number of a’s = number of b’s but we left with empty stack and c’s in input. We can’t ensure that number of c’s are double than a and b’s. A push down automata can’t remember number of a’s for third set of characters, that is. c.

Hence L₂ is a context sensitive language but not context free language.

Statement I:

L1 = { <M> | M takes at least 2016 steps on some input},

This language is decidable, because counting number of steps can always be decided. We can find TM whether it takes more than 2016 steps on some input string which has length up to 2016. If it processes 2016 steps till end, then will take at least 2016 steps. But if these are not taking 2016 steps, it means these have taken at most 2015 steps which means string is not processed completely. Also, if Turing machine reaches the halt state before reaching the end of string of input, it can be decided. In all cases, Turing machine M is recursive.

Statement II:

L2 = { <M> | M takes at least 2016 steps on all inputs}

For this, consider M makes less than 2016 steps for some input and we can just give it all possible inputs of length less than 2016 steps and check if it can reach a halt state within 2016 steps.

All the possible strings make a finite set. Thus, accepted by Turing machine. Hence, it is recursive language.

Statement III:

L3 = { <M> | M accepts ϵ},

It is based on the concept of rice theorem i.e. any non - trivial property of the language recognizable by a Turing machine is undecidable. As this language contains ϵ which is non – trivial property of recursive enumerable language and hence undecidable. Hence, it is not recursive.

Method: By option elimination

Option 1:

S → AB

A → Aa | b

B → c

Here, there is a left recursion in “A → Aa”

Option 3:

S → Aa | B

A → Bb | Sc | ϵ

B → d

Since, S → Aa and A → Sc which will result in S → Sca

So, it results in a left recursion.

Option 4:

S → Aa | Bb | c

A → Bd | ϵ

B → Ae | ϵ

Since A → Bd and B → Ae

which results in left recursion, A → Aed or B → Bde

Option 2:

S → Ab | Bb | c

A → Bd | ϵ

B → e

This grammar doesn’t include direct left recursive statement or indirect left recursive statement production.

Grammar G1 is:

D → int L;

L → id [E

E → num]

E → num] [E

Generate one dimensional array: a[10]

D → int L

→ int id[E

→ int id[num]

This leads to int a[10]

Generate two-dimensional array: int a [10] [3];

D → int L;

→ int id [E;

→ int id [num] [E;

→ int id [num] [num];

This leads to int a[10][3]

It correctly generates declaration given.

Grammar G2 is:

D → int L;

L → idE

E → E[num]

E → [num]

Generate one dimensional array: a[10]

D → int L;

→ int idE

→ int id[num]

This leads to int a[10]

Generate two-dimensional array: int a [10] [3];

int a[10][3];

D → int L;

→ int id E;

→ int id E[num];

→ int id [num] [num];

This leads to int a[10][3]

So, both grammar G1 and G2 generates the given declaration.

Scheduling Algorithm: Shortest Remaining Time First

Gantt chart:

0        3       7          8           10          13         20

Process Table:

Average turnaround time = \(\frac{{20 + 7 + 1 + 5}}{4} = 8.25\)

Important Points:

TAT = CT - AT

Concept:

Mutual exclusion: Mutual exclusion prevents simultaneous access to a shared resource.

Progress: If no process is executing in critical section and other processes are waiting outside the critical section then only those processes that are not executing in their remainder section can participate in deciding which will enter in the critical section next and selection cannot be postponed.

Bounded wait: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

Explanation:

There is strict alteration here i.e. after completion of process 0 if it wants to start again, it will have to wait until process leaves the critical section.

This violates the progress requirement.

As there are only two processes involved, it means there exists a bound on the number of times other processes are allowed to enter its critical section. So, it satisfies the bounded waiting.

Also, there is a mutual exclusion in this because only one process can enter the critical section at a time.

Concepts:

V(S): Signal will increment the semaphore variable, that is, S++. 

P(S): Signal will decrement the semaphore variable., that is, S--. 

Data:

Initial counting semaphore = x

Signal operation = 12 V

Wait operation = 20 P

Since at least 1 process in blocked state

Final counting semaphore (F) = -1

Formula:

F ≥ x + 20P + 12V

Calculation:

-1 ≥ x + 20(-1) + 12(+1)

∴ x ≤ 7

Therefore, largest value of initial semaphore count is 7

Data:

Cache latency = T₁ = 1 ms

Main memory latency = T₂ = 10 ms

Average read latency = T_avg

Formula:

T_avg = H₁T₁ + (1 – H₂) (T₁ + T₂)

Since, cost of checking whether a block exists in the cache is negligible

T_avg = H₁T₁ + (1 – H₂) (T₂)

Calculation:

CASE 1: Cache size = 10 MB

Hit rate = T₁ = 20% = 0.2

Miss rate = T₂ = 80% = 0.8

 T_avg = H₁T₁ + (1 – H₂) (T₂)

= 0.2 × 1 + 0.8 × 10

= 8.2 ms > 6 ms

CASE 2: Cache size = 20 MB

Hit rate = T₁ = 40% = 0.4

Miss rate = T₂ = 60% = 0.6

T_avg = H₁T₁ + (1 – H₂) (T₂)

= 0.4 × 1 + 0.6 × 10

= 6.4 ms > 6 ms

CASE 3: Cache size = 30 MB

Hit rate = T₁ = 60% = 0.6

Miss rate = T₂ = 40% = 0.4

T_avg = H₁T₁ + (1 – H₂) (T₂)

= 0.6 × 1 + 0.4 × 10

= 4.6 ms < 6 ms

Hence, smallest cache size required to ensure an average read latency of less than 6 ms is 30 MB.

Concept:

Cascadeless schedule

It is one in which each pair of transaction T_i and T_j such that T_j reads the data that is written by T_i than the commit or abort operation of T_i should appear before the read operation of T_j

Since there are no write-in T₁ read by T₂. Hence S is cascadeless schedule, that is, S does not have a cascading abort

Inner query total (name, capacity) results in

Second query total_avg(capacity) results in:

Sum of capacity = 20 + 40 + 30 + 10 = 100

Average capacity

Final result is tuples where name of district and total capacity should be more than or equal to 25.

Number of tuples returned by this SQL query = 2

Data:

L = size of frame

BW → bandwidth = 20 × 10⁶ b/s

T_p → propagation time = 40 μs = 40 × 10^-6 s

T_t → transmission time

Formula:

For CSMA/CD,

T_t ≥ 2 × T_p

\({{\rm{T}}_{\rm{t}}} = \frac{{\rm{L}}}{{{\rm{BW}}}}\)

Calculation:

\(\frac{{\rm{L}}}{{{\rm{BW}}}} \ge 2 \times 40 \times {10^{ - 6}}\)

L ≥ 2 × 40 × 10^-6 × 20 × 10⁶

L ≥ 1600 bits

L ≥ 200 bytes

L_min = 200 bytes

Therefore, the minimum size of a frame in the network is 200 bytes.

IEEE 802.11 MAC is wi-fi

Statement

I. At least three non-overlapping channels are available for transmissions.

802.11 operates in the frequency range of 2.4 GHz to 2.485 GHz. Within this 85 MHZ band, 802.11 defines 11 partially overlapping channels. Any two channels are non-overlapping if they are separated by four or more channels. In particular the set of channels 1, 6, and 11 is the only set of three non-overlapping channels. This statement is true.

Statement

II. The RTS-CTS mechanism is used for collision detection.

RTS (request to send) and CTS (control to send) are the control frames. They are not used for collision detection. They just help in collision reduction. RTS-CTS are used to announce to all nodes, that for which node wireless channel is reserved for communication. So, given statement is false.

Statement

III. Unicast frames are ACKed.

Because there is no way to detect collision in wireless, an ACK must be sent after each unicast frame transmission. If no ACK is sent, then there is no way to know if a previously sent transmission arrived to its destination so it will be resent. So, given statement is true.

Data:

Frame size = L = 1 KB = 8 × 10³ bits

Bandwidth = BW = 128 × 10³ bits/second

Propagation delay = T_p = 150 millisecond

utilization = 100%

\({\rm{\eta }} = \frac{{100}}{{100}} = 1\)

N = sender window size = receiver window size

Formula:

For selective repeat

\({\rm{\eta }} = \frac{{\rm{N}}}{{1 + 2{\rm{a}}}}\)

\({\rm{a}} = \frac{{{{\rm{T}}_{\rm{p}}}}}{{{{\rm{T}}_{\rm{t}}}}}\)

\({{\rm{T}}_{\rm{t}}} = \frac{{\rm{L}}}{{{\rm{BW}}}}\) 

minimum number of bits = ⌈ log₂ 2N ⌉

Calculation:

\({{\rm{T}}_{\rm{t}}} = \frac{{\rm{L}}}{{{\rm{BW}}}} = \frac{{8 \times {{10}^3}}}{{128 \times {{10}^3}}} = {2^{ - 4}};\)

\({\rm{a}} = \frac{{150 \times {{10}^{ - 3}}}}{{{2^{ - 4}}}} = 2.4\)

\(1 = \frac{{\rm{N}}}{{1 + 2{\rm{a}}}}\)

N = 1 + 2(2.4) = 5.8 ≈ 6

minimum number of bits = ⌈ log₂ (2 × 6) ⌉ = 4

Hence, the minimum number of bits required for the sequence number field to achieve 100% utilization is 4.