GATE CS 2011 Official Paper (Previous Year Paper)

The correct answer is option 1 i.e. Incomprehensible.

Explanation-

Inexplicable means incapable of being explained, interpreted or accounted for. 

• Incomprehensible: impossible to comprehend: UNINTELLIGIBLE.
• Indelible: that cannot be removed, washed away, or erased.
• Inextricable: forming a maze or tangle from which it is impossible to get free
• Infallible: incapable of error: UNERRING

Inexplicable means not explicable; that cannot be explained, understood, or accounted for. So the best synonym here is incomprehensible.

Explanation:

Let Log (P) = (1/2) Log (Q) = (1/3) Log (R) = l

∴ P = 10^k, Q = 10^2k, R = 10^3k

Now,

Option 1:

P²=Q³R²

(10^k)² = (10^2k)³ (10^3k)² 

10^2k ≠ 10^12k

Option 2:

Q² = PR

10^4k = (10^3k)(10^k)

10^4k = 10^4k

∴Q² = PR follows the given relation.

Option 3:

Q² = R³P ⇒ 10^2k ≠ 10^7k

Option 4:

R=P²Q² ⇒ 10^3k ≠ 10^6k

∴ Only option(2) is correct.

The correct answer is Option 3 i.e visiting 

Explanation:

Reading the given sentence we find that.

• The word contemplated is a transitive verb.
• A transitive verb always needs to transfer it's action on to something which is an object.
• Hence, here after the transitive verb contemplated we need a noun that will be the object.
• Out of the given options visiting is a gerund. And therefore it grammatically follows the verb contemplated.

Hence the correct answer is Option 3 i.e visiting.

Important Points

• A gerund is an -ing form of verb which acts as a noun.
• In the above case, we need a noun after the verb contemplated.
• And the gerund visiting is the appropriate option as it is a verb acting as a noun.
• Therefore the action of the verb contemplated is transferred to the gerund visiting.

Thus the correct sentence will be: "I contemplated visiting Singapore for my vacation bu decided against it."

The correct answer is Option 2 i.e Restrained

Explanation:

Reading the above statement we find that:

• The tone of the sentence clearly indicates a word similar to understated and tentative.
• The word should also be an antonym of strong.

Let's look at the meaning of the marked option:

• Restrained: Not excessively showy or ornate; understated and timid.

Hence from the above meaning, we find that restrained is similar in meaning to understated and tentative, and fits perfectly in the give sentence.

Thus, the correct answer is option 2 Restrained.

Additional Information 

Let's look at the meaning of the other given options. 

• Hyperbolic: Delibrately; or exaggerated.
• Argumentative: Given to arguing.
• Indifferent: Having no particular interest; unconcerned.

The correct answer is option 2 i.e. Split.

Explanation-

Amalgamate means to unite in or as if in an amalgam, let's have a look at all the given options. 

• Merge: to cause to combine, unite, or coalesce.
• Split: to divide lengthwise usually along a grain or seam or by layers
• Collect: to bring together into one body or place
• Separate:  to set or keep apart: DISCONNECT, SEVER

​

Amalgamate means to combine or unite to form one organization or structure. So the best option here is split. Separate on the other hand, although a close synonym, it is too general to be the best antonym in the given question while Merge is the synonym; Collect is not related.

The correct answer is Option 3 i.e what the leading causes of death are

Explanation:

Reading the above statement we find that.

• The given sentence starts by stating how to deal with bereavement and grief after a tragedy occurs and not about precautions.
• Therefore, irrespective of the causes of death, a school student rarely gets into details of causes
• Hence it is very clear that the leading causes of death are not included in a unit on bereavement.

Hence, the correct answer is option 3 i.e what the leading causes of death are.

Concept:

According to the given information:

Most dangerous microbe ∝ probability that microbe will overcome human immune system.

Most dangerous microbe ∝ area (growth of microbe)

Most dangerous microbe ∝ (quantity required)^-1

\(So, the;most;dangerous;microbe;\propto;\frac{Probability;\times;Area}{Quantity;required}\)

\(So, the;most;dangerous;microbe;=;\frac{K;\times;Probability;\times;Area}{Quantity;required}\)

\(So, the;most;dangerous;microbe;=;\frac{K;\times;Probability;\times;\pi{d^2}}{4;\times;Quantity;required}\)

Calculation:

Given:

For microbe P:

Probability (P) = 0.4, Diameter = 50 mm and Quantity required = 800 milligram of microbe/mass of body in kg.

\(The;most;dangerous;microbe;=\frac{\pi{K}}{4}\times\frac{0.4\times50^2}{800}\Rightarrow\frac{\pi{K}}{4}\times\frac{5}{4}=1.25\frac{\pi{K}}{4}\)

For microbe Q:

Probability (Q) = 0.5, Diameter = 40 mm and Quantity required = 600 milligram of microbe/mass of body in kg.

\(The;most;dangerous;microbe;=\frac{\pi{K}}{4}\times\frac{0.5\times40^2}{600}\Rightarrow\frac{\pi{K}}{4}\times\frac{4}{3}=1.33\frac{\pi{K}}{4}\)

For microbe R:

Probability (R) = 0.4, Diameter = 30 mm and Quantity required = 300 milligram of microbe/mass of body in kg.

\(The;most;dangerous;microbe;=\frac{\pi{K}}{4}\times\frac{0.4\times30^2}{300}\Rightarrow\frac{\pi{K}}{4}\times\frac{6}{5}=1.2\frac{\pi{K}}{4}\)

For microbe S:

Probability (S) = 0.8, Diameter = 20 mm and Quantity required = 200 milligram of microbe/mass of body in kg.

\(The;most;dangerous;microbe;=\frac{\pi{K}}{4}\times\frac{0.8\times20^2}{200}\Rightarrow\frac{\pi{K}}{4}\times\frac{8}{5}=1.6\frac{\pi{K}}{4}\)

Microbe S > Microbe Q > Microbe P > Microbe R.

∴ toxicity is more for microbe S and the company should target it in its first attempt.

Concept:

Total cost = Fixed cost + Variable cost

To find maxima and minima of a function y = f(x), follow these steps.

Step 1

\(Find;\frac{{dy}}{{dx}},;and;put\frac{{dy}}{{dx}} = 0.\)

Find the value of x and this value is said to be the stationary point, this is a necessary condition to find the extremum value of a function.

Step 2

\(Find;\frac{{{d^2}y}}{{d{x^2}}};\)

Check the value at the stationary point obtained in Step 1.

A function f(x) has a maxima at x = a if f’(a) = 0 and f”(a) < 0

A function f(x) has a minima at x = a if f’(a) = 0 and f”(a) > 0

A function f(x) has no maxima and minima at x = a if f’(a) = 0 and f”(a) = 0.

Calculation:

Given:

F = 100/q, V = 4q

Total cost (TC) = Fixed cost + Variable cost

\(∴;TC=4q;+;\frac{100}{q}\)

Step 1:

\(\frac{{d(TC)}}{{dq}} = 0\)

\(\frac{d(TC)}{dq}=4;-;\frac{100}{q^2}\)

∴ q = ± 5

\(\frac{{d^2(TC)}}{{dq^2}} =+ve;for;minima\)

\(\frac{{d^2(TC)}}{{dq^2}} =-ve;for;maxima\)

\(\frac{d^2(TC)}{dq^2}=\frac{200}{q^3}\)

At q = 5

\(\frac{d^2(TC)}{dq^2}=\frac{200}{5^3}\Rightarrow1.6;;(+ve;,;∴;minima)\)

At q = -5

\(\frac{d^2(TC)}{dq^2}=\frac{200}{5^3}\Rightarrow-1.6;;(-ve;,;∴;maxima)\)

∴ at q = 5, Total cost (TC) will be minimum.

Concept:

The transporter receives the same number of order each day and he currently has pending orders.

Let 'x' be the number of daily orders and 'y' be the number of pending orders.

Calculation:

Given:

Condition I:

Use of 7 trucks each day finishes all orders in 4 days.

∴ total numbers of trucks used = 7 + 7 + 7 + 7 ⇒ 28.

Total orders received in 4 days = 4x.

Pending orders = y.

∴ 4x + y = 28      eq(1).

Condition II:

Use of 3 trucks each day finishes all orders in 10 days.

∴ total numbers of trucks used = 3 × 10 ⇒ 30.

Total orders received in 10 days = 10x.

Pending orders = y.

∴ 10x + y = 30      eq(2).

Solving eq (1) and eq (2).

x = 0.33 ⇒ Daily orders

y = 26.66 ⇒ Pending orders.

Condition III:

Use of 'n' trucks each day finishes all orders in 5 days.

∴ total numbers of trucks used = 5 × n ⇒ 5n.

Total orders received in 5 days = 5x.

Pending orders = y.

∴ 5x + y = 5n   

∴ (5 × 0.33)  + (26.66) = 5n

∴ n = 5.66 ≈ 6

∴ minimum 6 number of trucks required so that there will be no pending order at the end of the 5^th day.

Concept:

\({\bf{Volume}};{\bf{of}};{\bf{liquid}};{\bf{left}} = {\bf{x}}{\left( {\frac{{{\bf{x}} - 1}}{{\bf{x}}}} \right)^{\bf{n}}}\)

where x = Original amount of liquid, n = Number of times replaced.

Calculation:

Given:

x = 10 litre, n = 3

Now, we know that

\({\bf{Volume}};{\bf{of}};{\bf{spirit}};{\bf{left}} = {\bf{x}}{\left( {\frac{{{\bf{x}} - 1}}{{\bf{x}}}} \right)^{\bf{n}}}\)

∴  Volume of spirit left = \(10{\left( {\frac{{10 - 1}}{{10}}} \right)^3} = \frac{{729}}{{100}} = 7.29\)  litres

The correct answer is option 3.

Concept

Any identifier is also a token so it is recognized by lexical Analyzer and hence it is recognized in the lexical analysis of the program

Phases in a compiler:

The correct answer is option 4:

Key Points

Since it is Layer-4 Firewall so it includes the layers → Physical Layer, Data Link Layer, Network Layer as well as Transport Layer

Allow →  Transport Layer or those layers who comes below transport Layer

Not Allow → Application Layer

Option 1:  Transport Layer specific

It is possible to block entire traffic by blocking all the traffic on port number 80. so, here don't need to check anything that it is application layer specific or not. we only need to block port number 80 for the required time interval.

Option 2:  Network Layer specific

ICMP is a network layer protocol that comes below the transport layer

Option 3:  Network Layer specific

IP addresses are used in the network layer, which below the transport layer.

Option 4:  Application Layer specific

In this option given that it is a multi-user system, so many users use the same port for communication because of this we can't block any specific port number. if we block a specific port number, all the users also blocked who is using that port number for communication. while we want to block a specific user, so how to do this. We need application layer-specific information of the user like user_id type of things that can't be checked as it is a 4-layer firewall. so it is not possible to allow other users and block some specific at the same time using a 4-layer firewall.

Sample space = {HH, HT, TH}

Required probability = 1/3

The correct answer is option 3

SMTP:

• SMTP stands for Simple Mail Transfer Protocol and it is an application layer protocol.
• SMTP is used to send an email from a mail client to a mail server.
• SMTP uses port 25.

POP:

• POP stands for Post Office Protocol and it is also an application layer protocol.
• POP allows an email client to download an email from an email server.

HTTP:

The Hypertext Transfer Protocol (HTTP) is an Application Layer protocol and is used to check email in a web browser.

So, m1 : SMTP  m2 : POP m3 : HTTP

Data

LOC = lines of code 

Let L1  = x and L2 = 2x

Calculation:

Total cost of the project:

\(\frac{x}{10000} \times 1000000 + 5\times 100000 = \frac{2x}{10000}\times750000 + 5 \times 50000\)

100x + 500000 = 150x + 250000

∴ 50x = 500000 – 250000

∴ x = \(\frac{250000}{50} = 5000\)

∴ L1 = x = 5000

The correct answer is t1 < t2

Key Point

Switching between user and kernel modes t1 is generally faster than switching between two processes t2 because:

• A mode switch (between user and kernel modes) occurs within the same process context, so it does not involve changing the process's memory or CPU registers.
• A process switch, on the other hand, requires a context switch, which includes saving and loading the state (CPU registers, memory mappings, etc.) of the processes involved. This is a more time-consuming operation than just switching modes within a single process.

Thus, typically, t1 < t2

Effort (person per month) = α.(kDSI)ⁿ

kDSI = Kilo LOC

= 2.8*(40)^1.2

= 2.8*83.6511

= 234.22 (person per month)

The correct answer is option 2

Option 1: SAME expressive power

NFA and DFA have the same expressive power.

Option 2: DIFFERENT expressive power

Some languages are accepted by NPDA but not by deterministic PDA. Therefore expressive power of DPDA < expressive power of NPDA.

So, deterministic pushdown automata (DPDA) and non-deterministic pushdown automata (NPDA) have DIFFERENT expressive power

Option 3: SAME expressive power

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine have the same expressive power

Option 4: SAME expressive power

Multi-tape Turing machines has same power as single tape Turing machines.

option 2: supported by pure HTML

Refresh the document every 30 seconds

<head>

  <meta http-equiv="refresh" content="30">

</head>

option 3:  NOT supported by pure HTML

Display the client time as part of the page → without Java script it is impossible

The correct answer is option 4.

Key Points The software requirements specification document is a detailed explanation of the behavior of a system to be developed, and it may include a set of use cases that describe user interactions with the software. There are also non-functional requirements in it. Non-functional requirements impose design constraints.

The following aspects of a system should be documented in an SRS document: Implementation Goals, Functional and Non-Functional Requirements. An algorithm for Software Implementation is required in the later stages of the software development process.

Hence the correct answer is Algorithms for Software Implementation.

The correct answer is option 4

Key Points

• Higher priority interrupt levels are assigned to requests which if delayed or interrupted could have serious consequences. Devices with high-speed transfer such as magnetic disks are given high priority and slow devices such as keyboards are given low priority.
• Since mouse pointer movements are more frequent than keyboard ticks. So it's obvious that its data transfer rate is higher than the keyboard.
• Interrupt from the CPU temperature sensor would have serious consequences if we ignored it and overheat can damage CPU circuitry.

Shortcut Trick

Priority with respect to interrupt

CPU temperature sensor > Hard Disk > Mouse > Keyboard.

Key PointsOption 1: Bank Account_Num is a candidate key

False, If two students hold a joint account then BankAccount_Num is not a candidate key and will not uniquely determine other attributes.

Option 2: Registration_Num can be a primary key

True, A Unique registration number of each registered student is a candidate key and uniquely determines other attributes.

Option 3: UID is a candidate key if all students are from the same country

True, Unique identity number, unique at the national level for each citizen is a candidate key and uniquely determines other attributes.

Option 4: If S is a superkey such that S∩UID is NULL then S∪ UID is also a superkey

True, Let's consider super key is  Registration_Num  and Registration_Num ∩UID is NULL then  Registration_Num ∪ UID is also a superkey.

Hence the correct answer is Bank Account_Num is a candidate key.

The correct answer is option 4

Formula:

A ⊕ B = A.B̅   + A̅ .B 

A ⊙ B = A̅ .B̅   + A.B 

EXPLANATION

Let's take 2-input variable A and B

Option 1: It is XNOR

\(\overline{A\oplus B} = \overline{A.\overline{B} + \overline{A}.B}\)

= (A̅ + B).(A + B̅ ) 

= A̅ .B̅   + A.B 

= A ⊙ B

Option 2: It is XNOR

\(\overline{\overline{A}\oplus \overline{B}} = \overline{.\overline{A}{B} + A.\overline{B}}\)

= (A + B̅).(A̅ + B) 

= A.B + A̅ .B̅ 

= A ⊙ B

Option 3: It is XNOR

\({\overline{A}\oplus {B}} = {\overline{A}.\overline{B} +{A}.B}\)

= A ⊙ B

Option 4: It is NOT XNOR

Make changes in the above diagram

It is XOR

The correct answer is option 2

Some laws of Boolean Algebra:

Distributive Law:

• P +QR = (P + Q).(P + R)
• P(Q + R) = PQ + PR

Inverse Law:

• PP̅ =0
• P + P̅ =1

EXPLANATION:

F = (P + Q̅ + R̅)⋅(P + Q̅ + R)⋅(P + Q + R̅)

F= ((P + Q̅) + R̅.R)(P + Q + R̅)

F = (P + Q̅)(P + Q + R̅)

F = P + Q̅.(Q + R̅)

F = P + Q̅R̅

The correct answer is option 1

Concept:

Binary modulo N counter can count up to 0 to N – 1

Therefore, binary modulo 258 counters will count from 0 to 257 (order may vary)

Formula:

Minimum number of flip flop needed = ⌈log2 N⌉

Calculation:

An n-bit binary counter consists of n flip-flops and can count in binary from 0 to 2ⁿ – 1

Mod 258 counter has 258 states. We need to find the number of bits to represent max 257

\(\lceil{log_2n}\rceil = \lceil{log_2258}\rceil =9\) bits required

So the minimum number of D flip-flops needed is 9.

The correct answer is option 3

Concept:

Multiple threads of the same process share other resources of the process except for register, stack, and stack pointer. In particular, a process is generally considered to consist of a set of threads sharing an address space, heap, static data, code segments, and file descriptors.

Thread of the same process doesn't share program counter (register), stack,  registers

Option 1:  FALSE

On a per-thread basis, the OS maintains only the CPU register state → Incorrect statement

Because in the above figure not only CPU register maintained by OS but also maintained code, data, files, stack.

Option 2:  FALSE

The OS does not maintain a separate stack for each thread → Incorrect statement

Because OS maintained a separate stack for each thread as shown in the above figure

Option 3:  TRUE

On a per-thread basis, the OS does not maintain a virtual memory state →  Correct statement

Because OS does not maintain a virtual memory state for an individual thread 

So, it is a true statement.

Option 4:  FALSE

On a per-thread basis, the OS maintains only scheduling and accounting information → Incorrect statement

Because OS maintains not only scheduling and accounting information but also maintained code, data, files, stack.

The correct answer is option 2

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 a graph such that adjacent vertices have different colors.

Explanation:

So, both K4 and Q3 are planar.

Concept:

Random variables:

Random variable assigns a real number to each possible outcome.

Let X be a discreet random variable,then

The variance of X = R =E[X2]- (E[X])2

Explanation:

• The difference between the expectation of the square of a random variable (E[X2]) and the square of the expectation of the random variable (E[X])2 is called the variance of a random variable
• Variance measure how far a set of numbers is spread out
• A variance of zero(R=0) indicates that all the values are identical
• A variance of X = R =E[X2]- (E[X])² This quantity is always non-negative as it is an expectation of a non-negative quantity
• A non-zero variance is always positive means R > 0

So, R ≥ 0 is the answer.

The correct answer is option 1

Finite Automata(FA):

• The first phase of the compiler is called lexical analysis or scanning. The lexical analyzer reads the stream of characters making up the source program and groups the characters into a meaningful sequence called lexemes.
• For each lexeme, the lexical analyzer produces tokens as output for the parser and tokens are expressed in regular expressions

So, a simple Finite Automata is sufficient for it

Phases in a compiler:

Additional Information

The correct answer is option 2

Data:

page fault service time = S = 10 ms = 107 ns

page fault rate = p = \(\frac{1}{10^{6}}\)

memory access time = m = 20 ns

Formula:

Effective Memory access time (EMAT) = p × (S + m) + (1 - p) × m

∴ EMAT = p×S + m 

Calculation: 

EMAT = \(\frac{1}{10^{6}}\)× 107 + 20 = 10 + 20

EMAT = 30 ns

Concept

Index addressing mode/ Base indexed addressing/ Base register indexed addressing:

Addresses have two parts: the number of an index register and a constant. The address of the operand is the sum of the constant and the contents of the index register. It contains indexed (direct) addressing, indexed immediate addressing, and indexed indirect addressing.

Explanation:

Base indexed addressing, as content in the R2 used as an indexed and base address will be 20

Example:

Let us have an array of addresses (in memory) where the data is present and we want to access the data that is present at address 25

LW R1, 20 (R2),

We have an indexed register R2 in which the index value 5 is present and then this indexed value is added to the base address 20 to get the desired location where the data is present and then transfer to R1

Effective address(EA) =Base address + Indexed register(R)

Effective address(EA) =20 +5 =25

Now, we get the data 5 at address 25, then it is loaded to the R1

Additional Information

Immediate Addressing:

Immediate addressing provides the operand value in the instruction itself for example adding a constant 5 to the accumulator value.

Register indirect addressing mode:

In register indirect addressing mode, the data to be operated is available inside a memory location and that memory location is indirectly specified by a register pair.

Register addressing mode:

In register addressing mode, the data to be operated is available inside the register(s) and register(s) is(are) operands. Therefore, the operation is performed within various registers of the microprocessor

The correct answer is option 3

EXPLANATION:

Let ASCII value of A be x and therefore the ASCII value of E will be x + 4

*char p = c;  //p is a pointer of type char that points to the starting address of character array

printf("%s", p + p [3] - p [1]);  // This will print the string from where updated pointer p points to the address( which is 104).

p = p + p [3] - p [1]

p = 100 + 'E' - 'A' = 100 + (x+4) - (x) = 104 = starting address

printf("%s", p); 

Therefore output is 2011

The correct answer is option 2

CONCEPT:

A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.

Explanation:

Option 1: not a max heap

Since there is no right child for element 8. Hence it is not a complete binary tree. Therefore it is not a max heap

Option 2: max heap

Follow max heap properties

Option 3: not a max heap

Reason:

In a max heap, the keys of parent nodes are always greater than or equal to those of the children

but in this option, the child node 8 is greater than parent node 5.

Option 4: not a max heap

Reason:

In a max heap, the keys of parent nodes are always greater than or equal to those of the children

but in this option child node, 10 is greater than parent node 8.

Key Points

Option 1: P ∩ Q 

Regular ∩ context-free is context-free and not regular. (pnqn  ∩ pq )=pnqn is context-free.

Option 2: P-Q

Regular-context-free

Regular∩ not context-free is not even context-free and not regular.

Option 3: Σ^* − P

Σ^* − P is an equivalent complement of P, hence regular. 

Option 4: Σ − Q*

Σ* − Q is an equivalent complement of Q and  It is not even context-free and not regular. 

Hence the correct answer is Σ* − P.

Additional Information

The correct answer is Option 1.

Key Points

• The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example ,a[] = {3, 10, 2, 1, 20} Output: Length of LIS = 3 The longest increasing subsequence is 3, 10, 20.
• We can see that there are many subproblems in the above recursive solution which are solved again and again. So this problem has Overlapping Substructure property and re-computation of same subproblems can be avoided by either using memorization or tabulation.
• If we closely observe the problem then we can convert this problem to longest Common Subsequence Problem. Firstly we will create another array of unique elements of original array and sort it. Now the longest increasing subsequence of our array must be present as a subsequence in our sorted array. That’s why our problem is now reduced to finding the common subsequence between the two arrays.

Hence the correct answer is The algorithm uses dynamic programming paradigm.

The correct answer is option 3.

Key Points

Statement I: L1 = {0p1q | p, q ∈ N},

Regular expression: 0+1+

Here, any number of 0's followed by any number of 1's. L1 requires no stack. Hence L1 is regular.

Every regular language is a context-free language.

Statement II: L2 = {0p1q | p, q ∈ N and p = q}

Context-Free Language: L2 =  {0p1p | p ∈ N}

Here, the number of 0's is equal to the number of 1's. L2 requires only one stack. Hence L2 is context-free language.

Statement III: L3 = {0p1q0r | p, q, r ∈ N and p = q = r}.

context Sensitive language: L3 = {0p1p0p | p  ∈ N}.

Here, the number of 0's followed by the equal number of 1's followed by equal to number 0's. It depends on three symbols. L3 requires two stacks. Hence L3 is a context-sensitive language.

It is not a context-free language

Additional Information

The correct answer is Option 2.

Key Points

 

Option 1: FALSE

7↓3↑4↑3↓2

= (7↓(3↑(4↑(3↓2))))     // order of execution

Since ↓ has higher precedence and therefore it is not correct

Option 2: TRUE

7↓3↑4↑3↓2

=7↓(3↑(4↑3))↓2

=(7↓(3↑(4↑3)))↓2     // order of execution

Since ↓ has left-associative and ↑ has  right-associative

Also ↑ has higher precedence and ↑ has lower precedence. 

Therefore it is correct.

Option 3: FALSE

7↓3↑4↑3↓2

7↓(((3↑4)↑3)↓2)     // order of execution

Since ↑ is left associative and therefore it is not correct

Option 4: FALSE 

7↓3↑4↑3↓2

(((7↓3)↑4)↑3)↓2)     // order of execution

Since ↑ is left-associative and therefore it is not correct

The correct answer is option 1.

Calculation:

Non-pipelined system require ,

\((2+2+1+1+1) \times 500 \space cycles +1+1=3502 \space cycles \)

DMA clock need = \(20+2 \times 500 \)

                           = 1020 cycles

Speed up  = \(3502 \over 1020\)

Speed up  = 3.43

Hence the correct answer is 3.4.

The correct answer is 1.

Key Points

Only one way for a given particular unlabeled binary tree is possible.

Example:

If a given particular unlabeled binary tree is, For keys 1,2,3,4,5,6 the only one arrangement is possible.

Hence the correct answer is 1.

Additional Information

The number of distinct binary search trees possible for n nodes is similar to counting the no. of distinct binary trees possible for n nodes assuming nodes are unlabeled. Hence, this value will also be  \({^{2n}C_n } \over (n+1)\)

The correct answer is option 1.

Key Points

The given predicate is, 

P(x)= -(x = 1) ∧ ∀ y(∃z(x=y*z) ⇒ (y = x) ∨ (y = 1))

If x is a prime number then (x ≠ 1 and the only divisors of x are x and 1)

∴P(x) is true means x is a prime number.

Hence the correct answer is P(x) being true means that x is a prime number.

The correct answer is option 4.

Calculation:

\(\displaystyle\int^{\pi/2}_0{\dfrac{\cos x+i\sin x}{\cos x-i \sin x}}dx\)

According to Euler’s formula, \(e^{iθ}​ = cos θ + i sin θ \ e^{-iθ}​ = cos θ - i sin θ \)

Therefore

\(e^{ix} = cos x+ isinx \ e^{-iθ}​ = cos θ - i sin θ \ I=\int_{0}^π{ e^{ix} \over e^{-ix} } dx \ I =\int_{0}^{π \over 2}{ e^{i2x} } dx\)

\( \ I = [{ e^{i2x} \over 2i}]_{0}^{π \over 2} \ I= {1 \over 2i}[cos2x+isin2x ]_{0}^{π \over 2} \ I= {1 \over 2i} \times (-2) \I={ -1 \over i } \I=i \space \space \space \space \space \space \space \space (∵ {1 \over i} =-i) \)

Hence the correct answer is i.

The correct answer is option 4.

Key Points

Index position of mode and median are the same. So option 1 and option 2 is not the answer.

μy = aμx + b

Correct, Y_i = a X_i + b

          \(ΣY_i = Σ(aX-i+b) \ ΣY_i=a(ΣXi)+n b \ {(Σ Y_i) \over n }={a(ΣX_i) \over n}+b\)

          μy = aμx + b

σy= aσx + b

Incorrect: variance of the constant is zero.

           \(σ_y= \sqrt { {1 \over n} Σ(μ_y - Y_i)^2 } \ σ_y= \sqrt { {1 \over n} Σ(μ_x+b - Y_i)^2 } \ σ_y= \sqrt { {1 \over n} Σ(aμ_x+b -aX_i-b)^2 } \ σ_y= \sqrt { {1 \over n} Σ(aμ_x-aX_i)^2 } \ σ_y= a \sqrt { {1 \over n} Σ(μ_x-X_i)^2 } \ σ_y= a σ_x\)

           σ_y= a σ_x

Hence the correct answer is σy= aσx + b

The correct answer is option 1.

EXPLANATION:

There are 5 cards (each carrying a distinct number from 1 to 5) in the deck. 

 

So arranging two cards among 5 cards, sample space will 5p3= 20 ways.

S → Total sample space.

n(S) = 20

E → Two cards are selected with the number on the first card being one higher than the number on the second card.

n(E)= {(2,1), (3,2), (4,3), (5,4) } = 4 ways

P(E)=\(\frac{n(E)}{n(S)}={4 \over 20 }= {1 \over 5}\)

Hence the correct answer is \(1 \over 5\).

The correct answer is option 1.

Concept:

Shortest Remaining Time First is a preemptive shortest job first scheduling algorithm, in which the process with the smallest amount of burst time is executed in the CPU.

Formula:

TAT = CT - AT

WT = TAT - BT

Calculation:

GANTT CHART:

Average waiting time = \({{(4+0+11)} \over 3}={15 \over 3 }=5\)

Hence the correct answer is5.

NOTE:

TAT = Turn Around Time

CT = Completion Time

WT = Waiting Time

BT = Burst Time

AT = Arrival Time

Answer: Option 4

Explanation:

Exp –    Load R1, a ; R1   ← M[a]

Load R2, b ; R2   ← M[b]

Sub R1, R2 ;  R1    ←  R1 - R2

Load R2, c  ; R2      ←  M[c]

Load R3, d  ; R3     ←  M[d]

Add R2, R3 ; R2   ←  R2 + R3

Load R3, e  ; R3      ←  M[e]

Sub R3, R2  ; R3   ←  R3 - R2

Add  R1, R3  ; R1   ←  R1 + R3

Total 3 Registers are required minimum.

The correct answer is option 1

Explanation:

Taking log base 2 on all the functions

 Increasing order of asymptotic complexity of functions f1, f2, f3 and f4  is f3 < f2 <f4 <​ f1

The correct answer is option 3

Concept:

If we multiply two matrices [A]_{l × m} and [B]_{m × n}

Then the number of scalar multiplications required = l × m × n

Data:

Given 4 matrix are given with their dimensions

Calculation:

Total number of ways of multiplication =\(\frac{^{2n}C_n}{n+1}\)

n = 4 - 1 = 3

Total number of ways of multiplication =\(\frac{^{2n}C_n}{n+1}\) =5

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

1. (M1M2)(M3M4)
2. M1 ((M2M3) M4)
3. M1(M2(M3M4))
4. ((M1M2)M3)M4
5. (M1(M2M3))M4

The minimum number of scalar multiplication can find out using (M1(M2M3))M4

(M1(M2M3))M4 =19,000

Shortcut Trick

Frist find scaler multiplication of those which are common in some of the 5 ways of multiplication

then it will become easy to solve

(M1M2) is common in 1 and 4

(M2M3) is common in 2 and 5

(M3M4) is common in 1 and 3

The correct answer is option 3.

Key Points

Query 1: \(Q1:\pi_{A_i...A_p}(\sigma_{A_p=c(r)})\)

Returns only a few tuples that satisfy the condition, therefore it requires Hashing. If the record is accessed for a particular value from the table, hashing will do better.

Query 2: \(Q2:\pi_{A_i...A_p}(\sigma_{c_1\le A_p\le c_2}(r))\)

Returns the range of tuples based on condition therefore it requires an ordered index. If records are accessed in a range of values, ordered indexing will perform better.

Hence the correct answer is Hashing will outperform ordered indexing on Q1, but not on Q2

Additional Information

Indexing:

Indexing is a data structure technique to efficiently retrieve records from database files based on some attributes on which the indexing has been done. Indexing in database systems is similar to the one we see in books. The ordering field is the field on which the records of the file are ordered. It can be different from the primary or candidate key of a file.

Hashing:

In a huge database structure, it is very inefficient to search all the index values and reach the desired data. Hashing technique is used to calculate the direct location of a data record on the disk without using an index structure.

The correct answer is option 1

Concept:

Eigenvalues of the upper triangles matrix or lower triangular matrix are just the diagonal elements of the matrix.

Calculation:

In the given matrix below,

P = \(\begin{bmatrix}1&2&3\\ 0&4&7\\ 0&0&3\end{bmatrix}\)

Diagonal elements are 1, 4, and 3, so,1, 4, 3 are the eigenvalues

Alternate Method

On applying |P - λI| = 0 yields

\(\left| {\begin{array}{*{20}{c}} {1 - \lambda }&1&0\ 0&{4 - \lambda }&1\ 0&0&{3 - \lambda } \end{array}} \right| = 0 \Rightarrow \left( {1 - \lambda } \right)\left( {4 - \lambda } \right)\left( {3 - \lambda } \right) = 0\)

⇒ λ = 1, 4, 3 are the eigenvalues

Key Points

Please do remember all the properties of eigenvalues and eigenvectors. Don’t apply the formula. It will be time-consuming.

Properties of Eigenvalues:

• The sum of Eigenvalues of a matrix A is equal to the trace of that matrix A
• The product of Eigenvalues of a matrix A is equal to the determinant of that matrix A
• If λ is an eigenvalue of a matrix A, then λn will be an eigenvalue of a matrix An.
• If λ is an eigenvalue of a matrix A, then kλ will be an eigenvalue of a matrix kA where k is a scalar

The correct answer is option 2

Concept:

The segments are separated by registers R_i that holds the intermediate results between the stages.

Data:

Stage delay and corresponding register delay given

S1 = 5 ,

S2 = 6 ,

S3 = 11,

S4 = 8,

And corresponding register delay is 1 for each stage

Number of stage = 4

Explanation:

Time is taken to execute N instructions in non-pipelined implementation will be =(5+6+11+8)N = 30×N

Clock period for pipelined implementation =max(5,6,11,8) + 1 = 12 ns

Time is taken to execute N instructions in pipelined implementation will be = (4 + N-1)12 ≈ 12×N (N is very large)

Speedup = \({30N\over12N }=2.5\)

Let n =3 and k = 1,2,3,.....

L = \(a^{3k}\)

Therefore, DFA will accept the language aaa,aaaaaa, aaaaaaaaa, ... i.e. \((aaa)^+\)

 

So, (n+1) states

The correct answer is option 4

Data:

Main Memory size =2³² Byte

Cache size = 8KB = 2¹³ Byte

Block size = 2⁵ Byte

Valid = 1 bit

Modified = 1 bit

**Formula:**cachesizeblockscachesizeblocksizetotallinesl

number of bits = ⌈log2 n⌉ 

Number of lines in cache = \(\frac{cache;size}{block;size}\)totallineslinesinaset

MM = tag + index + block offset .....(in bits)

Total bits required to store meta-data of 1 line =  Valid bit +  Modified bit + tag bit

Calculation:

Number of cache lines =\({{Cache}\ {size} \over block\ size }=\frac{2^{13}B}{2^5B}= 2^8B\)

So, index bit = 8

MM = tag + index + block offset

32 = tag +8 + 5

tag =19 bits

Total bits required to store meta-data of 1 line =  Valid bit +  Modified bit + tag bit

Total bits required to store meta-data of 1 line = 1  + 1 + 19 =21 bits

Cache memory has 256 lines

So, Total memory required =21 bits × 256 = 5376 bits

The correct answer is option 2

Data:

Seek time = 10 ms

Rotational speed = 6000 rpm

Transfer time has given negligible

total 100 files are loaded from the disk

Formula:

Disk access time = Seek time + Rotational latency + Transfer time

Calculation:

Rotational speed = 6000 rpm

6000 rotation → 60s

1 rotation → \({60\over6000}s\)

1 rotation → 10 ms

Average rotational delay = 10 ÷ 2 = 5 ms

Disk access time = seek time + Rotational latency + transfer time(given negligible)

Disk access time = 10 ms + 5ms + 0 = 15 ms

Now, total time to transfer one library → 15 ms

So, the total time to transfer 100 libraries → 100 × 15ms =1.5s

The correct answer is option 1.

Key Points

Minimization of DFA :

Step 1:

We will divide Q (set of states) into two sets. One set will contain all final states and another set will contain non-final states.

P₀ = {p,q,r}  P₁ ={s,t}

Step 2: 

Find Pk by partitioning the different sets of Pk-1. In each set of Pk-1, we will take all possible pair of states. If two states of a set are distinguishable, we will split the sets into different sets in Pk.

Here state p and q states go to only P₁ and P₀. But state r go to the only P₀. Hence state ' r ' is a different set. 

P₀ ={p,q} P₁ ={r} P₂ ={s,t} 

Here state p and state q  are different p goes to only P₀ and P2 and q goes to only P1 and P2. So both are different.

P0 ={p} P1 ={q}  P2 ={r} P3 ={s,t}

P0 ={p} P1 ={q}  P2 ={r} P3 ={s,t}

Step 3: 

Stop when Pk = Pk-1 (No change in the partition) 

Step 4: 

All states of one set are merged into one.

No. of states in minimized DFA will be equal to no. of sets in Pk. 

minimized DFA is,

Alternate Method

Option 2 and Option 3:

Minimized DFA  accepts string ' b ' but the given deterministic finite automata didn't accept the string b Hence option 2 and option 3 are false.

Option 4:

Minimized DFA  accepts string 'bba' but the given deterministic finite automata didn't accept the string 'bba' Hence option 4 is false.

 

After executing the given query, the output would be

The correct answer is option 3.

Key Points

Hence the correct answer is T2, T4, T5, T6.

The correct answer is option 2

Explanation:

So, foo (345, 10) return the value 12

foo(345,10) = 5 + foo(34, 10)

foo(345,10) = 5 + 4 + foo(3, 10)

foo(345,10) = 5 + 4 + 3 + foo(0, 10)

foo(0, 10) return 0

because 0< 0 false

foo(345,10) = 5 + 4 + 3 + 0 =12

The correct answer is option 4

Explanation:

foo (513, 2) returns the value 2

foo (513, 2) = 1 + foo (256, 2)

foo (513, 2) = 1 + 0 + foo (128, 2)

foo (513, 2) = 1 + 0 + 0 + foo (64, 2)

foo (513, 2) = 1 + 0 + 0 + 0 + foo (32, 2)

foo (513, 2) = 1 + 0 + 0 + 0 + 0 + foo (16, 2)

foo (513, 2) = 1 + 0 + 0 + 0 + 0 + 0+ foo (8, 2)

foo (513, 2) = 1 + 0 + 0 + 0 + 0 + 0+ 0+ foo (4, 2)

foo (513, 2) = 1 + 0 + 0 + 0 + 0 + 0+ 0+ 0+ foo (2, 2)

foo (513, 2) = 1 + 0 + 0 + 0 + 0 + 0+ 0+ 0+ 0+ foo (1, 2)

foo (513, 2) = 1 + 0 + 0 + 0 + 0 + 0+ 0+ 0+ 0+ 1+ foo (0, 2)

foo (0, 2) return value 0

because 0<0 false

foo (513, 2) = 1 + 0 + 0 + 0 + 0 + 0+ 0+ 0+ 0+ 1+ 0

foo (513, 2) = 2

The correct answer is option 4.

Key Points \(D_P =Q_R \D_Q=\bar Q_P. \bar Q_R \D_R= \bar Q_R.Q_Q \)

From above table If P Q R = 0 1 0 [at 1 ^st clock output] then next state of P Q R values = 0 1 1 [at 2 ^nd  clock].

Key Points

 \(D_P =Q_R \D_Q=\bar Q_P. \bar Q_R \D_R= \bar Q_R.Q_Q \)

Hence the is a MOD-4 counter hence the total number of distinct output (states)=4

Key Points

 

(6 is changed to 2)

So

N3→N1→3

N3→N2→2

N3→N3→0

N3→N4→2

N3→N5→5(Via N2)  (3,2,0,2,5)

New distance-vector at a node, N3 (3,2,0,2,5).

Key Points

 

It is down So N2→N1 is ∞

If poison we use in applied these N2 says it is always ∞. But in question there asked what is its value at N3. So the alternative route is N3→N4→N5→N2→N1, so its value is 2+4+3+1=10.

Please note, in question, they asked "NEXT ROUND" of update, which means '∞' at N2 will be received by N5 but not by N3, Hence N3 still assumes N3→N4→N5→N2 is all alternative route to N1.

The cost to N1 in the distance vector of N3 is 10.

The correct answer is option 2.

Key Points

Pattern observed in weight of MST being formed:

For n=3 ⇒ (1+2+3)+(1)

For n=4 ⇒ (1+2+3+4)+(1+2)

For n=5 ⇒ (1+2+3+4+5)+(1+2+3)

For n=6 ⇒ (1+2+3+4+5+6)+(1+2+3+4)

In general, the total weight of the minimum spanning tree for n:

= \(\sum_{i=1}^{n} i + \sum_{i=1}^{n-2} i\)

=n² - n + 1

Hence the correct answer is n2-n+1.

Alternate Method

 For n = 5, The graph is

 Cost of the minimum spanning tree (MST) of a graph with n=5 nodes

only option B satisfy.

The correct answer is option 3.

Key Points

 For n=10, The graph is

 

Cost of the minimum spanning tree (MST) of a graph with n=10 nodes

The length of the path from ν5 to ν6 in the MST= 8+4+3+6+10 = 31

The path  is V5⇒V6: (V5-V3-V1-V2-V4-V6)