GATE-CS-2016 (Set 2)

The man who is now Municipal Commissioner worked as

the security guard at a university

a security guard at the university

a security guard at university

the security guard at the university

Ans .

Explanation :
University considered as an organization that's why article the used before university. And Post of security is a general post, so article a has been used for security guard. So, option (B) is true.

Nobody knows how the Indian cricket team is going to cope with the difficult and seamer-friendly wickets in Australia. Choose the option which is closest in meaning to the underlined phrase in the above sentence.

put up with

put in with

put down to

put up against

Ans .

Explanation :
put up with - is a phrasal verb Meaning : to accept somebody/something that is annoying, unpleasant without complaining.

Find the odd one in the following group of words. mock, deride, praise, jeer

mock

deride

praise

jeer

Ans .

Explanation :
mock : tease deride : poke/laugh at praise : gratitude jerk : fool So except praise, all others are describing negative things.

Pick the odd one from the following options.

CADBE

JHKIL

XVYWZ

ONPMQ

Ans .

Explanation :
In the given options apart from Option D, characters at odd positions are consecutive alphabets in increasing order and similarly characters at even positions also are consecutive alphabets in increasing order. Option A: CADBE C,D,E(characters at 1st,3rd and 5th positions are consecutive alphabets in increasing order) similarly A,B(characters at 2nd and 4th positions are consecutive alphabets in increasing order). Option D: ONPMQ O,P,Q(characters at 1st,3rd and 5th positions are consecutive alphabets in increasing order) but N,M(characters at 2nd and 4th positions are not increasing order)

In a quadratic function, the value of the product of the roots (a, β) is 4. Find the value of
Que

Ans .

Explanation :
(a^n + ß^n)/ (1/a^n +1/ß^n) (a^n + ß^n)/ (ß^n + a^n )*(a^n * ß^n) (a^n * ß^n) aß^n 4^n .

Among 150 faculty members in an institute, 55 are connected with each other through Facebook and 85 are connected through WhatsApp . 30 faculty members do not have Facebook or WhatsApp accounts. The number of faculty members connected only through Facebook accounts is

Ans .

Explanation :
Suppose n(F) : number of faculty connected through facebook n(W) : number of faculty connected through whatsapp n(F ? W) : number of faculty connected through either facebook and whatsapp n(F n W) : number of faculty connected through both facebook and whatsapp n(F ? W) = (total faculty - faculty not connected to anything) = (150-30) = 120 From number theory: n(F ? W) = n(F) + n(W) - n(F n W) n(F) - n(F n W) = n(F ? W) - n(W) n(F) - N(F n W) = (120-85) = 35 n(F)- n(F n W) is the faculty that has only facebook account, Hence answer is 35.

Computers were invented for performing only high-end useful computations. However, it is no understatement that they have taken over our world today. The internet, for example, is ubiquitous. Many believe that the internet itself is an unintended consequence of the original invention. With the advent of mobile computing on our phones, a whole new dimension is now enabled. One is left wondering if all these developments are good or, more importantly, required. Which of the statement(s) below is/are logically valid and can be inferred from the above paragraph? (i) The author believes that computers are not good for us. (ii) Mobile computers and the internet are both intended inventions

(i) only

(ii) only

both (i) and (ii)

neither (i) nor (ii)

Ans .

Explanation :
Author has not said anything against internet and mobile computing but is talking about the surprising usage of these. "Many believe that the internet itself is an unintended consequence of the original invention." The author says that many believe that 'internet itself' is unplanned but actually both internet and mobile computers are unplanned(unintended) inventions.

All hill-stations have a lake. Ooty has two lakes. Which of the statement(s) below is/are logically valid and can be inferred from the above sentences?(i) Ooty is not a hill-station.(ii) No hill-station can have more than one lake.

(i) only

(ii) only.

both (i) and (ii)

neither (i) nor (ii).

Ans .

Explanation :
Given statement doesn't say that - "All hill-stations have a lake" but any place having a lake is surely a hill station. ---> Ooty may or may not be a hill station Hence (i) is false ---> Here, it is not a compulsion that a place need to have exactly one lake to be a hill station. Hence (ii) is also false

In a 2 * 4 rectangle grid shown below, each cell is a rectangle. How many rectangles can be observed in the grid?
Que

36.

Ans .

Explanation :
To form a rectangle, we must choose two horizontal sides and two vertical sides. So, number of rectangles we can form is mC2 * nC2. Since there are three horizontal lines, we can choose the horizontal sides in 3C2 ways. Since there are five vertical lines, we can choose the vertical sides in 5C2 ways. The number of rectangles we can form is = 5C2 * 3C2 = {(5*4)/2}*{(3*2)/2} = 10*3 = 30 So, option (C) is correct.

Choose the correct expression for f(x) given in the graph.
Que

Ans .

Explanation :
Simply, there are two test cases: ---> In graph, at x = 1, f(x) = 2 Let's find the values at x = 1 in given options: A) f(1) = 1 - |1-1| = 1 - 0 = 1 B) f(1) = 1 + |1-1| = 1 + 0 = 1 C) f(1) = 2 - |1-1| = 2 - 0 = 2 D) f(1) = 2 + |1-1| = 2 + 0 = 2 Hence (A) and (B) are incorrect. Now, ---> In the graph, at x=0, f(x) = 1 Let's find the values at x = 1 in the remaining options, i.e. C and D. (c) f(0) = 2 - |0-1| = 2 - 1 = 1 (d) f(0) = 2 + |0-1| = 2 + 1 = 3 Hence, C is the correct answer.

Consider the following expressions: (i) false (ii) Q (iii) true (iv) P ? Q (v) ¬Q ? P The number of expressions given above that are logically implied by P ? (P ? Q) is ______________ [This Question was originally a Fill-in-the-blanks Question]

Ans .

Explanation :

Let f (x) be a polynomial and g(x) = f (x) be its derivative. If the degree of (f(x) + f(-x)) is 10, then the degree of (g(x) - g(-x)) is _______________

Ans .C

Explanation :
f(x) can be either an even function or an odd function. If f(x) was an odd function, then f(x) + f(-x) = 0, but here it has been given that it has degree 10. So, it must be an even function. Therefore, f(x) = f(-x) => f'(x) = -f'(-x) Also, it has been mentioned that g(x) is the derivative of f(x). So, g(x) = f'(x) and g(-x) = -f'(-x) => g(x) - g(-x) = f'(x) - (-f'(-x)) => g(x) - g(-x) = f'(x) + f'(x) => g(x) - g(-x) = 2 * f'(x) But, f'(x) will have degree 9. Thus, C is the correct option.

The minimum number of colours that is sufficient to vertex-colour any planar graph is _______________

Ans D

Explanation :
A planar graph is a graph on a plane where no two edges are crossing each other. The set of regions of a map can be represented more abstractly as an undirected graph that has a vertex for each region and an edge for every pair of regions that share a boundary segment. Hence the four color theorem is applied here. Here is a property of a planar graph that a planar graph does not require more than 4 colors to color its vertices such that no two vertices have same color. This is known four color theorem.

The minimum number of colours that is sufficient to vertex-colour any planar graph is _______________ I. If m < n, then all such systems have a solution II. If m > n, then none of these systems has a solution III. If m = n, then there exists a system which has a solution

I, II and III are true

Only II and III are true

Only III is true

None of them is true

Ans C

Explanation :
For 'n' variables, we need atleast 'n' linear equations in terms of the given variable to find value of each variable. If no. of equations > no. of variables then also we can find the value of each variable. Here, m : No. of linear equations n : No. of variables For solution, m > or = n.

Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7, and given that it is of Type 2 is 0.4. The probability that an LED bulb chosen uniformly at random lasts more than 100 hours is : Note : This question was asked as Numerical Answer Type.

0.55

0.7

0.4

0.35

Ans A

Explanation :
The question is based on Bayes' Theorem. P(LED is Type 1) = 1/2 P(LED is type 2) = 1/2 Now, we need to see conditional probabilities. P( LED lasting more than 100 hours / LED is Type 1) = 0.7 P( LED lasting more than 100 hours / LED is Type 2) = 0.4 P(LED lasts more than 100 hours) = P( LED is Type1)* P(LED lasting more than 100 hours / LED is Type 1) + P(LED is Type 2) * P( lasting more than 100 hours / Type 2) = 0.5 * 0.7 + 0.5 * 0.4 = 0.35 + 0.20 = 0.55 Thus, A is the correct choice.

Suppose that the eigenvalues of matrix A are 1, 2, 4. The determinant of (A-1)T is

1/8

1/4

0.2

Ans A

Explanation :
1/8 Determinant of A = 1*4*2 = 8 which is product of Eigen values. Determinant of A-1 = 1/8 as determinant of inverse of matrix is inverse of determinant. Determinant of Transpose (A-1) = 1/8 since determinant of transpose of matrix remains same as original one.

Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2’s complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is _____________

-1

Ans A

Explanation :
Here "longest latency for the sum to stabilize" means maximum delay that ripple carry adder would take to add A and B, we are given value of A and need to find the value of B. The Delay in Ripple Carry Adder is as follows - For sum there are 2 XOR gates. - For carry there is 1 XOR,1 AND and 1 OR gate. i.e total 3 gate delays in case of carry and 2 gate delays in sum. If we do 2's complement of 1 in 8 bit we get "00000001". same we do for each option -1 : "11111111" 2 : "00000010" 1 : "00000001" -2 : "11111110" So in case of -1 the carry bit will change and thus it will take 1 extra gate delay, hence we could see that the maximum delay we could get when input at B will be -1, i.e. add "00000001" with "11111111" and would get Maximum delay.

Let, x1?x2?x3?x4 = 0 where x1, x2, x3, x4 are Boolean variables, and ? is the XOR operator. Which one of the following must always be TRUE?

x1x2x3x4 = 0

x1x3+x2 = 0

x'1?x'3=x'2?x'4

x1+x2+x3+x4 = 0

Ans C

Explanation :
First we rearrange the terms, x1?x2?x3?x4 = 0 x1?x3?x2?x4 = 0 x1?x3 = x2?x4 Then use a?b=a'?b'a?b=a'?b' to get (C). x'1?x'3=x'2?x'4 Another approach : You can take a counter example to disprove other options. You can take x1 = x2 = x3 = x4 = 1. Only option (C) is correct.

Let X be the number of distinct 16-bit integers in 2’s complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation. Then X -Y is

Ans A

Explanation :
Answer: For n bits, Distinct values represented in 2's complement is -2^n-1 to 2^n-1 -1 Distinct values represented in Signed Magnitude is -(2^(n-1) -1) to 2^(n-1) -1 For example if n = 8, we can represent numbers from -128 to 127 in 2's complement representation and numbers from -127 to 127 in signed magnitude representation. Difference is 1. The difference of 1 is there because there are two different representations of +0 and -0 in signed magnitude representation. But in 2's complement representation, there is one representation of 0.

Let X be the number of distinct 16-bit integers in 2’s complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation. Then X -Y is

Ans A

Explanation :
Answer: 6 bits are needed for 40 distinct instructions ( because, 32 < 40 < 64 ) 5 bits are needed for 24 general purpose registers( because, 16< 24 < 32) 32-bit instruction word has an opcode(6 bit), two register operands(total 10 bits) and an immediate operand (x bits). The number of bits available for the immediate operand field => x = 32 - ( 6 + 10 ) = 16 bits

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is ________ [This Question was originally a Fill-in-the-blanks Question]

Ans A

Explanation :
Answer: 6 It would be node number 31 for given distance 4. For example if we consider at distance 2, below highlighted node G can be the farthest node at position 7. A / \ B C / \ / \ D E F G Alternative Solution : t is the n-th vertex in this BFS traversal at distance four from the root. So height of tree is 4. Max number of nodes = 2^{h+1} - 1 = 2^{5} - 1 = 31 At distance four, last node is 31. option (C)

Ans A

Explanation :
Answer: 6 It would be node number 31 for given distance 4. For example if we consider at distance 2, below highlighted node G can be the farthest node at position 7. A / \ B C / \ / \ D E F G Alternative Solution : t is the n-th vertex in this BFS traversal at distance four from the root. So height of tree is 4. Max number of nodes = 2^{h+1} - 1 = 2^{5} - 1 = 31 At distance four, last node is 31. option (C)

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); }

Ans C

#include"stdio.h" void f(int* p, int m) { m = m + 5; *p = *p + m; return; } int main() { int i=5, j=10; f(&i, j); printf("%d", i+j); } For i, address is passed. For j, value is passed. So in function f, p will contain address of i and m will contain value 10. Ist statement of f() will change m to 15. Then 15 will be added to value at address p. It will make i = 5+15 = 20. j will remain 10. print statement will print 20+10 = 30. So answer is C.

Q.
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ? I. Quicksort runs in T(n2) time II. Bubblesort runs in T(n2) time III. Mergesort runs in T(n) time IV. Insertion sort runs in T(n) time

I and II only

I and III only

II and IV only

I and IV only

Ans C
C

Given an array in ascending order, Recurrence relation for total number of comparisons for quicksort will be T(n) = T(n-1)+O(n) //partition algo will take O(n) comparisons in any case. = O(n^2) II. Bubble Sort runs in T(n^2) time If an array is in ascending order, we could make a small modification in Bubble Sort Inner for loop which is responsible for bubbling the kth largest element to the end in kth iteration. Whenever there is no swap after the completion of inner for loop of bubble sort in any iteration, we can declare that array is sorted in case of Bubble Sort taking O(n) time in Best Case. III. Merge Sort runs in T(n) time Merge Sort relies on Divide and Conquer paradigm to sort an array and there is no such worst or best case input for merge sort. For any sequence, Time complexity will be given by following recurrence relation, T(n) = 2T(n/2) + T(n) // In-Place Merge algorithm will take T(n) due to copying an entire array. = T(nlogn) IV. Insertion sort runs in T(n) time Whenever a new element which will be greater than all the elements of the intermediate sorted sub-array ( because given array is sorted) is added, there won't be any swap but a single comparison. In n-1 passes we will be having 0 swaps and n-1 comparisons. Total time complexity = O(n)

Q.
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on:

Greedy paradigm.

Divide-and-Conquer paradigm

Dynamic Programming paradigm

neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Ans C
C

Floyd Warshall Algorithm is a Dynamic Programming based algorithm. It finds all pairs shortest paths using following recursive nature of problem. For every pair (i, j) of source and destination vertices respectively, 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][k] + dist[k][j]. The following figure is taken from the Cormen book. It shows the above optimal substructure property in the all-pairs shortest path problem.Since there are overlapping subproblems in recursion, it uses dynamic programming.

Q.
N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: T(N) delete, O(log N) insert, O(log N) find, and T(N) decrease-key What is the time complexity of all these operations put together

O(Log²N)

O(N)

O(N²)

T(N²Log N)

Ans C
C

The time complexity of decrease-key operation is T(1) since we have the pointer to the record where we have to perform the operation. However, we must keep the doubly linked list sorted and after the decrease-key operation we need to find the new location of the key. This step will take T(N) time and since there are T(N) decrease-key operations, the time complexity becomes O(N²). Note that the other three operations have a lower bound than this one.

Q.
The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________ [Note that this question was originally asked as Fill-in-the-Blanks type]

2

3

4

5

Ans A
A

The minimum no of state is 2.

Q.
Language L1 is defined by the grammar: S1 -> aS1b | e Language L2 is defined by the grammar: S2 -> abS2 | e 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

Ans C
C

L1 has the property that no of a's should be equal to no of b's in a string, and all a's should precede all b's . Hence extra memory will be required to check this property of a string ( Finite Automaton can't be built for this type of language). Hence this is not regular language. Therefore P is False. L2 has the property that no of a's should be equal to no of b's, but order of a's and b's is different here, it is (ab)*, which will require no extra memory to be accepted.( Finite Automaton can be built for this language). Hence L2 is regular language. Therefore Q is True.

Q.
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

Ans D
D

St 1: As L3 is Recursive and recursive languages are closed under complementation, L3’ will also be recursive. L3’ U L4 is also recursive as recursive languages are closed under union. St 2: As L2 is Context- Free, it will be recursive as well. L2 U L3 is recursive because as recursive languages are closed under union. St 3: L1* is regular because regular languages are closed under kleene –closure. L1* U L2 is context free as union of regular and context free is context free. St 4: L2’ may or may not be context free because CFL are not closed under complementation. So it is not true. So I, II and III are correct.

Q.
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

A

B

C

D

Ans B
B

Lexical analysis uses Regular expression to recognize identifiers. Top down parsing uses Left Most Derivation to generate the string the of the language. Type checking is done at Semantic analysis phase of the compiler. Activation records of a function are loaded into stack memory at Run time.

Q.
In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

LRU (Least Recently Used)

OPT (Optimal Page Replacement)

MRU (Most Recently Used)

FIFO (First In First Out)

Ans D
D

In some situations FIFO page replacement gives more page faults when increasing the number of page frames. This situation is Belady’s anomaly. Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm. For example, if we consider reference string 3 2 1 0 3 2 4 3 2 1 0 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults.

Q.
B+ Trees are considered BALANCED because

the lengths of the paths from the root to all leaf nodes are all equal.

the lengths of the paths from the root to all leaf nodes differ from each other by at most 1

the number of children of any two non-leaf sibling nodes differ by at most 1

the number of records in any two leaf nodes differ by at most 1

Ans A
A

In both B Tree and B+ trees, depth (length of root to leaf paths) of all leaf nodes is same. This is made sure by the insertion and deletion operations. In these trees, we do insertions in a way that if we have increase height of tree after insertion, we increase height from root. This is different from BST where height increases from leaf nodes. Similarly, if we have to decrease height after deletion, we move the root one level down. This is also different from BST which shrinks from bottom. The above ways of insertion and deletion make sure that depth of every leaf node is same.

Q.
Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires

Anarkali’s public key.

Salim’s public key.

Salim’s private key

Anarkali’s private key.

Ans A
A

Sender uses its private key to digitally sign a document. Receiver uses public key of sender to verify. So option A is correct.

Q.
In an Ethernet local area network, which one of the following statements is TRUE ?

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

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

A station continues to transmit the packet even after the collision is detected.

The exponential backoff mechanism reduces the probability of collision on retransmissions.

Ans A
A

An Ethernet is the most popularly and widely used LAN network for data transmission. It is a protocol of data link layer and it tells how the data can be formatted to transmit and how to place the data on network for transmission. Now considering the Ethernet protocol we will discuss all the options one by one (A) This option is false as in Ethernet the station is not required to stop to sense for the channel prior frame transmission. (B) A signal is jammed to inform all the other devices or stations about collision that has occurred so that further data transmission is stopped. Thus this option is also false (C) Once the collision has occurred the data transmission is stopped as the jam signal is sent. Thus this option is also incorrect. (D) To reduce the probability of collision on retransmissions an exponential back off mechanism is used.

Q.
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

Ans C
C

Whenever the client request for a webpage, the query is made in the form say www.geeksforgeeks.org. As soon as the query is made the server makes the DNS query to identify the Domain Name Space. DNS query is the process to identify the IP address of the DNS such as www.org. The client’s computer will make a DNS query to one of its internet service provider’s DNS server. Step 2 : As soon as DNS server is located a TCP connection is to be established for the further communication. The TCP protocol requests the server to establishing a connection by sending a TCP SYN message. Which is further responded by the server using SYN_ ACK from server to client and then ACK back to server from client (3- way hand shaking protocol). Step 3 : Once the connection has been established the HTTP protocol comes into picture. It requests for the webpage using its GET method and thus, sending an HTTP GET request. Hence, the correct sequence for the transmission of packets is DNS query, TCP SYN, HTTP GET request.

Q.
A binary relation R on N x N is defined as follows: (a, b) R (c, d) if a <= c or b <= d. Consider the following propositions: P: R is reflexive Q: R is transitive Which one of the following statements 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

Ans B
B

THEORY: REFLEXTIVE RELATION: A relation ‘R’ on a set ‘A’ is said to be reflexive if, (xRx) for every x£A. Ex. If A= {1,2} And R, and P be a relation on AxA, defined as, R= {(2,2),(1,1)} => R is reflexive as it contains all pair of type (xRx). P= {(1,1)} => P is not reflexive relation on A, as it doesn’t contain (2,2). TRANSITIVE RELATION: A relation ‘R’ on set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz) for every x,y,z £A. Ex: if A= {1,2} Let R be a relation on AxA, defined as, R= {(1,1),(1,2),(2,1)} => R is transitive. SOLUTION: Given, (a, b) R (c, d) if a <= c or b <= d i.Check for reflexivity: if an element of set be (a,b) then, (a,b)R(a,b) should hold true. Here, a<=a or b<=b. So, (a,b)R(a,b) holds true. Hence, ‘R’ is reflexive. ii. Check for transitivity: if elements of set be (2,3),(3,1) and(1,1) Then, (2,3)R(3,1) as 2<=3 And (3,1)R(1,1) as 1<=1 But (2,3)R(1,1) doesn’t hold true as 2>=1 and 3>=1. Hence, R is reflexive but not transitive.

Q. Which one of the following well-formed formulae in predicate calculus is NOT valid?

A

B

C

D

Ans D
D

Suppose if there are two statements P and Q, P=>Q = ~PvQ i.e. The only situation where implication fails is (=>) when P is true and Q is false. i.e. A truth statement can't imply a false statement. So, for these type of questions it will be better to take option and check for some arbitrary condition By looking options, we are pretty sure that A,B are correct Suppose X is any number and statement is P(x) = X is a prime number Q(x) = X is a non-prime number If we look at option D, 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 obviously false i.e. here, truth statement implies a false statement which is not valid. If we carefully look at option C, There exists a number x, which is both prime and non-prime which is false and a false statement can imply either true or false. So option (C) is correct So Answer is Option (D)

Q. Which one of the following well-formed formulae in predicate calculus is NOT valid?

A

B

C

D

Ans D
D

Suppose if there are two statements P and Q, P=>Q = ~PvQ i.e. The only situation where implication fails is (=>) when P is true and Q is false. i.e. A truth statement can't imply a false statement. So, for these type of questions it will be better to take option and check for some arbitrary condition By looking options, we are pretty sure that A,B are correct Suppose X is any number and statement is P(x) = X is a prime number Q(x) = X is a non-prime number If we look at option D, 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 obviously false i.e. here, truth statement implies a false statement which is not valid. If we carefully look at option C, There exists a number x, which is both prime and non-prime which is false and a false statement can imply either true or false. So option (C) is correct So Answer is Option (D)

Q. Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements: I. Each compound in U \ S reacts with an odd number of compounds. II. At least one compound in U \ S reacts with an odd number of compounds. III. Each compound in U \ S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE?

Only I

Only II

Only III

None

Ans B
B

Answer is B. This a graph theory question. "\" is the set difference operation. Same as U - S. Since U is universal set, U\S would give complement of S = S' Let S contains Compounds numbered {1,2,3...8, 9} so U\S contains Compounds {10, 11, 12.... 22, 23} Consider these compounds to be vertices of a graph. An edge b/w two vertices indicate that the compounds react with each other. This graph has NO multiple edge cause that doesn't make sense. There are no directed edges cause if one compound reacts with other it also means other reacts with it too. Single edge represent reaction b/w both. It has NO Loops cause compound don't react with itself. Hence graph is simple undirected graph. We know that "An undirected graph has even number of vertices of odd degree" 9 vertices of this graph have degree 3 (odd degree) cause 9 compounds react with 3 other compounds. Hence there must be at LEAST 1 more vertex which must have an odd degree. This extra compound must belong to U\S cause 9 compounds in S have already been accounted for. This implies statement II in the question is TRUE. Other 2 statements are False. Statement III - Consider that all 9 compounds in S react with the same 3 compounds in U\S say with {20, 21, 22} hence all compounds in U\S either react with Zero or 9 compounds but not Even number. Similarly Statement I can be proved wrong by visualizing the graph.

Q. The value of the expression 1399(mod 17), in the range 0 to 16, is : Note : This question was asked as Numerical Answer Type.

4

3

8

16

Ans A
A

Answer is A. Answer: We have 13 * 13 * 13 * ... * 13 (total 99 terms) By remainder theorem, => (-4) * (-4) * ... * (-4) (total 99 terms) => 16 * 16 * ... * 16 * (-4) (total 50 terms, 49 terms for 16 and one term for -4) Reapplying remainder theorem, => (-1) * (-1) * ... * (-1) * (-4) (total 50 terms, 49 terms for -1 and one term for -4) => (-1) * (-4) => 4 Thus, A is the correct option.

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

28

20

18

30

Ans A
A

Background:Explanation: Pipelining is an implementation technique where multiple instructions are overlapped in execution. The stages are connected one to the next to form a pipe - instructions enter at one end, progress through the stages, and exit at the other end. Pipelining does not decrease the time for individual instruction execution. Instead, it increases instruction throughput. The throughput of the instruction pipeline is determined by how often an instruction exits the pipeline. The same concept is used in pipelining. Bottleneck here is UF as it takes 5 ns while UG takes 3ns only. We have to do 10 such calculations and we have 2 instances of UF and UG respectively. Since there are two functional units, each unit get 5 numbers of units to compute on. Suppose computation starts at time 0. which means G starts at 0 and F starts at 3rd second since G finishes computing first element at third second. So, UF can be done in 5*10/2=25 nano seconds. For the start UF needs to wait for UG output for 3 ns and rest all are pipelined and hence no more wait. So, answer is 3+25=28

Q. Consider a processor with 64 registers and an instruction set of size twelve. Each instruction has five distinct fields, namely, opcode, two source register identifiers, one destination register identifier, and a twelve-bit immediate value. Each instruction must be stored in memory in a byte-aligned fashion. If a program has 100 instructions, the amount of memory (in bytes) consumed by the program text is

100

200

400

500

Ans D
D

Answer: One instruction is divided into five parts, 1) The opcode- As we have instruction set of size 12, an instruction opcode can be identified by 4 bits, as 2^4=16 and we cannot go any less. 2) & (3) Two source register identifiers- As there are total 64 registers, they can be identified by 6 bits. As they are two i.e. 6 bit + 6 bit. 4) One destination register identifier- Again it will be 6 bits. 5) A twelve bit immediate value- 12 bit. Adding them all we get, 4 + 6 + 6 + 6 + 12 = 34 bit = 34/8 byte = 4.25 byte. As there are 100 instructions, We have a size of 425 byte, which can be stored in 500 byte memory from the given options. Hence (D) 500 is the answer.

Q. The width of the physical address on a machine is 40 bits. The width of the tag field in a 512 KB 8-way set associative cache is ____________ bits

24

20

30

40

Ans A
A

Answer: We know cache size = no.of.sets* lines-per-set* block-size Let us assume no of sets = 2^x And block size= 2^y So applying it in formula. 2^19 = 2^x + 8 + 2^y; So x+y = 16 Now we know that to address block size and set number we need 16 bits so remaining bits must be for tag i.e., 40 - 16 = 24 The answer is 24 bits

Q. The width of the physical address on a machine is 40 bits. The width of the tag field in a 512 KB 8-way set associative cache is ____________ bits

24

20

30

40

Ans A
A

Answer: We know cache size = no.of.sets* lines-per-set* block-size Let us assume no of sets = 2^x And block size= 2^y So applying it in formula. 2^19 = 2^x + 8 + 2^y; So x+y = 16 Now we know that to address block size and set number we need 16 bits so remaining bits must be for tag i.e., 40 - 16 = 24 The answer is 24 bits

Q. Consider a 3 GHz (gigahertz) processor with a three-stage pipeline and stage latencies v1, v2, and v3 such that v1 = 3v2/4 = 2v3. 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

2

4

8

16

Ans B
B

Answer: Consider this pipeline (V1) --> (V2) --> (V3) Can be written as (V) --> (4V/3) --> (V/2) Where given V = V1 = 3V2/4 = 2V3 Largest stage is stage 2 with 4V/3 seconds time required. Speed of processor is limited by this stage only. In fact this is the speed of the processor. Frequency given is 3Ghz, which means processor can execute 3 Giga clock cycle.... in 1 second Or 1 clock cycle .....in (1/3G) secs (G for giga) But we know that stage latency of the largest stage in pipeline limits the time of 1 clock cycle. Hence 4V/3 = 1 clock cycle = 1/3G secs V = 1/4G...........(1) Now largest stage that is stage 2 is split into equal size, so new pipeline is (V)-->(2V/3)-->(2V/3)-->(V/2) Now largest stage is V seconds Hence, In V seconds do 1 clock cycle In 1 second do 1/V clock cycles But V = 1/4G So in 1 second do 4 Ghz. {ANS}

Q. A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _____________ [This question was originally asked as Fill-in-the-Blanks question]

6

7

8

9

Ans C
C

Answer: here node with integer 1 has to be at root only. Now for maximum depth of the tree the following arrangement can be taken. Take root as level 1. make node 2 at level 2 as a child node of node 1. make node 3 at level 3 as the child node of node 2. .. .. and so on for nodes 4,5,6,7 .. make node 8 at level 8 as the child node of node 7. make node 9 at level 9 as the child node of node 8. Putting other nodes properly, this arrangement of the the complete binary tree will follow the property of min heap. So total levels are 9. node 9 is at level 9 and depth of node 9 is 8 from the root.

Q. 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

A

B

C

D

Ans C
C

We can solve this question taking any two values for X and Y. Suppose X= 2 and Y= 5, now this code will calculate Looking at each iteration separately Before iteration 1 – X=2 Y= 5 a=2 , b=5, res=1 Iteration 1 – since b%2 !=0 we go to else part Therefore after iteration 1, X=2, Y=5, a=2, b=4, res=2 Iteration 2 – since b%2=0 we go to if part Therefore after iteration 2 , X=2, Y=5, a=4, b=2, res=2 Iteration 3 – since b%2=0 we go to if part Therefore after iteration 3 , X=2, Y=5, a=16, b=1, res=2 Iteration 4 – since b%2!=0 we go to else part Therefore after iteration 4 , X=2, Y=5, a=16, b=0, res=32 Now putting the values of X, Y , a, b, res in the equations given in options after each iteration we can see only equation c is correct. This solution is contributed by Parul sharma. Another solution In option C Before Iteration 1: X^Y=64 res * (a^b)=64 Before Iteration 2: X^Y=64 res * (a^b)=64 Before Iteration 3: X^Y=64 res * (a^b)=64

Q. Consider the following New-order strategy for traversing a binary tree: Visit the root; Visit the right subtree using New-order Visit the left subtree using New-order The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

+ - 1 6 7 * 2 ˆ 5 - 3 4 *

- + 1 * 6 7 ˆ 2 - 5 * 3 4

- + 1 * 7 6 ˆ 2 - 5 * 4 3

1 7 6 * + 2 5 4 3 * - ˆ -

Ans C
C

Reverse Polish expression is derived through Post-Order i.e. 1) Visit Left Node 2) Visit Right Node (L R N) 3) Visit Root Node --- Acc. to Ques. New Order algorithm is : 1) Visit Root Node 2) Visit Right Node (N R L) 3) Visit Left Node ie. New Order Expression will be a total reverse of the Post-Order algorithm Post-Order Expression : 3 4 * 5 – 2 ˆ 6 7 * 1 + – Hence , New Order Expression : – + 1 * 7 6 ^ 2 – 5 * 4 3

Q. 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

2

3

4

5

Ans B
B

Q. Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is

1500

2000

500

100

Ans A
A

We have many ways to do matrix chain multiplication because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result of the matrix chain multiplication obtained will remain the same. Here we have four matrices A1, A2, A3, and A4, we would have: ((A1A2)A3)A4 = ((A1(A2A3))A4) = (A1A2)(A3A4) = A1((A2A3)A4) = A1(A2(A3A4)). However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. Here, A1 is a 10 × 5 matrix, A2 is a 5 x 20 matrix, and A3 is a 20 x 10 matrix, and A4 is 10 x 5. If we multiply two matrices A and B of order l x m and m x n respectively,then the number of scalar multiplications in the multiplication of A and B will be lxmxn. Then, The number of scalar multiplications required in the following sequence of matrices will be : A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500. All other parenthesized options will require number of multiplications more than 1500.

Q. 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(n^a), then the least possible value (accurate up to two decimal positions) of a is

2.2 to 2.4

3.2 to 3.4

0 to 1.8

1

Ans A
A

The time complexity of a recurrence relation is the worst case time complexity. First we have to find out the number of function calls in worst case from the flow chart. The worst case will be when all the conditions (diamond boxes) turn out towards non-returning paths taking the longest root. In the longest path we have 5 function calls.
So the recurrence relation will be – A(n) = 5A(n/2) + O(1) (O(1) because rest of the statements have O(1) complexity.) Solving this recurrence relation using Master theorem – a = 5 , b= 2 , f(n) =O(1) , nlogb a= nlog2 5 (case 1 master theorem) A(n) =nlogb a value of log 25 is 2.3219, so, the best option is option a

Q. The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____________ Note: The height of a tree with a single node is 0. [This question was originally a Fill-in-the-Blanks question]

2

4

64

32

Ans C
C

Answer: To get height 6, we need to put either 1 or 7 at root. So count can be written as T(n) = 2*T(n-1) with T(1) = 1 7 / [1..6] 1 \ [2..7] Therefore count is 26 = 64 Another Explanation: Consider these cases, 1 2 3 4 5 6 7 1 2 3 4 5 7 6 1 7 6 5 4 3 2 1 7 6 5 4 2 3 7 6 5 4 3 2 1 7 6 5 4 3 1 2 7 1 2 3 4 5 6 7 1 2 3 4 6 5 For height 6, we have 2 choices. Either we select the root as 1 or 7. Suppose we select 7. Now, we have 6 nodes and remaining height = 5. So, now we have 2 ways to select root for this sub-tree also. Now, we keep on repeating the same procedure till remaining height = 1 For this last case also, we have 2 ways. Therefore, total number of ways = 26= 64

Q. In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V | = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

T(n²)

T(m+n)

T(^m2)

T(n⁴)

Ans B
B

First you need to find twins of each node. You can do this using level order traversal (i.e., BFS) once. Time complexity of BFS is T(m +n). And you have to use linked list for representation which is extra space (but memory size is not a constraint here). Final, time complexity is T(m + n) to set twin pointer. Option (B) is correct.

Q. Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is S* . II. There exists a regular language A such that for all languages B, A n B is regular. Which one of the following is CORRECT?

Only I is true

Only II is true

Both I and II are true

Both I and II are false

Ans B
B

Answer: False, Since there is no mention of transition between states. There may be a case, where between two states there is no transition defined. Statement II: True, Since any empty language (i.e., A = F ) is regular and its intersection with any other language is F. Thus A n B is regular.

Q. Consider the following languages: L1 = {aⁿb^mcⁿ : m, n >= 1} L2 = {aⁿbⁿc²ⁿ : n >= 1} Which one of the following is TRUE?

Both L1 and L2 are context-free

L1 is context-free while L2 is not context-free

L2 is context-free while L1 is not context-free.

Neither L1 nor L2 is context-free.

Ans B
B

L1 = {aⁿb^mcⁿ |m, n = 1} is context free language because it is derived by the following CFG: S- > aSc|aBc; B- > bB|b • L2 = {aⁿbⁿc²ⁿ |n = 1} is not a context free language, this can be proved using pumping lemma. Intuitively, a pushdown automaton can’t remember number of as for the third set of characters coming, i.e. c. This language is very similar to {aⁿb^mcⁿ |n = 1} which is known to be a non-CFL. Hence, correct answer would be (B) L1 is context-free while L2 is not context-free. L2 is not context free. no. of b's will match with no. of a's leaving c's to be matched with no one..so L2 cant be context free.

Q. Consider the following languages. L1 = { | M takes at least 2016 steps on some input}, L2 = { | M takes at least 2016 steps on all inputs} and L3 = { | M accepts e}, where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?

L1 is recursive and L2, L3 are not recursive

L2 is recursive and L1, L3 are not recursive

L1, L2 are recursive and L3 is not recursiv

L1, L2, L3 are recursive

Ans C
C

L1 and L2 both are recursive. L1 = { | M takes at least 2016 steps on some input} In L1 we can stop giving input once we find any string which is accepted in less than 2016 steps. In L2 we have to check all possible inputs whose length is less than 2016 and all possible string whose length is less than 2016 is a finite set. For both L1 and L2 machine is definetly going to halt. Both L1 and L2 are recursive. L3 is undecideble, M accepts e. So L3 is not recursive. Option (C) is CORRECT.

Q. Which one of the following grammars is free from left recursion?

A

B

C

D

Ans B
B

Answer: Grammar A has direct left recursion because of the production rule: A->Aa. Grammar C has indirect left recursion because of the production rules:S-> Aa and A->Sc Grammar D has indirect left recursion because of production rules : A-> Bd and B-> Ae Grammar B doesn't have any left recursion (neither direct nor indirect).

Q. 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, int a[10][3]; The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num. Grammar G1 D ? int L; L ? id [E E ? num] E ? num] [E Grammar G2 D ? int L; L ? id E E ? E[num] E ? [num] Which of the grammars correctly generate the declaration mentioned above?

A

B

C

D

Ans A
A

Answer: Context-Free Grammars A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings. A CFG consists of the following components: 1) A set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar. 2) A set of nonterminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols. 3) A set of productions, which are rules for replacing (or rewriting) nonterminal symbols (on the left side of the production) in a string with other nonterminal or terminal symbols (on the right side of the production). 4) A start symbol, which is a special nonterminal symbol that appears in the initial string generated by the grammar. To generate a string of terminal symbols from a CFG, we: 1) Begin with a string consisting of the start symbol; 2) Apply one of the productions with the start symbol on the left hand size, replacing the start symbol with the right hand side of the production; 3) Repeat the process of selecting nonterminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all nonterminals have been replaced by terminal symbols. Given a grammar G with start symbol S, if there is some sequence of productions that, when applied to the initial string S, result in the string s, then s is in L(G), the language of the grammar. Source : https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/cfg.html We need to check which of the two grammars correctly generate "int a[10][3];". This means we need to check if int id[num][num]; Grammar G1 D ? int L; L ? id [E E ? num] E ? num] [E Grammar G2 D ? int L; L ? id E E ? E[num] E ? [num]

Q.

Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time first.The average turn around time of these processes is ___________ milliseconds. Note : This question was asked as Numerical Answer Type.

8.25

10.25

6.35

4.25

Ans A
A

Answer:
PreEmptive Shortest Remaining time first scheduling, i.e. that processes will be scheduled on the CPU which will be having least remaining burst time( required time at the CPU). The processes are scheduled and executed as given in the below Gantt chart. Turn Around Time(TAT) = Completion Time(CT) - Arrival Time(AT) TAT for P1 = 20 - 0 = 20 TAT for P2 = 10 - 3 = 7 TAT for P3 = 8- 7 = 1 TAT for P4 = 13 - 8 = 5 Hence, Average TAT = Total TAT of all the processes / no of processes = ( 20 + 7 + 1 + 5 ) / 4 = 33 / 4 = 8.25 Thus, A is the correct choice.

Q. Consider the following two-process synchronization solution.The shared variable turn is initialized to zero. Which one of the following is TRUE?

This is a correct two-process synchronization solution.

This solution violates mutual exclusion requirement.

This solution violates progress requirement

This solution violates bounded wait requirement

Ans C
C

Answer: It satisfies the mutual excluision : Process P0 and P1 could not have successfully executed their while statements at the same time as value of ‘turn’ can either be 0 or 1 but can’t be both at the same time. Lets say, when process P0 executing its while statements with the condition “turn == 1”, So this condition will persist as long as process P1 is executing its critical section. And when P1 comes out from its critical section it changes the value of ‘turn’ to 0 in exit section and because of that time P0 comes out from the its while loop and enters into its critical section. Therefore only one process is able to execute its critical section at a time. Its also satisfies bounded waiting : It is limit on number of times that other process is allowed to enter its critical section after a process has made a request to enter its critical section and before that request is granted. Lets say, P0 wishes to enter into its critical section, it will definitely get a chance to enter into its critical section after at most one entry made by p1 as after executing its critical section it will set ‘turn’ to 0 (zero). And vice-versa (strict alteration). Progess is not satisfied : Because of strict alternation no process can stop other process from entering into its critical section.

Q. Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is ________.

7

8

9

10

Ans A
A

Answer:20-7 -> 13 will be in blocked state, when we perform 12 V(S) operation makes 12 more process to get chance for execution from blocked state. So one process will be left in the queue (blocked state) here i have considered that if a process is in under CS then it not get blocked by other process.

Q. A file system uses an in-memory cache to cache disk blocks. The miss rate of the cache is shown in the figure. The latency to read a block from the cache is 1 ms and to read a block from the disk is 10 ms. Assume that the cost of checking whether a block exists in the cache is negligible. Available cache sizes are in multiples of 10 MB.The smallest cache size required to ensure an average read latency of less than 6 ms is _______ MB.

10

20

30

40

Ans C
C

Answer: When CPU needs to search for data, and finds it in cache, it's called a HIT, else wise MISS. If data is not found in the ache, then CPU searches it in main memory. Consider x to be MISS ratio, then (1-x) would be HIT ratio. Whenever there is hit, latency is 1ms and 10ms upon miss. Time to read from main memory(disk) for all misses = x * 10 ms Time to read for all hits from cache = (1-x)*1 ms Average time: 10x + 1 -x = 9x + 1 As asked in the question, average read latency should be less than 6 ms. 9x +1 < 6 9x < 5 x < 0.5556 For 20 MB, miss rate is 60% and for 30 MB, it is 40%. Thus, the smallest cache size required to ensure an average read latency of less than 6 ms is 30 MB.

Q. Consider the following database schedule with two transactions, T1 and T2. S = r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X); a1; a2; where ri(Z) denotes a read operation by transaction Ti on a variable Z, wi(Z) denotes a write operation by Ti on a variable Z and ai denotes an abort by transaction Ti . Which one of the following statements about the above schedule is TRUE?

S is non-recoverable

S is recoverable, but has a cascading abort

S does not have a cascading abort

S is strict

Ans C
C

Answer: T2 overwrites a value that T1 writes T1 aborts: its “remembered” values are restored. Cascading Abort could have arised if - > Abort of T1 required abort of T2 but as T2 is already aborted , its not a cascade abort. Therefore, Option C Option A - is not true because the given schedule is recoverable Option B - is not true as it is recoverable and avoid cascading aborts; Option D - is not true because T2 is also doing abort operation after T1 does, so NOT strict.

Q. Consider the following database table named water_schemes The number of tuples returned by the following SQL query is with total(name, capacity) as select district_name, sum(capacity) from water_schemes group by district_name with total_avg(capacity) as select avg(capacity) from total select name from total, total_avg where total.capacity >= total_avg.capacity

1

2

3

4

Ans B
B

Answer: First group by district name is performed and total capacities obtained as following Ajmer 20 Bikaner 40 Charu 30 Dungargarh 10 Then average capacity is computed, Average Capacity = (20 + 40 + 30 + 10)/4 = 100/4 = 25. Finally districts with more than average are selected. Bikaner is 40 which is greater than average (25) Charu is 30 which is also greater than average (25). Therefore answer is 2 tuples.

Q. A network has a data transmission bandwidth of 20 × 10 6 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 _________ bytes. Note : This question was asked as Numerical Answer Type.

200

250

400

1200

Ans A
A

Answer: For frame size to be minimum, its transmission time should be equal to twice of one way propagation delay. i.e, Tx = 2Tp suppose minimum frame size is L bits. Tx = L / B where B is the bandwidth = 20 * 10^6 bits/sec and given Tp = 40 micro seconds as Tx = 2 Tp L / B = 80 micro seconds L = B * 80 micro seconds = 20 * 10^6 bits/sec * 80 micro seconds = 1600 bits Now as the answer has to be given in Bytes, hence, 1600 / 8 bytes = 200 bytes. Thus, A is the correct answer.

Q. 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

Ans A
A

Answer: For frame size to be minimum, its transmission time should be equal to twice of one way propagation delay. i.e, Tx = 2Tp suppose minimum frame size is L bits. Tx = L / B where B is the bandwidth = 20 * 10^6 bits/sec and given Tp = 40 micro seconds as Tx = 2 Tp L / B = 80 micro seconds L = B * 80 micro seconds = 20 * 10^6 bits/sec * 80 micro seconds = 1600 bits Now as the answer has to be given in Bytes, hence, 1600 / 8 bytes = 200 bytes. Thus, A is the correct answer.

Q. A network has a data transmission bandwidth of 20 × 10 6 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 _________ bytes. Note : This question was asked as Numerical Answer Type.

All I, II, and III

I and III only

II and III only

II only

Ans A
A

Answer: 802.11 uses 5 GHz Radio Band(High Frequency) which has 23 overlapping channels rather than the 2.4 GHz frequency band which has only three non-overlapping channels. RTS(Request To Send) and CTS(Clear To Send) are control frames, which facilitate the exchange between stations and help in collision reduction and not DETECTION. As Station 1 would send data frame to Station 2, only when it receives a CTS frame. First Station 1 sends a RTS to Station 2, in response Station 2 sends back CTS. After data is received by Station 2, it send Acknowledgement frame(ACKed). As Station 2 sends a Acknowledgement to a single recipient on a network, Unicast Frames are acknowledged

Q. Consider a 128×10 3 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 acknowledgement. The minimum number of bits required for the sequence number field to achieve 100% utilization is ___________

2

4

6

8

Ans A
A

Answer: To achieve 100% efficiency, the number of frames that we should send = 1 + 2 * Tp / Tt where, Tp is propagation delay, and Tt is transmission delay. So, Number of frames sent = 1 + 4.687 = 5.687 (approx 6) As the protocol used is Selective repeat, Receiver window size should be equal to Sender window size. Then, Number of distinct sequence numbers required = 6 + 6 = 12 Number of bits required to represent 12 distinct numbers = 4 So, Answer is (B)

UPSCFEVER - POPULAR PAGES

Join The Movement

Share

upscfever.com

Discussions and Comments

Journey of a Thousand Miles begins with One Click!!!

GATE-CS-2016 (Set 2)

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments