GATE CS 2012 Official Paper (Previous Year Paper)

The given sequence is:

Explanation:

Let E(x) represent mean

Then by the property of mean

E(Cx) = cE(x) where c is constant

And E(x + c) = E(x) + E(c) = E(x) + c

∴ Options P and R always holds true.

Now,

Let Var (x) represent the variance

Then var (x + c) = var (x) + var (c)

 var (x + c) = var (x)    {∵ var (c) = 0}

∴ S.D (x + c) = S.D (x)

Now,

var (cx) =(c²)var (x)

S.D (cx) = (c)S.D (x)

∴ Options Q and S are incorrect.

Calculation: 

Let 100 shock absorbers are supplied

so, X supplies = 60 (60% of 100)

Y supplies = 40 (40% of 100)

Reliable supply by X = 96% of 60 = 57.6

Reliable supply by Y = 72% of 40 = 28.8

Required probability $P\left( Y \right) = \frac{{28.8}}{{57.6 + 28.8}} = 0.33$

Given:

y = 2x – 0.1x²

differentiating w.r.t x

$\frac{{dy}}{{dx}} = 2 - 0.2x = 0$

$x = \frac{2}{{0.2}} = 10$

${\left( {\frac{{{d^2}y}}{{d{x^2}}}} \right)_{x = 10}} = - 0.2 < 0$

∴ At x = 10, y will have a maximum value.  

y_max = y(10) = (2 × 10) - 0.1(10²) = 10

Explanation:

• Clearly, in the given question there is nothing related to gender is mentioned in the advertisement, eliminating options 1)
• Xenophobic means having or showing a dislike of or prejudice against people from other countries. There, is no such thing related to people of other countries is mentioned in the advertisement, eliminating it too.
• The requirements that are mentioned for the post is designed to make the post attractive, Transportation paid, expenses reimbursed are mentioned. So option 4) is the most suitable answer.

The correct answer is option 1- that

Explanation 

To answer this question, we need to understand the meaning of defining and non-defining clauses. 

• A defining clause (also called an essential clause or a restrictive clause) gives information essential to the meaning of the sentence. We always use 'that' with defining clauses.

Example: My bike that has a broken seat is in the garage.

• Unlike defining clauses, non-defining clauses (also called nonessential or nonrestrictive clauses) don’t limit the meaning of the sentence. You might lose interesting details if you remove them, but the meaning of the sentence wouldn’t change. We always use 'which' with non-defining clauses.

Example: The goat was standing on the roof of the house which was abandoned.

In the given sentence, if we consider the first clause, the information given is incomplete and it can only be completed via the introduction of the second clause. Hence, we have to use 'that' in this sentence.

The correct answer is option 4. 

Explanation 

As we can see, the question has been framed to test our grammatical knowledge regarding the use of the adjective 'less'. 

• 'Less' has been used correctly in option 1. Here, 'less' means 'minus'.
• 'Less' has been used correctly in option 2 as well. It has been used here to compare the country's expenditure to that of Bangladesh.
• 'Less' has been used correctly in option 3 as well. If we don't use the word 'than' after 'less', we have to use the comparative form of less- 'lesser'.
• The usage of 'less' is wrong in option 4. 'Less' is generally used as a way of comparing two quantities or amounts. Here, the word 'less' needs to be replaced with the words 'little' or 'low'.

The correct answer is option 1- Diminish Explanation

Mitigate: make (something bad) less severe, serious, or painful; lessen the gravity of (an offence or mistake)

Diminish: make or become less; decrease in size, degree etc.

Thus we can see that among the options, 'diminish' is closest in meaning to the word 'mitigate'. They are near-synonyms.

The meaning of the other words:

• Divulge: make known (private or sensitive information)
• Dedicate: devote (time or effort) to a particular task or purpose
• Denote: be a sign of, indicate; stand as a name or symbol for

The correct answer is option 2- setbacks

Explanation   

Setback: something that happens that delays or prevents a process from developing

From the given context, it is clear that the mission finally resolved the conflict after many failed attempts and obstacles. Thus, 'setback' is the correct word for the given blank.

   

The meaning of the other words:

• Attempt: an effort to achieve or complete a difficult task or action
• Meeting: an assembly of people for a particular purpose, especially for formal discussion
• Delegation: a group of people who have been sent somewhere to have talks with other people on behalf of a larger group of people.

You may be confused regarding the use of 'attempts' and 'setbacks'. Attempt does not have any negative connotation to it, whereas setback has one. As the sentence is specifically referring to fruitless attempts taken in the past, 'setbacks' would be a more apt choice.

As q = total number of quantities produced.

Total cost = 5q²

Total sales = 50q

Profit (P) = total cost – total sales

P = 5q² – 50q

Differentiating w.r.t q

$\frac{{dP}}{{dq}} = 10q - 50 = 0$

$q = \frac{{50}}{{10}} = 5$

$\frac{{{d^2}P}}{{d{q^2}}} = 10 > 0$

∴ At q = 5, profit (P) is maximum.

The correct answer is “option 2”.

EXPLANATION:

I₁ states that:

Statement

Consider A = it rains,

B = match played

So, If (it rains) then (match will not be played) that means,

A → (¬ B)

Inference states that “there was no rain” means A = false (F)

Therefore, for any F → (¬ B) i.e. for any "F that implies not B" is true.

So this inference is valid.

Here the only condition is if it rains the match will not be played. That doesn’t mean if it will not rain then the match will be played.

If the match was played then it means it doesn’t rain.

So this inference is valid.

I₂ states that:

Statement

Consider A = it rains,

B = match played

So, If (it rains) then (match will not be played) that means,

A → (¬ B)

Inference states that “the match was played”.

Here the only condition is if it rains the match will not be played. If the match was played then it means it doesn’t rain.

That doesn’t mean if it will not rain then the match will be played.

So this inference is invalid.

Hence, the correct answer is "option 2".

The correct answer is "option 3".

CONCEPT

Normalization is used to minimize redundancy from a set of relations.

It is used to organize data effectively in the database.

Normal forms are used to reduce redundancy from the database.

Third Normal form: A relation is said to be in third normal form if it is in 2NF & there must not exist any transition dependency.

Also, it must satisfy these properties:

1. For the function A → B, A should be a super key.
2. B should be a part of a key attribute or prime attribute i.e. B should be a part of a candidate key.

BCNF: A relation is said to be in Boyce-Codd normal form (BCNF) if it is in 3NF & must satisfy this property: 

1. For the function A → B, A should be a super key.

EXPLANATION:

Option 1: FALSE

Any relation in BCNF must be in 3NF.

Option 2: FALSE

A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on every key of R but this does not guarantee transitive dependency.

Option 3: TRUE

Every relation is BCNF must be in 3NF.

Option 4: FALSE

Any relation can be in both BCNF & 3NF if it satisfies the condition of BCNF.

Hence, the correct answer is “option 3”.

The correct answer is "option 3".

CONCEPT:

The expression in switch condition is evaluated once and compared with values of each case value.

Also, the break statement is used to move the control out of the switch case after matching case statements gets executed.

If there is no match, then the default clause is used.

The default clause is optional

EXPLANATION:

char inChar = ‘A’ ; 

<br>

// inChar variable having char datatype is initialized with value “A”.

switch ( inChar )   // switch condition is compared

 

case ‘A’: printf("Choice A\n"); 

<br>

// the case value is matched & statement gets executed but since there is no break it will move to case value B

 

case 'B':                                     

<br>

//no statement & no break so it will move to case value C

case ‘C’: printf ("Choice B");         

<br>

// print given statement & since no break so it will move to case value D

case 'D':                                 

<br>

 //no statement & no break so it will move to case value E

case 'E':                               

         

//no statement & no break so it will move to the default case

default: printf ( "No Choice" ) ; }     

<br>

// print the statement and move out of the switch case.

So the output will be:

Choice A

Choice B No Choice

Hence the correct answer is "option 3".

The correct answer is option 2

CONCEPT:

From Diagram: NP-complete ⋂ P = ϕ

NP-complete problems:

They are those for which no polynomial-time algorithm exists. We can say a problem is NP-complete if it is NP and belongs to NP-hard.

NP problems:

A problem is a member of the NP class if there exists a non-deterministic machine that can solve it in polynomial time.

NP-Hard:

A problem is called NP-hard if all the NP class problems are polynomial-time reducible to that and as hard as any problem of NP class

EXPLANATION:

• Every problem in P is also in NP
• Given that P ≠ NP, this means there exists a problem that is in NP but not in P

So the option NP-complete ∩ P = Φ is correct

The correct answer is "option 3".

CONCEPT:

There are three types of complexities:

1. Worst case: It is the maximum running time taken by any algorithm. 
2. Average case: It is the average running time taken by any algorithm. 
3. Best case: It is the minimum running time taken by any algorithm. 

EXPLANATION:

Since the worst-case running time to search ‘n’ elements in a balanced Binary Search Tree (BST) is (log₂n).

If the number of elements is (n2ⁿ) then,

Search time will be: T(n) = (log₂n.2ⁿ)

Since log₂(A.B) = log₂A + log₂B

∴T(n) =log₂n + log₂2ⁿ

∴T(n)  = log₂n + n.log22 = log2n + n

T(n) = O(n)

Hence the correct answer is "option 3".

The correct answer is "option 1".

EXPLANATION:

Option 1: TRUE

The truth table X is**:**

 

F is equal to X.

Option 2: FALSE

The truth table X+Y is**:**

F is not equal to X+Y.

Option 3: FALSE

The truth table X’Y + XY' is**:**

F is not equal to X’.Y +X.Y'.

Option 4: FALSE

The truth table Y is :

 F is not equal to Y.

Hence, the correct answer is "option 1".

From truth table, the sum of minterms

F(X, Y) = X.Y̅ + X.Y = X(Y̅ + Y) = X

The correct answer is option 2:

Concept:

32-bit floating-point representation of a binary number in IEEE- 754 is

In IEEE-754 format, 32-bit (single precision)

Decimal value = (-1)s × 1.M × 2E – 127

Option 2: Correct

If E = 126 then exponent part = 126 - 127 = -1

Fraction part = M = 0

Since 0.5 is positive and hence S = 0

Decimal value = (-1)s × 1.M × 2E – 127 

Decimal value = (-1)⁰ × 1.0 × 2126 – 127 = 0.5

The correct answer is option 3.

Concept:

Fork () is a system call that creates a new process. After a new child process is created, both processes will execute the next instruction. If fork() returns a negative value, the creation of the child process was unsuccessful. Return zero to the newly created process.

Explanation:

If there are n fork() calls, then the number of child processes created is 2n – 1.

Calculation:

n = 3,

Number of child processes created = 23 – 1 = 7​

The correct answer is option 2

CONCEPT:

y = f(x)

x ∈ [a,e]

f(a) is local minima

f(c) is local maxima

f(d) is local minima

f(e) is local maxima

Absolute max OR global max OR greatest value = max(f(c),f(e)) =f(e)

Absolute min OR global min OR least value = max(f(a),f(d)) =f(d)

EXPLANATION:

Graph of sin(x)

So local minima One, at 3π/2 in the interval x ∈ [π/4, 7π/4].

The correct answer is option 3

CONCEPT

PDU for the application layer is messages.

Additional Information

• A protocol data unit (PDU) is a single unit of information transmitted among peer entities of a computer network.
• PDU for the physical layer is bits.
• PDU for the data link layer is a frame.
• PDU for the network layer is packets.
• PDU for the transport layer is a segment.

The correct answer is "option 4".

CONCEPT:

According to Cayley Hamilton theorem:

If matrix A has Eigenvalue ‘x’ then An has Eigenvalue as xn.

DATA:

According to the given values,

a₁₁ = a₁₂ = a₂₁ = 1, a₂₂ = -1

The 2 x 2 matrix will be: $A = \left[ \begin{matrix} 1 & 1 \ 1 & -1 \ \end{matrix} \right]$

CALCULATION:

Considering characteristic equation is |A - λ I| = 0

where λ is eigen value and I is identity matrix

∴ Characteristics equation is given by

\(\left| \begin{array}{*{35}{r}} 1-\lambda & 1 \ 1 & -1-\lambda \ \end{array} \right|=0\)

Solving the matrix,

−(1 − λ).(1 + λ) − 1 = 0

−(1 − λ2) – 1 = 0

− 2 + λ2 = 0

λ2 = 2

λ = ±(2)1/2

Therefore the Eigen values are:

((2)^1/2)¹⁹= 2⁹ x (2)^1/2 = 512√2

((-2)1/2)19= (−1)⁹  x 29 x (2)1/2 = −512√2

Hence the correct answer is "option 4".

The correct answer is "option 2".

EXPLANATION:

NFA is:

Consider, ∑ = {a} and ϵ is the empty string

The ∑ = {a} and the NFA accept the following strings:

{a, aa, aaa, aaaa,……}

That means, the language accepted by the regular expression is {a⁺}

Therefore, the complement of the language is:

= {a* - a⁺}

= ϵ

Hence, the correct answer is "option 2".

The correct answer is option 3.

STATEMENT:

“Some real numbers are rational”

Option 1: Incorrect

There exist some numbers which are either real OR rational

Option 2: Incorrect

All real numbers are rational

Option 3: Correct

There exist some numbers which are both real and rational

Option 4: Incorrect

There exists a number such that if it is rational, it is real​

The correct answer is "option 3".

EXPLANATION:

Option 1: CORRECT

In the Entity-Relationship model or ER model, the Multi-valued attributes of any entity can have one or more attribute values.

In a single-valued attribute, any entity can only have a single attribute value.

Option 2: CORRECT

In ER model, the attribute which can be further broken down into more attribute values is known as the “composite attribute”.

So, an attribute of an entity can be composite.

Option 3: INCORRECT

In the Entity-Relationship model or ER model, the Multi-valued attributes of any entity can have one or more attribute values.

An attribute can have multiple attribute values but not in a row of relational tables.

In a relational table, rows must contain atomic values.

Option 4: CORRECT

In the Relational model, the values of the intersection of one row & column should contain either:

1. Exactly one value or
2. Null value.

Hence the correct answer is “option 3”.

The correct answer is option 3

EXPLANATION:

GROUP BY clause:

• The GROUP BY statement groups rows that have the same values into summary rows, like "find the number of customers in each country".
• The GROUP BY statement is often used with aggregate functions (COUNT, MAX, MIN, SUM, AVG) to group the result-set by one or more columns.

Syntax:

SELECT column_name(s)

FROM table_name

WHERE condition

GROUP BY column_name(s)

Example:

SELECT COMPANY, COUNT(*)  

FROM PRODUCT_MAST   

GROUP BY COMPANY 

Therefore all attributes used in the GROUP BY clause must appear in the SELECT clause 

HAVING clause:

• HAVING clause is used to specify a search condition for a group or an aggregate.
• Having is used in a GROUP BY clause.
• If you are not using GROUP BY clause then you can use HAVING function like a WHERE clause.

Syntax:

SELECT column1, column2   

FROM table_name  

WHERE conditions   

GROUP BY column1, column2   

HAVING conditions  

ORDER BY column1, column2;  

 

Example:

SELECT COMPANY, COUNT(*)  

FROM PRODUCT_MAST   

GROUP BY COMPANY  

HAVING COUNT(*)>2; 

Therefore an SQL query can contain a HAVING clause only if it has a GROUP BY clause.

Confusion Points

The answer is as per standard SQL

The correct answer is option 4

Concept

Rule Of Towers of Hanoi problem:

Tower of Hanoi is a mathematical puzzle where we have three poles and n disks. The main goal in the puzzle is to move the entire stack to another pol, obeying the following simple rules: 

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

Solution Of Towers of Hanoi problem:

Begin with n disks on pole one

1. We can transfer top n-1 disks from pole1 to pole3 using T(n-1) moves
2. We keep the largest disk fixed during these moves
3. Then, we use one move to transfer the largest disk to the second pole.
4. We can transfer top n-1 disks on pol3 to pol2 using T(n-1) additional moves, placing them on top of the largest disk, which always stays on the bottom of pol2

Moreover, it is easy to say that the puzzle can not be solved using fewer steps. This shows that

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with ṅ discs is

T(n) = 2T(n − 1) + 1

Example:

Follow the above algorithm to solve the problem of the Tower of Hanoi

here we have three-pole and also have three disks

 

The correct answer is "option 4".

CONCEPT:

A planar graph is a graph that can be drawn on the plane in such a way that its edges must intersect only at their endpoints.

In a planar graph, the graph is drawn in such a way that no edges must cross each other.

The graph whose edges overlap or cross each other is known as a Non-planar graph.

A graph to be planar must satisfy the following Euler’s formula:

v - e + f = 2

where

v is the number of vertices

e is the number of edges

f is the number of faces 

CALCULATION

v = 10, e = 15

According to Euler’s formula:

v - e + f = 2 

10 – 15 + f = 2

f = 2 – 10 + 15

f = 7

Out of 7, there will be always one unbounded face.

So, the number of faces is 6.

Hence, the correct answer is "option 4".

The correct answer is "option 3".

CONCEPT:

There are three types of complexities:

1. Worst case: It is the maximum running time taken by any algorithm. 
2. Average case: It is the average running time taken by any algorithm. 
3. Best case: It is the minimum running time taken by any algorithm. 

EXPLANATION:

The average case time can be equal to or lesser than the worst case.

So, A(n) would be the upper bound case by W(n).

Also, it will not be a strict upper bound as it can be the same as an average case like Merge sort.

Therefore,

A(n) = O(W(n))

Hence the correct answer is "option 3".

The correct answer is option 4

Explanation:

A ROM cannot be written and implement with the 4-bit multiplier, so we must store all possible combinations of 2⁴ × 2⁴ inputs and their corresponding output bits giving a total of 24 × 24 × 8 bits, that is 2 Kbits.

So, the amount of ROM needed to implement a 4-bit multiplier is 2 Kbits.

Let's take an example of two 4 bit number multiplication

Let ${\rm{A}} = {\rm{;}}{{\rm{a}}_3}{{\rm{a}}_2}{{\rm{a}}_1}{{\rm{a}}_0}$

${\rm{B}} = {{\rm{b}}_3}{{\rm{b}}_2}{{\rm{b}}_1}{{\rm{b}}_0}$

Then

Additional Information

Multiplication of two n bit number will result in data = (2n) bits

Multiplication of two n bit number needs 2n address lines

Size of ROM = 22n × 2n bits

n = 4

Size of ROM = 22×4 × 2(4) bits

Size of ROM = 211 bits

Size of ROM = 2Kbits

  

G → Giga, M → mega, K → kilo

1 G = 230

1 M = 220

1 K = 210

• Register renaming technique is used to eliminate false data dependencies arising from the reuse of registers by successive instructions that do not have any real data dependencies between them.
• The elimination of these false data dependencies reveals more instruction-level parallelism in an instruction stream, which can be exploited by various and complementary techniques such as superscalar and out-of-order execution for better performance.
• Register renaming is done in pipelined processors to eliminate WAR/WAW hazards.

Important Points:

WAR → write after read

WAW → write after write

The correct answer is option 3

Concept:

Cumulative Distribution Function

If f(x) is the probability density function and F(X) is the cumulative distribution function then the relation between both of them is:

F(X) = P[X ≤ x] = \(\mathop \smallint \nolimits_{ - \infty }^x f\left( x \right)dx\) = sum of all values less than equal to x.

Explanation:

Given that P(-1) =0.5 and P(1) =0.5. So, at all other points, p must be zero as the sum of all probabilities must be 1.

F(X) is the cumulative distribution function and let P is the probability and given X is random variable, So

F(X) = P[X ≤ x]

F(-1)=P(X <= -1)

        = P(x = -1)

        =0.5

and F(1)=P(X <= 1)

              =P(x = -1) + P(x = 1)

              =0.5 + 0.5

             =1

So, the correct answer is option 3

SMTP

• Simple Mail Transfer Protocol (SMTP) is the standard protocol for sending emails across the Internet. Therefore, SMTP transfers messages from the sender’s mail servers to the recipient’s mail server.

Additional Information

TCP:

TCP is the transfer layer protocol. Electronic mail function is supported by the transfer layer protocol TCP. TCP is a connection-oriented and reliable transport protocol. Therefore, SMTP transfer messages from the sender’s mail servers to the recipient’s mail servers using TCP

UDP:

• UDP is an unreliable connectionless-transport layer Protocol used for its simplicity and efficiency in applications where error can be provided by the application layer
• UDP provided process-to-process communication

IPv4 address: 32 bits

IP address = Network ID + Host ID

Network ID + Host ID =32

PREFIX is the part of the Network ID

The correct answer is option 4

CONCEPT:

Decidable language: A language is decidable if there exists a Turing machine which halts or accepts it.

EXPLANATION:

1: Undecidable

There is no TM to determine whether a given program will produce an output.

2: Undecidable

Context-free languages are not closed under complementation.

3: Decidable

Regular languages are closed under complementation.

4: Decidable

Recursive languages are closed under complementation.

So option 4 is correct

The correct answer is option 3.

Key Points

Option 1: abaabaaabaa

               The combination of {ab,aa, baa} forms abaabaaabaa. And this is correct combination.

               "ab aa baa ab aa"

Option 2: aaaabaaaa

               The combination of {ab,baa} forms aaaabaaaa. And this is correct combination.

               “aa aa baa aa”

Option 3: baaaaabaaaab

                This is not a correct combination of {ab,aa,baa}. Ending with 'b' can not get from given strings.

               "baa aa ab aa aab"

Option 4: baaaaabaa

               The combination of {ab,aa, baa} forms baaaaabaa. And this is the correct combination.

               "baa aa ab aa"

Hence the correct answer is 1, 2 and 4.

The correct answer is "option 2".

EXPLANATION:

The original graph is:

Option 1: Not an Isomorphic

The original graph doesn’t contain 3 cycle sub-graph but this graph contains.

So this is not an isomorphic graph.

Option 2: An Isomorphic

This graph contains a 5 cycle graph as in the original graph and the max degree of this graph is 4.

 So, this is an isomorphic graph.

Option 3: Not an Isomorphic

The original graph doesn’t contain a node having degree 3 but this graph contains.

So this is not an isomorphic graph.

Option 4: Not an Isomorphic

The original graph doesn’t contain 4 cycle sub-graph but this graph contains.

So this is not an isomorphic graph.

The correct answer is option 2.

Key Points

P and Q are initialized to Zero, write operation on P and Q will be executed.

Consider any non-serial schedule like R1(P), R2(Q), R1(Q), R2(P), W1(Q), W2(P). R1(P) conflicts with W2(P) Hence T1 must be before T2. R2(Q) conflicts with W1(Q) Hence T2 must be before T1. There is no serial schedule that satisfies both of them hence it does not conflict with serializable.

Hence the correct answer is a schedule that is not conflict serializable.

Concept:

Bisection method:

Used to find the root for a function. Root of a function f(x) = a such that f(a)= 0

Property: if a function f(x) is continuous on the interval [a…b] and sign of f(a) ≠  sign of f(b). There is a value c belongs to [a…b] such that f(c) = 0, means c is a root in between [a….b]

Note:

Bisection method cut the interval into 2 halves and check which half contains a root of the equation.

1. Suppose interval [a…b] .

2. Cut interval in the middle to find m : $m =\frac{{a+b}}{{2}}$

3. sign of f(m) not matches with f(a) proceed the search in the new interval.

Calculation:

The bisection method is applied to a given problem with [1, 9]

After 1 iteration

${x_1} = \frac{{1; + ;9}}{2} = 5$

Now since f(x₁) > 0, x₂ replaces x₁

Now, x₀ = 1 and x₁ = 5

And after 2^nd iteration 

${x_2} = \frac{{1; + ;5}}{2} = 3$

Now since f(x₁) f(x₂) > 0, x₂ replaces x₁ and x₀ = 1 and x₁ = 3 and after 3^rd iteration

${x_2} = \frac{{1; + ;3}}{2} = 2$

Now, f(x₂) = f(2) = 2⁴ – 2³ – 2² – 4 = 0

So the method converges exactly to the root in 3 iterations.

The correct answer is “option 4”.

CONCEPT:

A spanning tree of graph G is a subset of G which has all vertices covered with the minimum possible number of edges.

Some properties of spanning tree are:

1. Spanning tree doesn’t contain any cycle.
2. Spanning tree cannot be disconnected.

Every connected and undirected graph G has at least one spanning tree.

EXPLANATION:

Consider graph G with edge weights > 1,

Consider graph G’ with squared edge weights of graph G,

The minimum spanning tree (T) of graph G is:

Minimum Spanning Tree (T’) of graph G’ is:

So, T is not equal to T'and t' < t².

Hence, the correct answer is "option 4".

The correct answer is “option 2”.

CONCEPT:

Karnaugh Map is used to simplify Boolean algebra expressions.

It is a graphical technique of simplifying Boolean expressions.

It is also known as K-map.

K-map contains two types of methods:

1. SOP (Sum Of Product): This produces logical expressions that contain OR of multiple AND terms.

Example: b̅.d̅ + d̅.c̅ 

2. POS (Product Of Sum): This produces logical expressions that contain AND of multiple OR terms.

Example: (b̅ + d̅)(d̅ + c̅)

EXPLANATION:

The first quad will form from the K-map:

(ab – 00, 10, cd – 00,10)

Value is: b̅.d̅ 

The second quad will form from the K-map:

(ab – 00, 10, cd – 00,01)

Value is c̅.b̅

So, the minimal form of the given K-map is b̅.d̅ + c̅.b̅**.**

Hence, the correct answer is "option 2".

Correct Explanation for FCFS and RR2 Scheduling

🔹 Given:

🔸 FCFS (First Come First Serve)

• P1 arrives at time 0 → executed first → finishes at time 5
• P2 arrives at time 1 → executed next → finishes at time 5 + 7 = 12
• P3 arrives at time 3 → executed last → finishes at time 12 + 4 = 16

✅ FCFS Completion Order: P1, P2, P3

🔸 RR2 (Round Robin with Time Quantum = 2)

• Time 0–2: P1 executes → remaining = 3
• Time 2–4: P2 executes → remaining = 5
• Time 4–6: P3 executes → remaining = 2
• Time 6–8: P1 executes → remaining = 1
• Time 8–10: P2 executes → remaining = 3
• Time 10–12: P3 executes → completes ✅
• Time 12–13: P1 executes → completes ✅
• Time 13–15: P2 executes → remaining = 1
• Time 15–16: P2 executes → completes ✅

✅ RR2 Completion Order: P3, P1, P2

📌 Summary

✔️ Final Answer: FCFS: P1, P2, P3    RR2: P3, P1, P2

The correct answer is option 2

CONCEPT:

M=Fetch_And_Add(X, I) //return previous value of i

if X=10 and i=2

then X=X+2 =10+2 =12

M=2 // because return previous value of i is 2

EXPLANATION:

AcquireLock(L){

1. while (Fetch_And_Add(L,1)) //if Fetch_And_Add(L,1) return 0 then go to CS otherwise going into loop 2.   L = 1;

}

ReleaseLock(L){

3.        L = 0;

}

Option 1: TRUE

<br>

Let's take 4-bit register

if n=15

Here overflow occurs and L becomes zero so it fails

Option 2: TRUE

1,2,3 shows the execution of line number

when P0 execute line number 3 then L=0 and lock is available but P1 fall into an infinite loop

So, fails as L can take on a non-zero value when the lock is actually available

Confusion Points

Option 1 is also the correct answer and the given answer is as per the official answer key, that is, option 2

The correct answer is "option 2".

EXPLANATION:

Value on the die for the first time:

{1, 2, 3}                                  

Value on the die for the second time:

{1, 2, 3, 4, 5, 6}

Therefore, values are:

 

Sample space = 36

The sum must be at least 6 so,

Values of dice are: (1,5), (1,6), (2,4), (2,5), (2,6), (3,3), (3,4), (3,5), (3,6)

So, 9/36 is the probability of getting 6 when both dices are thrown.

If the value of dice comes to 6 in the first dice then there is no need to roll it again.

Prob. of getting 6 is: 1/6

Total probability = 1/6 + 9/36

                               = 5/12

Hence, the correct answer is “option 2”.

The correct answer is Option 1.

Key Points

 

Since Half of 4096 post addresses must be given organization A, we can set the 12^th bit to 1, include that bit into the network path of organization A. So the valid allocation of address to A is 245.248.136.0/21.

The 12^th bit is set to 0, but we need only half of the 2048 address, 13^th bit can be set to be 0 addresses to B is 245.248.128.0/22.

Hence the correct answer is 245.248.136.0/21 and 245.248.128.0/22.

The correct answer is "option 1".

CONCEPT:

A circular queue is a queue whose last position is connected back to the first position.

ENQUEUE – It is the operation to insert elements into the queue.

DEQUEUE – It is the operation to delete elements from the queue.

After inserting an element in the last position, the next element again gets inserted into the first position.

EXPLANATION:

Given, Rear = Front = 0

Here, the Rear is used to insert elements & the front is used to delete elements.

To check full condition in queue:

(Rear + 1) % n == Front

Example: Consider queue is full that means Rear = 6, front = 0, n = 7

(6+1) % 7 = 7 % 7 = 0

To check empty condition in queue:

Rear == Front

Example: Consider queue is empty that means Rear = 0, front = 0, n = 7

Rear = Front = 0

Hence, the correct answer is “option 1”.

The correct answer is “option 4”.

The access link is a pointer to the activation record.

A direct implementation of the normal static scope rule for a nested function is obtained by adding a pointer called access link to each activation record.

Consider any procedure P, if P is nested immediately within procedure Q in any code, then access link in any activation of P points to the most recent activation of Q.

EXPLANATION:

Main →  A1 → A2 → A21 → A1

Activation records are created at procedure exit time.

Since A1 & A2 are defined under Main ().

A1 & A2 access links are pointed to the main function.

A21 is defined under A2, so its access link will point to A2.

Hence, the correct answer is “option 4”.

The correct answer is “option 3”.

CONCEPT:

An Onto function is such a function that for every element in the codomain, there exists an element in the domain that maps to it.

A function f from A to B is known as Onto function if**:**

For all 'b' in B, there is an 'a' in A such that f(a) = b.

In other words, all elements of B are used.                   

The onto function is:

The non-onto function is:

Here, value 3 is not used.

CALCULATION:

Consider number of elements in m & n respectively.

Number of onto functions possible is:

n^m – ⁿC1(n-1)^m + ⁿC2(n-2)^m +……

Here, m = n, n= 2

= 2ⁿ – ²C1(2-1)ⁿ + ²C2(2-2)ⁿ

= 2ⁿ – 2×1 + 0

= 2ⁿ – 2 

Hence, the correct answer is “option 3”.

The correct answer is “option 3”.

CONCEPT:

A graph that contains an edge between every pair of vertices is known as a complete graph.

A complete graph with 6 vertices is:

EXPLANATION:

To get a cycle to length 4, edges of length 4 can be selected to form a cycle.

To get the cycle of length 4, select any 4 vertices.

The number of selection of 4 vertices out of 6 vertices is: ⁶C₄ i.e. 15

Example:

Consider 4 vertices {a, b, c, d}, total cycles using 4 vertices are:

a-b-c-d, a-b-d-c, a-c-b-d, a-c-d-b, a-d-b-c, a-d-c-b

Therefore, number of cycle using n vertices is (n-1)!

But number of distinct cycles of length 4 with vertices (a,b,c,d) is 3.

{Since abcd and adcb are same, in different directions}

So, the total number of distinct cycles of length 4 is:

= 15 × 3

= 45

Hence, the correct answer is "option 3".

The correct answer is "option 2".

CONCEPT:

The Recurrence relation for the number of comparisons needed to sort an array of n integers is:

T(n) = 2T(n/2) + n

= O(nlog₂n)

EXPLANATION:

Consider n strings of length n in place of each integer, since each integer takes O(1) time to sort then,

Complexity to sort one string of size n - O(n)

Complexity to sort n strings of size n - O(n * nlog₂n) = O(n²log₂n)

Hence, worst case running time is O(n2log2n).

The correct answer is “option 4”.

CONCEPT:

Dijkstra’s algorithm is an algorithm used for finding the shortest paths between nodes or vertices in a graph.

 This algorithm is basically used to find the shortest path from a starting node to a target node in a weighted graph.

This algorithm creates a tree of the shortest path from a vertex to other nodes in the graph.

This algorithm assigns initial distance values & will try to improve step by step.

Dijkstra’s algorithm works as follows**:**

1. It initializes distances according to the algorithm.
2. Pick a node and calculate the distance to adjacent nodes.
3. Pick the next node with the smallest distance & repeat distance calculations.
4. Find the result of the shortest-path tree.

CALCULATION:

The shortest-path tree is:

Hence, the shortest path from S to T is S → A → C → E → T.

The correct answer is option 2

DATA:

In the index node of a Unix- style file system,

Direct Block pointer = 8

Single Indirect Block pointer = 1

Double Indirect Block pointer = 1

Disk block address = disk block entries size = 8 B

Disk Block size = 128 B

CALCULATION:

Number of entries in a block = $\frac{disk; block; size}{disk; block; address; size} = \frac{128; B}{8;B}$ = 24

File size = (8 direct + 1 singel indirect + 1 double indirect) × Block size

File size = (8 × 1 + 1 × 24 + 1 × 24 × 24 ) × 128 B

File size = (210 B + 211 B + 215 B )

File size = (1 + 2 + 32)KB

∴ The maximum size of file is 35 KB or 35 KBytes

The correct answer is Option 2.

Concept:

First In First Out (FIFO):

In this algorithm, the operating system keeps track of all pages in the memory in a queue. The oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

Optimal Page replacement:

In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.

Least Recently Used :

In this algorithm, the page will be replaced which is least recently used.

Solution: 

First In First Out (FIFO):

The given virtual page reference string is 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 and the main memory size is 3-page frames.

Total number of page faults= 6

Optimal Page replacement:

Total number of page faults= 5

Least Recently Used :

Total number of page faults= 9

The number of page faults with OPTIMAL, FIFO, LRU (5,6,9) is OPTIMAL < FIFO < LRU.

The correct answer is option 1

Concept:

Referential integrity constraints

• In a relational database, a referential integrity constraint is specified between two tables with the help of a foreign key.
• In the Referential integrity constraints, if a foreign key in Table 1 refers to the Primary Key of Table 2, then every value of the Foreign Key in Table 1 must be null or be available in Table 2.

B is a foreign key of R1 that refers to C(primary key) in R2, B must be null or to be available in R2

r2(C) is a superset of r1(B)

So {subset - Superset} =Φ

So the correct answer is ΠB(r1) - ΠC(r2) = Φ

Additional Information

functional dependency: Dependency of attributes in relations

Foreign key

• A foreign key means that values in one table must also appear in another table. T
• he referenced table is called the parent table while the table with the foreign key is called the child table.
• The foreign key in the child table will generally reference a primary key in the parent table.

Primary key

• A primary key is a specific choice of a minimal set of attributes (columns) that uniquely specify a tuple (row) in a relation (table). Primary key cannot accept null values and there can be only one primary key constraint for one table.

The correct answer is option 1

Data:

Number of packets = n =1000

Size of each Packet = L = 1000 bits

The link bandwidth on each link is = BW = 1Mbps =10⁶ bits/s

Each link be of length = d= 100 km

Signals travel over each link at a speed = v= 108m/s

Transmission delay = T

Propagation delay = P

Formula:

$T = \frac{L}{{BW}}$

$P = \frac{d}{v}$

Calculation:

Propagation delay for the first packet to transmit S to R1

$P = \frac{{100×10^3}}{{ {{10}^8}}} = {1\times10^{ - 3}};s = 1;ms$

So, the propagation delay for the first packet to transmit S to D

P =1 × 3=3ms

Transmission delay for the first packet to transmit S to R1

$T = \frac{{1000}}{{{{1\times10}^6}}} = 1 × {10^{ - 3}};s = 1;ms;$

So, the transmission delay for the first packet to transmit S to D

T=1 × 3=3ms

So, total time is taken to transmit the first packet from S to D =P +T=6ms

Using pipelining, the remaining packet follows the first packet

then remaining every packet take 1ms to transmit from S to D

So, the total time is taken to transmit all 1000 packets from S to D is

⇒ time for the first packet + time for the remaining 999 packets

⇒ 6ms + 999ms

⇒ 1005ms

So, the total time is taken to transmit all 1000 packets from S to D is 1005ms.

The correct answer is option 3

EXPLANATION:

Initial window size or window size for first transmission: cwnd = 2 MSS

For 2nd transmission → cwnd = 22 = 4 MSS

For 3rd transmission → cwnd = 23 = 8 MSS

When threshold is reached then additive increase

For 4th transmission → cwnd = 8 + 1 = 9 MSS

For 5th transmission → cwnd = 9+ 1 = 10 MSS(fails)

Now window size reduced to 10/2 =5 MSS

For 6th transmission → cwnd = 1 MSS

For 7rd transmission → cwnd = 21 = 2 MSS

For 8th transmission → cwnd = 22 = 4 MSS

Thersoled reached now additive increase

For 9th transmission → cwnd = 4 + 1 = 5 MSS

For 10th transmission → cwnd = 5 + 1 =6 MSS

So, at the end of 10th successful transmission 

The congestion window size will be  6 + 1 = 7 MSS

The correct answer is option 4.

Key Points

 L={All the strings of 0's and 1's where every substring of 3 symbols has at most 2 zero's }

Case 1: If we go with option 1.

If we take the substring 0000, it has a substring 000 containing more than 2 zero's so it is an invalid string but it is accepted by DFA. Hence this option is not possible.

Case 2: If we go with option 2.

W=000 is a string and has a substring 000 having more than 2 zeros. Not in a language but it is accepted. So option 2 is not possible.

Case 3: If we go with option 3.

W=001000 has a substring 000 having more than 2 zeros and accepted but it is not in the given language.

Case 4: If we go with option4.

This machine accepts all the strings that were every substring of 3 symbols has at most 2 zeros.

So the correct answer is option 4.

The correct answer is option 1

EXPLANATION:

The box B1 gets executed when left subtree of n is NULL and right subtree is not NULL. So, height of n will be height of right subtree plus one.

The box B2 gets executed when both left and right subtrees of n are not NULL. So, height of n will be max of heights of left and right subtrees of n plus 1.

So, the correct answer is 

B1: (1+height(n → right))

B2: (1+max(h1, h2))

EXAMPLE:

Find the height of this tree using option 1 in the program

int height (treeptr n)

{ if (n == NULL) return -1;

  if (n →  left == NULL)

       if (n →  right == NULL) return 0;

       else return (1+height(n → right)) ;     // Box 1

else { h1 = height (n →  left);

         if (n → right == NULL) return (1+h1);

         else { h2 = height (n → right);

         return (1+max(h1, h2)) ; // Box 2

                       }

           }

}

So, the height of the above tree is 3

The correct answer is option 3.

Key Points

 If the variables are static then, it is persisting previous state value from the destruction of various function calls. The variable 'a' in prtFun() is static, i.e its lifetime is global and hence retains its value always, meaning history sensitive.

Hence the correct answer is 4     2,  6     2,  2     0.

The correct answer is option 4.

Key Points

If the variable is auto, these variables will be reinitialized in every function calls. Now the variables are all auto storage classes. Their lifetime is local.

Hence correct answer is  4     2, 4     2, 2     0.

The correct answer is option 1.

Key Points

 Apply first cross-product then apply filter. Cross product yields 10 rows, then you play filter A.ID>40 or C.ID<15 produces 7 rows.

AUB= A.Id

12,15,25,98,99

|x| is cross product followed selection and projection.

Hence the correct answer is 7.

The correct answer is option 2.

Key Points

The ALL keyword specifies that the search condition is TRUE if the comparison is TRUE for every value that the subquery returns. If the subquery returns no value, the condition is TRUE.

There is no Name='Arun' in the B table. So it returns no value then the condition become is TRUE for every row. So Finally it prints the ID of the A table.

Hence the correct answer is 3.

The correct answer is option 1

EXPLANATION:

FIRST(A) = FIRST(s) ={a, b, ε}

FIRST(B) = FIRST(s) ={a, b, ε}

So,FIRST(A) = {a, b, ε} = FIRST(B)

FOLLOW(A) = {First of { bB}, FIRST of {aB}}

FOLLOW(A) = {a, b}

FOLLOW(B) = FOLLOW(S) ={FOLLOW(A), $}

FOLLOW(B) = FOLLOW(S) ={FOLLOW(A), $} ={a, b,$}

Now, the answer is

FIRST(A) = {a, b, ε} = FIRST(B)

FOLLOW(A) = {a, b}

FOLLOW(B) = {a, b, $}

The correct answer is option 3

EXPLANATION:

FIRST and FOLLOW:

 

Parsing Table:

 

Hence the answer is

E1: S → aAbB, S → ε

E2: S → bAaB, S → ε

E3: B → S

The correct answer is option 3

Data:

Physical address (PA) = 2³² bytes

Block size = 32 B = 25 B

Number of bits for block size = 5

cache size =256 KByte = 2¹⁸ B

set associative = 4 -way 

Calculation:

number of bits = ⌈log2 n⌉ 

Number of blocks = $\frac{cache;size}{block; size}$ =${2^{18} B\over 2^5B}=2^{13}$

Number of sets in cache = ${\frac{number; of; blocks}{set; associativity}} = {2^{13}\over 2^2}=2^{11}$

Number of bits in set =11

PA = tag + set + offset

32 = tag + 11+ 5

∴ tag = 16 bits

So, the number of bits in the tag field of an address is 16 bits

The correct answer is option 1

Data:

Physical address space = 2³² bytes

Block size = 32 B = 25 B

Number of bits for block size = 5

cache size =256 KByte = 218 B

set associative = 4 -way 

Calculation:

number of bits = ⌈log2 n⌉ 

Number of blocks = $\frac{cache;size}{block; size}$ =${2^{18} B\over 2^5B}=2^{13}$

Number of sets in cache = ${\frac{number; of; blocks}{set; associativity}} = {2^{13}\over 2^2}=2^{11}$

Number of bits in set =11

Virtual address = tag + set + Byte offset (in bits)

32 = tag + 11+ 5

∴ tag = 16 bits

16 bit address 2 valid bits, 1 modified bit and 1 replacement bit

So, total bits =20

So, Each cache tag directory entry contains = 20 × Number of blocks = 20 × 2¹³ bits

∴ 213 = 8 K bits

So, Each cache tag directory entry contains = 20 × 8 K bits=160 Kbits

So, the size of the cache tag directory is 160 Kbits