GATE CS 2015 Official Paper: Shift 1 (Previous Year Paper)

The correct determiner to fit the given blank should be ‘any’. This is because it is used to refer to one or some of a thing or number of things, no matter how much or how many.

‘No paper’ would make the construction of the sentence a double negative since ‘didn’t’ has been used. 

'Much’ is used for uncountable nouns and hence, cannot be used for an object like paper.

‘A few paper’ is also grammatically incorrect since the correct way to use this determiner would be to say "a few sheets of paper".

Hence, option 1 is correct.

The given sentence uses the word 'enjoy' which has a positive connotation and is followed by the adverb ‘immensely’, which means to a large extent.

All of the options except option 3 use adjectives with negative connotations - terrible, horrible, terrifying - to describe the subject's experience and and are hence, incorrect.

Option 3 uses the word 'terrific' which has a positive connotation and is hence accurate.

Hence, option 3 is correct.

The combinations of words in all options except B are synonyms of each other.

‘Wheedle’ means to use flattery to obtain something and ‘roundabout’ means not following a direct route. Thus, these two words are unrelated and do not form a synonymous combination.

Hence, the right answer is option 2.

Distance between two floors of building = 9 feet

Height of each step = 3/4 (Statement I)

Width of each step = 1 (Statement II)

Using the data give in statement I, we may calculate the number of steps in a set of stairs as

\(n = \frac{9}{3} \times 4 = 12;step\)

So, statement I is sufficient to give the answer.

However, there is no use of width given in statement II to calculate number of required steps in set of stairs. So, width of foot can be anything, and it is not sufficient to obtain the number of steps.

Thus, statement I alone is sufficient, but statement II alone is not sufficient.

Total number of possibilities \(= 4 \times 5 = 20\)

Number of possibilities that the sum of two numbers equals 16 = 4

And they are \(= \left{ {\left( {2,14} \right),;\left( {3,13} \right),;\left( {4,12} \right),;\left( {5,11} \right)} \right}\)

Probability \(= \frac{4}{{20}} = 0.2\)

The phrase ‘take to one's heels’ means 'to start running in order to escape'. Out of the given options, this meaning is best expressed by the phrase ‘took to flight’, which means the same thing.

Hence, option 3 is correct.

Explanation:

• The fall in the drop of water levels in the lakes has to be tackled by both courses of actions I and II in order to supply adequate water to the city. There has to be a partial decrease in the water supply by the government so that everyone is supplied with water and nobody faces a total water cut.  Also, the citizens must be made aware of the situation and they should be encouraged to make responsible and minimal use of water in order to conserve it. A total ban on the water supply is illogical since water is a necessity for everyone and thus the third course of action does not follow.

Answer: 32 to 32 

Explanation: 

From the pie-chart, we have 

The proportion of male to female students in each department is 5:4. ( male ratio = 5/9 and female ratio = 4/9)

Hence 40 males in Electrical Department, So total students in Electrical Department = 40 *(9/5) = 72 

Total electrical student percentage = 20%

Hence Total number of students in college = (72/20)*100 = 360

Hence number of females in Mechanical Department = 0.1(4/9)(360)** = 16

and number of females in Civil Department = 0.3(4/9)360 = 48

Hence the Difference = 48-16 = 32

Probability of non-pass = 1 - Probability of at least one pass

=1 - 0.75 = 0.25

(1 - m) (1 - p) (1 - c) = 0.25

(1 + mp - m - p) (1 - c) = 0.25

1 + mp - m - p - c - mpc + mc + pc = 0.25

m + p + c - mp - pc - mc + mpc = 0.75 -------Eq(1)

Probability of exactly 2 pass = 0.4

mp(1- c) + pc(1 - m) + mc(1 - p) = 0.4

mp + pc + mc - 3mpc = 0.4

mp + pc + mc - 2mpc = 0.5 ----------Eq(2)

Note: Adding the probability of all passes to probability of exactly 2 pass gives probability of at least 2 passes.

So, mpc = 0.1 = 1/10 ----------Eq(3)

From Eq(2) and Eq(3):

mp + pc+ mc - mpc = 0.6 ----------Eq(4)

And from Eq(1) and Eq(4):

m + p + c = 0.75 + 0.6 = 1.35

m + p + c = 135 / 100 = 27/20

Hence, the correct answer is option D.

Average marks of the class in the examination is \(= \frac{{total;amrks;obtained}}{{total;number;of;student}}\)

\(= \frac{{21 \times 2 + 15 \times 3 + 11 \times 1 + 23 \times 2 + 31 \times 5}}{{44}} = 6.795\)

Data:

g(x) = 1 – x

\(h\left( x \right) = \frac{x}{{x - 1}}\) 

Calculation:

\(g\left( {h\left( x \right)} \right) = 1 - ;\frac{x}{{x - 1}} = ; - \frac{1}{{x - 1}}\)

\(h\left( {g\left( x \right)} \right) = ;\frac{{1 - x}}{{1 - x - 1}} = \frac{{1 - x}}{{ - x}};\)

\(\frac{{g\left( {h\left( x \right)} \right)}}{{h\left( {g\left( x \right)} \right)}} = \frac{{ - \frac{1}{{x - 1}}}}{{\frac{{\left( {1 - x} \right)}}{{ - x}};}} = \frac{{\frac{x}{{x - 1}}}}{{1 - x}}; = \frac{{h\left( x \right)}}{{g\left( x \right)}}\)

\(let;y = {x^{\frac{1}{x}}}\)

Taking log_e on both sides

\({\log _{\rm{e}}}{\rm{y}} = \frac{1}{{\rm{x}}}{\log _{\rm{e}}}{\rm{x}}\)

\({\rm{Taking;}}\mathop {{\rm{lim}}}\limits_{{\rm{x}} \to \infty } {\rm{;on;both;sides;}}\)

\(\mathop {{\rm{lim}}}\limits_{x \to \infty } {\log _{\rm{e}}}{\rm{y}} = \mathop {{\rm{lim}}}\limits_{x \to \infty } \frac{1}{{\rm{x}}}{\log _{\rm{e}}}{\rm{x}}\)

Substituting x = ∞

It is of the form \(\frac{\infty}{\infty}\) 

Differentiating w.r.t x

\(\mathop {{\rm{lim}}}\limits_{x \to \infty } {\log _{\rm{e}}}{\rm{y}} = \mathop {{\rm{lim}}}\limits_{x \to \infty } \frac{1}{{\rm{x}}}\)

Substituting x = ∞

\({\log _{\rm{e}}}{\rm{y}} = 0;;;;;;;\left( {\frac{1}{\infty } = 0} \right)\)

∴ y = e⁰

∴ y = 1

• Prim’s algorithm uses the greedy method to find the minimum spanning tree of a graph G(V, E).
• Floyd-Warshall algorithm uses dynamic programming approach to find all-pairs shortest paths of a graph G(V, E) .
• Mergesort uses divide and conquer approach to sort an array.
• Hamiltonian circuit finding requires backtracking.

Worst-case time complexity of the Quicksort is O (n2) 

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

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

Recurrence relation gives: T(n) = O (n2). Hence option 2 is correct

Maximum nodes in Graph with height 5:

Maximum number of nodes = 1 + 2 + 4 + 8 + 16 + 32 = 6 

Minimum nodes in Graph with height 5:

Minimum number of nodes = 6 

Tips and Tricks:

If nmax is the maximum number of nodes and H height of in a binary search tree, then

n_max = 2H+1 – 1

put H = 5

n_max = 2H+1 – 1 = 2⁶ - 1 = 63

If n is the minimum number of nodes and H is the height of in a binary search tree, then

n_min = H + 1

put H = 5

nmin = 5  + 1 = 6

Condition coverage test: Each one of the Boolean expression with values TRUE and FALSE. For this, tester should know the code. Hence it is White box testing.

Equivalence class partitioning: divides the input test data into each partition at least once of equivalent data from which test cases can be derived. Only input vales are needed, not the code. Hence it is black box testing.

Volume testing: Check system performance with increasing volumes of data in the database.

Alpha Testing is a type of software testing performed to identify bugs before releasing the product to real users or to the public. Alpha Testing is system testing

Statement I:  3, 5, 7, 8, 15, 19, 25

It doesn't violate Binary search tree property and hence it is the correct order of traversal.

Statement II: 5, 8, 9, 12, 10, 15, 25

15 is left of 12 which violates binary search tree property.

Statement III: 2, 7, 10, 8, 14, 16, 20

14 is left of 10 which violates binary search tree property.

Statement IV: 4, 6, 7, 9 18, 20, 25 

It doesn't violate Binary search tree property and hence it is the correct order of traversal.

Viable Prefixes: The set of prefixes of right sentertict forms that can appear on the stack are called viable prefixes.

The stack contains only a set of viable prefixes at a given time.

Formula:

p ↔ q ≡ (¬ p ∧ ¬ q) ∨ (p ∧ q) = p̅.q̅ + p.q 

p → q = ¬ p ∨ q ≡ p̅ + q

Derivation:

Option 1:

(¬ p ⋁ q) ⋀ (p ⋁ ¬ q) ≡  (p̅ + q).(p + q̅ ) ≡ p̅.q̅ + pq 

Option 2:

(¬ p ⋁ q) ⋀ (q → p) ≡ (¬ p ⋁ q) ⋀ (¬ q ∨ p) ≡  (p̅ + q).( q̅ + p) ≡ p̅.q̅ + pq 

Option 3:

(¬ p ⋀ q) ⋁  (p ⋀ ¬ q) ≡ p̅.q + p.q̅ ≠ p̅.q̅ + pq 

Option 4:

(¬ p ⋀ ¬ q) ⋁  (p ⋀ q) ≡ p̅.q̅  + p.q

Therefore, (¬ p ⋀ q) ⋁  (p ⋀ ¬ q)  is NOT equivalent to p ↔q

Concepts:

In mathematics, the power set (or powerset) of any set S is the set of all subsets of S, including the empty set and S itself.

Explanation:

A = {5, {6}, {7}}

Power set of A = 2^A = {Φ, {5}, {{6}}, {{7}}, {5, {6}}, {5, {7}}, {{6}, {7}}, {5, {6}, {7}}}

Statement I

Φ is element of power set of A. Therefore, Φ ϵ 2^A.

Statement II.

Power set of A consists of all subsets of A and from the definition of a subset, ϕ is a subset of any set.

Therefore, Φ ⊆ 2^A

Statement III

{5, {6}} is element of power set of A. Therefore, {5, {6}} ϵ 2^A.

Statement IV

{5, {6}} is element of power set of A. Therefore, {{5, {6}}} ⊆ 2^A.

Hence statement IV is false.

Therefore option 3 is correct.

Circuit for Johnson counter:

From LSB bit complement (Q̅₃  ) is fed into MSB(Q₀)

Q0 is MSB and Q3 is LSB 

Count sequence of 0 → 8 → 12 → 14 → 15 → 7 → 3 → 1 → 0 →  (repeat)

Confusion Point:

If Q₃ is MSB and Q₀ is LSB

Count sequence of 0 → 1 → 3 → 7 → 15 →14 →12 → 8 → 0 →  (repeat)

Important Points:

In Anser key. option 4 is given as correct

In three address instruction formats, each address filled can specify a memory operand or a processor register.

E.g. ADD C B Address \ C ← B + [Address]

But Accumulator register is implicitly used as destination address. E.g. ADD B

Statement I: FALSE:

TCP sequence number of a segment is the byte number of the first byte in the segment. For example, if the segment contains 200 bytes which are from 100 to 199, then the sequence number of the segment would be 100 and the sequence number of the next segment would be 200.

Statement II:TRUE:

To avoid frequent retransmission of a packet, the estimated round trip time at any given point of time is greater than or equal to retransmission time out.

Statement III: FALSE 

Size of the receiver’s buffer never change. Advertised window is the part of the receiver buffer which keeps changing depending upon the processing capability at the receiver's side and the network traffic.

Statement IV: TRUE

The number of unacknowledged bytes at the sender is always less than or equal to the advertised window

Concept:

In a symmetric key cryptographic system, both parties have access to the key. So, the first person has N-1 keys with other N-1 people, the second one has another N-2 with N-2 people (since 1 is already considered) and so on till 1.

Formula

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

Calculation

Total number of keys required = 1 + 2 + 3 + … + (N – 2) + (N – 1)

where n = N – 1  

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

Statement I: TRUE

XML is a structured way of organizing content.

Statement II: FALSE

XML is case sensitive whereas HTML is not case sensitive.

Statement III: TRUE

XML facilitates user-defined tags whereas HTML has only pre-defined tags.

Statement IV: FALSE

XML tags must be closed while HTML tags may not be closed.

Therefore option 3 is correct.

A router will not change the source address of the packet, rest of the given fields can be changed at the router.

Checksum: Checksum field changes at every router in correspondence with the change in values of other fields.

TTL (Time to Live): After every hop, the TTL field is reduced by one. Hence this field changes at every router.

Length: If fragment - apian is required length field will certainly change.

HTTP: Multiple TCP connections can be used at client and server end.

FTP: For FTP also multiple connections can be used at the same time.

TELENT: Only one TCP connection is allowed at a time.

SMTP: SMTP also allows only one TCP connection at a time.

Properties:

Context free language is not closed under complementation.

Recursively enumerable language is not closed under complementation.

Recursively enumerable language is closed under union.

Recursive languages are closed under complementation.

Explanation:

L₁: Context-free

L₂: recursively enumerable but not recursive

Statement I:

L̅₁ (complement of L₁) is recursive → TRUE

Since context free language (L₁) is not closed under complementation. Therefore, L̅₁ is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursive language.

Statement II:

L̅₂ (complement of L₂) is recursive → FALSE

Since recursively enumerable language (L₂) is not closed under complementation. Therefore, L̅₂ is not recursively enumerable language. If a language is not recursively enumerable then it cannot be recursive for sure. Since recursive language is subset of recursively enumerable language.

Statement III:

L̅₁ is context-free → FALSE

Since context free language (L₁) is not closed under complementation. Therefore, L̅₁ is not context free language.

Statement IV: → TRUE

Since context free language (L₁) is not closed under complementation. Therefore, L̅₁ is not context free language.

Complement of context free grammar is context sensitive language and every context sensitive language is recursively enumerable language.

Also, recursively enumerable language is closed under union. Therefore, L̅₁ ∪ L₂ is recursively enumerable.

Data

1 word (W) = 1 byte (B)

Logical address = 232 B

page size = 4 KB = 212 B

page table entry (PTE) = y B

Formula:

Page table size (PTS) = number of pages × y

Calculation:

number of pages = \(\frac{{{2^{32}}}}{{{2^{12}}}} = {2^{20}}\)

Page table size (PTS) = number of pages × y

\(PTS = {2^{20}} \times 4B\)

∴ PTS = 4 MB

Important points

1 MB = 2²⁰ B

where B stands for byte

Initial value of B is 2 //value stored in main memory

Value of B = 4

First execute P2()

P2 ( ) {

D = 2 * B;   // 2 × 2 = 4

B = D – 1; // B = 4 – 1 = 3

}

write the value of B = 3 to memory

execute P1()

P1 ( ) {

C = B – 1; // C = 3 – 1 = 2

B = 2 * C; // B = 2 × 2 = 4

}

write the value of B = 4 is memory.

Distinct value of B is 4.

Value of B =3

First Execute P1()

P1 ( ) {

C = B – 1; // C = 2 – 1 = 1

B = 2 * C; // B = 2 × 1 =2

}

write the value of B = 2 to memory

then execute P2()

P2 ( ) {

D = 2 * B;   // 2 × 2 = 4

B = D – 1; // B = 4 – 1 = 3

}

write the value of B = 3 to memory

One of the distinct values of B is 3.

Value of B = 2

First execute P2()

P2 ( ) {

D = 2 * B;   // 2 × 2 = 4

B = D – 1; // B = 4 – 1 = 3

}

//don’t write to memory

execute P1()  // with initial value of B = 2

P1 ( ) {

C = B – 1; // C = 2 – 1 = 1

B = 2 * C; // B = 2 × 1 = 2

}

write the value B = 3 by P2() in memory.

overwrite the value written by P2() as B = 2 by P1() in memory.

One of the distinct values of B is 2.

Therefore, the distinct values of B are 2, 3 and 4.

The number of distinct values that B can possibly take after the execution is 3.

Select operation is equivalent to the projection operation in relational algebra, except that select in SQL retains duplicates and on the contrary projection removes the duplicates.

A file is organized so that the ordering of data records is the same as or close to the ordering of data entries in some index is called clustered index, hence table can have only one clustered index.

Given \(LU; = ;\left[ {\begin{array}{*{20}{c}} 2&2\ 4&9 \end{array}} \right]\)

\(\left[ {\begin{array}{*{20}{c}} x&0\ z&y \end{array}} \right]\left[ {\begin{array}{*{20}{c}} 1&p\ 0&1 \end{array}} \right]; = ;\left[ {\begin{array}{*{20}{c}} 2&3\ 4&9 \end{array}} \right]\)

\(;\left[ {\begin{array}{*{20}{c}} x&xp\ z&zp + y \end{array}} \right] = ;\left[ {\begin{array}{*{20}{c}} 2&2\ 4&9 \end{array}} \right]\)

lower diagonal entry I22 = y

x = 2,

xp = 2 

∴ p = 1

z = 4

zp + y = 9

(4)(1) + y = 9

y = 9 - 4

∴ y = 5

lower diagonal entry I22 = 5

f1 ( ) swaps values of a and b but in its local environment as parameters are passed by value.

f2 ( ) swaps values of b and c in main ( ), as parameters are passed by reference.

Hence final values of a, b and c are 4, 6 and 5 respectively.

∴ 5 – 4 – 6 = - 5

Concepts:

Minimum height of the tree is when all the levels of the binary search tree (BST) are completely filled.

Maximum height of the BST is the worst case when nodes are in skewed manner.

Formula:

Minimum height of the BST with n nodes is ⌈log2 (n + 1)⌉ - 1

The maximum height of the BST with n nodes is n - 1.

BST with a maximum height:

Insertion:

Traverser the BST to the maximum height

Worst-case time complexity of Insertion = θ (n - 1) ≡ θ (n)

Deletion:

Traverser the BST to the maximum height

Worst-case time complexity of  = θ (n - 1) ≡ θ (n)

Data:

 \(\eta ≥\frac{50}{100} ≥ \frac{1}{2}\)

T_p = 20 ms

BW = 64 Kb

Formula: 

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

\(a = \frac{T_p}{T_t}\)

\(T_t = \frac{L}{BW}\)

Calculation:

\(\eta ≥ \frac{1}{2}\)

\(\frac{1}{1 + 2a} ≥ \frac{1}{2}\)

1 + 2a ≤ 2

2a ≤ 1

\(2\frac{T_P}{T_t} ≤ 1\)

2 × 20 × 10^-3   ≤ T_t

L ≥ 2 × 20 × 10-3  × 64 × 10³

L ≥ 40 × 64 bits

L ≥ 2560 bits (We need to convert in bytes)

L ≥ 2560 bits/ 8

L ≥ 320 bytes

L_min = 320 bytes

he minimum frame size in bytes to achieve a link utilization of at least 50% is 320

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:

Heap before inserting ‘35’:

After inserting ‘35’ will swap with ‘15’ and then with ‘30’.

New array order is: 40 35 20 10 30 16 17 8 4 15

Concepts:

Cyclomatic complexity is a software metric used to indicate the complexity of a program. It is a quantitative measure of the number of linearly independent paths through a program's source code.

Predicates are if, else if, else, and if

Data:

Number of predicates = n = 4

Cyclomatic complexity = No. of predicates + 1 

Formula:

Cyclomatic complexity = 4 + 1 = 5

The cyclomatic complexity of the program segment is 5

Data:

S₁ = 0.1, S2 = 0.2, S3 = 0.3 and S4 = 0.4

Formula:

Probability of successful transmission in first slot = P (at a time only one node transfers)

\(P(T) = S_1.\bar S_2.\bar S_3.\bar S_4 + \bar S_1.S_2.\bar S_3.\bar S_4 + \bar S_1.\bar S_2.S_3.\bar S_4 + \bar S_1.\bar S_2.\bar S_3.S_4\)

Calculation:

P(T) = 0.1 × 0.8 × 0.7 × 0.6 + 0.9 × 0.2 × 0.7 × 0.6 + 0.9 × 0.8 × 0.3 × 0.6 + 0.9 × 0.8 × 0.7 × 0.6

∴ P(T) = 0.4404

The probability of sending a frame in the first slot without any collision by any of these four stations is 0.4404

\()**Concepts:**

XOR operation is commutative and associative

**Calculation:**

p ≠ q ≡ p̅.q + p.q̅ ≡ p ⊕ q //XOR operation

**Explanation:**

\(\begin{array}{l} p ≠ q; = ;p̅ q; + ;p̅ q; = ;q ≠ p\ \left( {p ≠ q} \right) ≠ r; = ;\left( {̅ pq; + ;p̅ q} \right) ≠ r\ = ;\overline {̅ pq; + ;p̅ q} .r; + ;\left( {̅ pq; + ;p̅ q} \right).̅ r\ = ;\overline {̅ pq} .\overline {p̅ q} .r; + ;̅ pq̅ r; + ;p̅ q̅ r\ = ;\left( {p; + ;̅ q} \right)\left( {̅ p; + ;q} \right)r; + ;̅ pq̅ r; + ;p̅ q̅ r \end{array}\)

\(= ;pqr; + ;̅ p̅ qr; + ;̅ pq̅ r; + ;p̅ q̅ r\) - - - (1)

\(\begin{array}{l} p ≠ \left( {q ≠ r} \right); = ;p ≠ \left( {̅ qr; + ;q̅ r} \right)\ = ;̅ p.\left( {̅ qr; + ;q̅ r} \right); + ;p.\left( {\overline {̅ qr; + ;q̅ r} } \right)\ = ;̅ p̅ qr; + ;̅ pq̅ r; + ;p\left( {q; + ;̅ r} \right)\left( {̅ q; + ;r} \right) \end{array}\)

\(= ;̅ p̅ qr; + ;̅ pq̅ r; + ;pqr; + ;p̅ r̅ q\) - - - - - (2)

∴ (1) = (2)

Hence ≠ is both commutative and associative.

\(\mathop \sum \limits_{x = 1}^{99} \frac{1}{{x\left( {x + 1} \right)}} =\ \frac{1}{2} + \frac{1}{{2 \times 3}} + \frac{1}{{3 \times 4}} + \frac{1}{{4 \times 5}} \ldots \frac{1}{{99 \times 100}}\)

\(\mathop \sum \limits_{x = 1}^{99} \frac{1}{{x\left( {x + 1} \right)}} = \ \frac{1}{2} + \frac{1}{6} + \frac{1}{{12}} + \frac{1}{{20}} \ldots + \frac{1}{{9900}}\)

\(\mathop \sum \limits_{x = 1}^{99} \frac{1}{{x\left( {x + 1} \right)}} = \ \left( {1 - \frac{1}{2}} \right) + \left( {\frac{1}{2} - \frac{1}{3}} \right) + \left( {\frac{1}{3} - \frac{1}{4}} \right) + \left( {\frac{1}{4} - \frac{1}{5}} \right) \ldots + \left( {\frac{1}{{99}} - \frac{1}{{100}}} \right)\)

\(\mathop \sum \limits_{x = 1}^{99} \frac{1}{{x\left( {x + 1} \right)}} = 1 - \frac{1}{{100}} = 0.99\)

ℒ = {p, q, r, s, t}

|ℒ| = 5

∴ |ℒ ³| = 5 × 5 × 5 = 125

Example of Lattice

Hasse diagram of [{1,2,3,5,30};/]

x ⋁ (y ⋀ z) = (x ⋁  y) ⋀ (x ⋁  z) that satisifes

2 ⋁ (3 ⋀ 1 ) ≡ 2 ⋁ 3 ≡ 1

(2 ⋁ 3) ⋀ (2 ⋁ 1) ≡ 1 ∨ 1 ≡ 1

L.H.S = R.HS

Thefore pr ≠ 0

x ⋁ (y ⋀ z) = (x ⋁  y) ⋀ (x ⋁  z) that doesn't satisifes

2 ⋁ (3 ⋀ 5 ) ≡ 2 ⋁ 30 ≡ 2

(2 ⋁ 3) ⋀ (2 ⋁ 5) ≡ 1 ∨ 1 ≡ 1

L.H.S ≠ R.HS

Thefore pr ≠ 1

Number of ways to chose {2, 3, 5} = 3! =6

∴ only 6 combination will violate the distributive property

probability that satify the distributive property = \(1 - \frac{6}{125} = 0.952\)

Therefore \(\frac{1}{5} < {p_r} < 1\)is correct answer

Functionally complete operations set is a set of logic functions from which any arbitrary Boolean logic function can be realized.

Examples of functionally complete operation set are:

1. OR gate, NOT gate
2. AND gate, NOT gate
3. NOR gate
4. NAND gate
5. 2:1 MUX

Any superset of the above examples will also form functionally complete operations set.

f (X, Y, Z) = X’ YZ + XY’ + Y’Z’     (1)

substitute Y = X  and Z = X in equation (1)

f (X, X, X) = X’.X.X + X.X’ + X’X’ = X'

substitute X = Z  and Y = X in equation (1)

f (Z, Z, Z) == Z’.Z.Z + Z.Z’ + Z’Z’  = Z'

substitute Z = Y  and X = Y in equation (1)

f (X, Y, Z) = Y’ YZ + YY’ + Y’Y’ = Y'

Therefore operation for NOT gate is possible 

substitute Y = X  in equation (1)

f (X, X, Z) = X’ XZ + XX’ + X’Z’     (1)

f (X, X', Z) =  X'Z'

substute X = X' and Z = Z' //use the complement 

in above function

f =  X'Z' = X.Z

Therefore operation for AND gate is possible

and hence f is functionally complete.

g (X, Y, Z) = X’ YZ + X’ YZ’ + XY

g(X,X,X) = X’ X.X + X’ X.X’ + X.X = X // complement cannot be derived

Therefore g is not functinally complete

Data:

number of faces = |F|

number of vertices  = |V| = 10

edges covering each face = 3

Formula:

According to Euler’s formula : 

|V| - |E|  + |F| = 2

Calculation

edges on each face is three

∴ 2 |E| = 3 |F|       (every edge is shared by 2 faces)

\(|F| = \frac{2}{3} |E|\)

\(10 - E + \frac{2}{3}|E|=2\)

|E| = 24

the number of edges in G is 24

For one bit:

number of bit strings of length 1 containing two consecutive 1’s is 0

∴ a₁ = 0

For two bits:

number of bit strings of length 2 containing two consecutive 1’s is 1

∴ a₂ = 1

For 3 bits:

number of bit strings of length 3 containing two consecutive 1’s is 3

∴ a₃ = 3

Similarly

For 4 bits:

a₄ = 8

Option 1:

a₃ = a_n-2 + a_n-1 + 2^n-2

a₃ = a₁ + a₂ + 2¹

∴ a₃ = 0 + 1 + 2 =3

Also, a₄ = 1 + 3 + 2² = 8

Option 2:

a_n = a_n-2 + 2a_n-1+ 2^n-2

a₃ = a₁ + 2a₂ + 2¹

a₃ = 0 + 2 + 2 = 4 (INCORRECT)

Option 3:

a_n = 2a_n-2 + a_n-1 + 2^n-2

a₃ = 2a₁ + a₂ + 2¹

∴ a₃ = 1 + 2 = 3

a₄ = 2a₂ + a₃ + 2²

∴ a₄ = 2 + 3 + 4 = 9 (INCORRECT)

Option 4:

a_n = 2a_n-2 + 2a_n-1 + 2^n-2

a₃ = 2a₁ + 2a₂ + 2¹

∴ a₃ = 0 + 2 + 2= 4 (INCORRECT)

Concept:

A variable is considered live if it is used in the block and not overwritten by any other variable.

Rule of liveliness: If a block does not use a variable which is live after its exit point, then this variable is live also before the entry point of that block.

Explanation:

Here, variable {q and r} are live in line 1 of block 1. But p is dead because p is overwritten in the first line and then used by s. Variable s is dead at the entry point of block 1. U is not read in block 1 so it is dead before block 1.

Before Block 2, variable r and u are being read so they are live at entry point of Block 2. Similarly, in Block 3, variable s and u are live at entry point of block 3.

In Block 4, variable v and r is live and by rule of liveliness variable r and v are live before Block 3 also.

Variables which live in Block 2: r and u

Variables which are live in Block 3: r, s, u and v

But we have to find which are live in both blocks. So, answer is r and u.

Concept:

Three address code is an intermediate code generated by compilers while optimizing the code.

Rules in static single assignment form:

• Each variable must be assigned exactly once.
• Every variable must be defined before it is used.
• All of the uses reached by the assignment must be renamed.

Explanation:

Given expression: q + r / 3 + s – t * 5 + u * v / w

So, t₁ = r/3

t₂ = t * 5

 t₃ = u * v

t₄ = t₃ / w

t₅ = q + t₁

t₆ = t₅ + s

t₇ = t₆ – t₂

t₈ = t₇ – t₄

Total 8 temporary variables are required to create a three-address code in static single assignment form.

Concept:

A relation is in 3NF for every functional dependency if X -> A  and one of the following condition holds true .

1. X is a superkey  or

2. A is a prime attribute.

Explanation:

E₁ has attributes a₁₁ and a₁₂. a₁₁ is the primary key.

Entity E₂ has attributes a₂₁ and a₂₂ where a₂₁ is the primary key.

Entity E₃ has attributes a₃₁ and a₃₂ where a₃₁ is the primary key.

R₁₂ is many to many relationship between E₁ and E₂. So, R₁₂ contains attributes a₁₁ and a_21.

R₁₃ is a one to many relationship between E₁ and E_3. R₁₃ contains attributes a₁₁ and a₃₁

In this we have 5 tables 3 for three entities and 2 for two relation.

But we have to find minimum number of tables or relations considering if all the relations are in 3 NF.

Here, we have to keep a separate table for R₁₂ because if we combine it with any other relation it will violates 1 NF and hence 3NF. Because it will contain composite key since it is a many to many relation.

But we can combine relation R₁₃ with entity E₃.

R₁₃E₃ (a₁₁, a₃₁, a₃₂)

It will not violates 3 NF . Because here a_11, a₃₁, a₃₂ is the key.  Here, it will not create any partial dependency. Hence it satisifies 3NF.

So, minimum 4 relations are required here.

Consider DFA M,

It is accepting all the string that ends with a.

Language for DFA M L(M) = {a, aa, ba, aaa, aba, …}

Regular expression = (a + b )*a

DFA N is accepting all the languages ending with b.

Language for DFA N L (n) = {b, ab, bb, aab, abb, bbb,…….}

Regular expression = (a + b)*b

Intersection of both these languages L (M) ꓵ L(N) = { } = Ø i.e. empty language

For this, we just need 1 state with all transitions to itself and no final state.

In this Z represents the top of the stack.

1, Z → 1Z means, on input symbol 1 , if stack top is Z then it changes to 1.

Here, in q₀ state, for a 1 , a ‘1’ is pushed into the stack and for a ‘0’ a ‘0’ is pushed into stack. In q₁ stack, for a ‘0’ a ‘1’ is popped and for a ‘1’ a ‘0’ is popped. It means when it finds a complement of input character on top of stack then it pop one element from top of stack.

Given string is 101100 having 6 letters, but in options we have to append 5 length string so one bit is ignored to transit between state.

Only option 2) matches with this PDA.

String will be like 10110010010

At state q₀, input is 1, push 1 (remain at q₀ state)

At state q₀, input is 0, push 0 (remain at q₀ state)

At state q₀, input is 1, push 1 (remain at q₀ state)

At state q₀, input is 1, push 1 (remain at q₀ state)

At state q₀, input is 0, push 0 (remain at q₀ state)

At state q₀, input is 0, ignore (move to q₁ state)

At state q₁, input is 1, stack top 0, pop (remain at q₁ state)

At state q₁, input is 0, stack top 1, pop (remain at q₁ state)

At state q₁, input is 0, stack top 1, pop (remain at q₁ state)

At state q₁, input is 1, stack top 0, pop (remain at q₁ state)

At state q₁, input is 0, stack top 1, pop (remain at q₁ state)

At state q₁, input is null, stack top null, accepted.

Lemma:

Let G = (V, E) be a directed or undirected graph, and let s ϵ V be an arbitrary vertex, then, for any edge (u, v) ϵ E

δ(s, v) ≤ δ(s, u) + 1   

Explanation:

Option 1: d(u)−d(v) = 0 → possible

 u and v have an edge from y and y is in the shortest path from s to u or v.

Option 2: d(u)−d(v) = 1 → possible

v and y are in the shortest path from s to u and both y and v are siblings - same distance from s to both t and v causing y − u edge to be in BFS tree and not v – u.

Option 3: d(u)−d(v) = −1 → possible

By interchanging u and v.

Option 4: d(u)−d(v) = 2 → not possible.

Because on BFS traversal we either visit u first or v.  Take u, now, put all neighbours of u on queue. Since v is a neighbour and v are not visited before as assumed, d(v) will become d(u) + 1. Similarly, for v being visited first.

First instance of all three process arrive at t = 0ms

Their arrival times are like:

T₁ = 0, 3, 6, 9, 12, ……….

T₂ = 0, 7, 14, 21, ………

T₃ = 0, 20, 40, 60, …………

Because they arrive periodically at intervals of 3, 7 and 20 milliseconds.

Also, their burst time are given as 1, 2 and 4 ms respectively.

Priorities are in the inverse of period.

As, they all first arrive at time 0, so Gantt chart will be like:

0          1          3           4        6          7          9          10       12

So, in this way first instance of T₃ completes its execution at the end of 12 ms.

The correct answer is 0110110…

EXPLANATION:

Output for next cycle is in the sequence 0110110……

Data:

Seek time for a sector = 4 ms

Rotational speed = 1000 RPM

Sectors in a file = 2000

Formula:

Total time to read entire file = seek time + rotational latency + transfer time

Calculation:

10000 rotations → 60 sec

\(\therefore 1{\rm{;rotation}} \to \frac{{60}}{{10000}}{\rm{;seconds}} \to 6{\rm{;ms;}}\)

\({\rm{Rotational;latency;for;a;sector}} = \frac{{6{\rm{;ms}}}}{2} = 3{\rm{;ms}}\)

1 rotation covers 1 track

1 track has 600 sectors

\({\rm{Transfer;rate;for;a;sector}} = \frac{6}{{600}} = \frac{1}{{100}}{\rm{;ms}}\)

Total time needed = total sectors in a file × (seek time + rotational delay + transfer rate)

\({\rm{Total;time;needed}} = 2000 \times \left( {4{\rm{;}} + {\rm{;}}3{\rm{;}} + \frac{1}{{100}}{\rm{;}}} \right)ms\)

Total time needed = 14020

Data:

Clock rate for non-pipeline = 2.5 GHz

CPI for non-pipeline = 4

Clock rate for pipeline = 2 GHz

CPI for pipeline = 1

Formula:

Speed up = \(\frac{{Execution;time\left( {non;pipeline} \right)}}{{Execution;time;\left( {pipeline} \right)}}\)

Execution time = CPI × Cycle time (CPI is cycles per instruction)

\({\rm{Cycle;time;}} = \frac{1}{{{\rm{clock;rate}}}}\)

Calculation:

Execution time for non-pipeline = \(4 \times \frac{1}{{2.5}} = 1.6;ns\)

Execution time for pipeline = \(1 \times \frac{1}{2} = 0.5;ns\)

Speed up = \({{1.6}}{{0.5}} = 3.2\)

LOOK Algorithm:

Header first goes to the farthest request towards the right and then returns to the farthest request 1.

For SCAN it takes 140 head movements

∴ Total Tracks = (100 - 50) + (100 - 10) = 90 + 50 = 140

Shortest Seek Time First (SSTF)

Total tracks = (50 - 45) + (90 - 45) + (90 - 10) = 130

Hence the additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN is 140 - 130 = 10.

LRU:

9-page faults:

FIFO:

9-page faults:

Hence LRU and FIFO will have 9-page faults.

Alternate method:

Hence LRU and FIFO will have 9-page faults.

\(let;I = \mathop \smallint \limits_{1/\pi }^{2/\pi } \frac{{{\rm{cos}}\left( {1/x} \right)}}{{{x^2}}}\)

\(put\frac{1}{x} = t\)

\(when;x = \frac{1}{\pi };;then;t = \pi \)

\(when;x = \frac{2}{\pi };;then;t = \frac{\pi }{2}\)

\(\frac{1}{x} = t\)

Differentiating with respect to x

\(- \frac{1}{{{x^2}}};dx = dt\)

\(\therefore I = - \mathop \smallint \limits_\pi ^{\frac{\pi }{2}} {\rm{cos}}\left( t \right)dt\)

\(I = - \left[ {\sin \left( t \right)} \right]_\pi ^{\frac{\pi }{2}}\) 

I = -[sin(π/2) – sin(π)]

∴ I = -1

Concept:

The determinant of the matrix is equal to the product of eigenvalues

Sum of all eigenvalues of a matrix is equal to its trace

Data:

λ₁ = -1

λ₂ = 7  

Calculation:

1 + a =  λ1 + λ2

1 + a = -1 + 7

∴ a = 5

\(|A|; = ;\left| {\begin{array}{*{20}{c}} 1&4\ b&a \end{array}} \right|\)

1 × a - 4 × b = λ1 × λ2

a - 4b = (-1) × (7)

5 - 4b = -7

∴ b = 3 

The values of a and b are 5 and 3  respectively.

(I) Unsorted Array:

\(\begin{array}{l} T\left( {Find} \right) \simeq \frac{N}{2}\ T\left( {Insert} \right) \simeq 0\left( 1 \right)\ T\left( {Delete} \right) \simeq \frac{N}{2}\ T\left( {Decrease;key} \right) \simeq \frac{N}{2}\ \therefore T\left( {total} \right) \simeq \sqrt {\log N} \left[ {\frac{3}{2}N} \right]; + ;{\rm{N}} \end{array}\)

(II) Min - Heap:

\(\begin{array}{l} T\left( {Find} \right) \simeq \frac{N}{2}\ T\left( {Insert} \right) \simeq \log N\ T\left( {Delete} \right) \simeq \frac{N}{2}; + ;\log N\ T\left( {Decrease;key} \right) \simeq \frac{N}{2}; + ;\log N\ \therefore T\left( {Total} \right) \simeq \sqrt {\log N} \left[ {\frac{{3N}}{2}; + ;2\log N} \right]; + ;N\log N \end{array}\)

(III) Sorted Array:

\(\begin{array}{l} T\left( {Find} \right) \simeq \log N\ T\left( {Insert} \right) \simeq \log N; + ;\frac{N}{2}\ T\left( {Delete} \right) \simeq \log N; + ;\frac{N}{2}\ T\left( {Total} \right) \simeq \sqrt {\log N} \left[ {3\log N; + ;\frac{3}{2}N} \right]; + ;\frac{{{N^2}}}{2}; + ;N\log N \end{array}\)

Sorted doubly linked list will be even worst choice.

Hence unsorted array will be the best choice for given algorithm.

• The given SQL query is selecting the Student_Name column from the Student table and the sum of Marks column from the Performance table.
• It is joining the two tables on Roll_No column and grouping the results by Student_Name.
• The result of the query will return two rows because there are only two distinct student names in the Student table, "Raj" and "Rohit".
• For "Raj", there are two rows in the Performance table with Roll_No = 1 and 3, and the sum of Marks for these rows is 310.
• For "Rohit", there is only one row in the Performance table with Roll_No = 2, and the sum of Marks for this row is 140.
• Therefore, the SQL query will return the following two rows:

Output of the given SQL query will be:

Hence, the number of rows returned by the SQL query is 2.

x is a 2-D array of arrays

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

Since minimum spanning tree is given, in order to obtain a minimum sum of weights for the graph and to exclude the edge while building MST.

|AB| = max(9,2) + 1 = 10 (1 is added because weights are distinct)

|ED| = max(6,4) + 1 = 7

|CD| = max(15, 2, 7) + 1 = 16

Hence the minimum sum of weights for the graph is 36 + 10 + 7 + 16 = 69.

\(\begin{array}{l} \therefore p; = ;\log n,;q; = ;\log p; = ;\log \left( {\log n} \right)\ \therefore q; = ;n.\log \left( {\log n} \right) \end{array}\)

code is doing division by subtraction. Y is being subtracted repeatedly from r until it is less than y.

∴ At the end: