GATE CS 2019 Official Paper (Previous Year Paper)

Break down is a phrasal verb which means an explanatory analysis, especially of statistics.

'Break' and 'breaks' are rejected as they do not have 'down' in them, and they do not form a meaningful sentence when filled in the blank.

The sentence is in simple present tense with a singular subject, hence 'breaks down' is the correct answer. 

Hence, 'breaks down' is correct.

The given sentence implies that the search engine’s business model has trust as the main subject.

Revolves around: to have (someone or something) as a main subject or interest.

Plays around: to deal with or treat something in a careless way.

'Plays' is rejected as it does not fit the sentence contextually.

Sinks and bursts are rejected as they are grammatically incorrect with 'around'.

Option 1 is correct.

Let speed of car 1 be 50 km and speed of car 2 be 60 km

Since both are moving in same direction,

relative speed = | 50 - 60 | = 10 km/h

distance = 20 km, time = ?

$speed = \frac{{distance}}{{time}}$

$10 = \frac{{20}}{{time}}$

∴ time = 2 h

The number of hours it takes for the distance between the two cars to be 20 km is 2 hours.

Let initially, ₹ x be contributed by each friend and ₹ y be gift cost

Therefore, the cost of the gift is $y = 10x$ (I)

After two friends left, the cost of the gift is not changed and contribution is increased by 150 per friend

Therefore, cost of the gift is $y = \left( {10 - 2} \right) \times \left( {x + 150} \right)$ (II)

From I and II

$\begin{array}{l} 10x = 8\left( {x + 150} \right)\ 2x = 1200\ \therefore x = 600 \end{array}$

$\begin{array}{l} y = 10x\ y = 10 \times 600\ \therefore y = 6000 \end{array}$

The cost of the gift was Rs. 6000

Courts employ judges.

Schools employ teachers.

Option 4 is correct.

Let S1: P says “Q committed the crime.”

S2: Q says “S committed the crime.”

S3: R says “I did not do it.”

S4: S says “What Q said about me is false.”

1. Assume that P committed the crime:

S1 is false, S2 is false, S3 is true, S4 is true

Since S3 and S4 are true, R and S says true but only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that P committed the crime is false.

2. Assume that R committed the crime:

S1 is false, S2 is false, S3 is false, S4 is true

Since S4 is true, S says true and only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that R committed the crime is true.

3. Assume that S committed the crime:

S1 is false, S2 is true, S3 is true, S4 is false

Since S2 and S3 are true, Q and R both says true but only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that S committed the crime is false.

4. Assume that Q committed the crime:

S1 is true, S2 is false, S3 is true, S4 is true

Since S1, S3 and S4 are true, P, R and S says true but only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that Q committed the crime is false.

Total number of administrators = total number of people in rectangle

Total number of people in rectangle = 10 + 20 + 20 = 50

Total number of people = 70 + 10 + 20 + 20 + 40 = 160

$percentag{e_{content}} = \frac{{50}}{{160}} \times 100$

$percentag{e_{content}} = 31.25$

the percentage of administrators shall be in the range of 31 to 45

The given sentence means that the High Court refuses the idea of begging to be considered a disease leading to its stigmatization and criminalization and instead claims that begging is a phenomenon taking place due to the 'failure of the state to protect citizens who fall through the social security net'.

Options 1, 3, and 4 are rejected as they contain information which is not provided in the question. 

Option 2 is correct as it is the closest in meaning to the information provided in the question.

Students in respective clubs,

Only Drama Club = 60,

Only Dance Club = 80

Only Maths Club = 30

Drama Club and Dance Club = 38 + 2 = 40

Dance Club and Maths Club = 10 + 2 = 12

Drama Club and Maths Club = 5 + 2 = 7

Drama Club and Dance Club and Maths Club = 2

Total number of students = 60 + 80 + 30 + 38 + 10 + 5 + 2 = 225

Since 75% of students are not included in any of the clubs. Therefore, Venn diagram consists of only 25 percentage of students in the college.

Let x be total number of students in the college

$x \times \frac{{25}}{{100}} = 225$

$\therefore x = 900$

the total number of students in the college is 900.

Option 1:

Z is staying in the wing located in the north-west direction.

Therefore option 1 is incorrect.

Option 2:

X is in wing closed to Garden

Also, Z is staying in the wing located in the north-west direction.

Therefore option 2 is incorrect.

Option 3:

Z is staying in the wing located in the east direction

Therefore option 3 is incorrect.

Option 4:

X is in wing away from Garden

Y is in wing away from Washroom (WR)

Z is staying in wing located in the south-west direction

Therefore option 4 is correct.

Given:

Cache size = 16 KB = 2¹⁴ B

${\log _2}{2^{14}}$ = 14 bit

Cache block size = 16 B = 2⁴ B

${\log _2}{2^{4}}$ = 4 bit (offset)

Physical address = 2³² B = 4 GB //32-bit address

To find:

Number of bits in tag field

Number of bits in Index field

Explanation:

In Fully Associative Mapping:

Physical address:

Physical Address = Tag + block offset

32 = Tag + 4 // use number of bit

Tag = 28 bit

In Fully Associative Mapping, index fields is included in tag field there is no separate field for index in fully Associative Mapping. Hence number of bit in index field is zero

Note:

KB is Kilo Byte (2¹⁰ B)

To enable 5 input AND gate: A₁₅ A₁₄ A̅ ₁₃ A̅ ₁₂ A₁₁

First address: 1100 1000 0000 0000 = C800

Last address: 1100 1111 111 1111 = CFFF

Range of address: C800 to CFFF

28₁₀ = (11100)₂ = (0000 0000 0001 1100)₂

-28₁₀ = 2’s complement of 0000 0000 0001 1100

2’s complement of 0000 0000 0001 1100 = 1111 1111 1110 0100

Note:

Tricks to find: 2’s complement

Start reading the bits from LSB (right hand side) and write it unless first 1 is encounter, leave the first 1 as it is and complement the remaining bits.

Let U = {1, 2}

All Possible subsets of U = {ϕ, {1}, {2}, {1, 2}}

A = (x, X), x ∈ X and X ⊆ U

x can be only {ϕ, 1, 2}

When x = 1

X = (1, {1})

X = {1, {1, 2}}

When x = 2

X = {2, {2}}

X = {2, {1, 2}}

Therefore, total elements in A, |A| = 2 + 2 = 4.

Option 1:

|A| = n × 2^{n - 1} = 2 × 2^{2 - 1} = 4

Option 2:

\(\left| A \right| = \mathop \sum \limits_{k = 1}^n k\left( {\begin{array}{{20}{c}} n\ k \end{array}} \right) = 1 \times \left( {\begin{array}{{20}{c}} 2\ 1 \end{array}} \right) + 2 \times \left( {\begin{array}{*{20}{c}} 2\ 2 \end{array}} \right)\)

$\left| A \right| = 2 + 2 = 4$

Both the options are correct.

Important Points:

x = ϕ and X = ϕ is not considered since ϕ ∈ ϕ is not true.

Although we cannot generalize just from one example but in general both the cases always hold true for given conditions

1. (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) 

Therefore exclusive OR is associative and hence (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) 

(x + y) ⊕ z ≠ x ⊕ (y + z) ∴ is it not a valid identity

x + y = x ⊕ y // if xy = 0

(xy + x'y')'

= (x’ + y’).(x+y) // Demorgan’s Law

= x’y +xy’

= x ⊕ y

• Non-deterministic push down automata (NPDA) determines the middle position of the string in the language and start popping until Z(end of stack elements) is meet to tell the acceptance of it .
• As all the string present in the language ww^R accepted by NPDA Hence it is a context free language (CFL).
• From the properties of regular language: Reverse, Suffix, Prefix, Concatenation of Regular language is Regular.
• Every regular language is context free language, but every context free language is not a regular language also ww^R it is not possible to give, DFA, NFA or ϵ - NFA accepting the language. Therefore, it is not Regular language.

No Overflow occurs if two number with opposite signs are added.

Overflow is possible only when two number with same signs are added.

Numbers are in sign-magnitude form

Therefore, X and Y can take any value between - (2^{(n - 1)} - 1) to (2^{(n - 1)} - 1)

Assume n = 4

Therefore, X and Y can take any value between -7 to 7

Z = X - Y

To make X and Y of same sign take X as negative or take Y as negative but do not take both simultaneously. Also take larger number to force overflow

Case I: X = -7 and Y = 7

Z = -7 - 7 = -14 // smallest number possible

Case II: X = 7 and Y = -7

Z = 7 - (-7) = 7 + 7 = 14 // largest number possible

Case I and Case II are extreme overflow conditions

Based on Assumption (4 bit) on sign-magnitude form

Range of n - 1 = 3 bit = -3 to 3

Range of n = 4 bit = -7 to 7

Range of n + 1 = 5 bit = -15 to 15 // capable of handling overflow

Range of n + 2 = 6 bit = -31 to 31 // capable of handling overflow

Minimum number of bit needed = 5 = n + 1

I implies II means ≡ I → II

${X^{ - 1}} = \frac{{{\rm{Adj}}\left( {\rm{X}} \right)}}{{\left| X \right|}}$

If |X| ≠ 0 then X^-1

$\left| X \right| = \frac{{Adj\left( X \right)}}{{{X^{ - 1}}}}$

If X^-1 then |X| ≠ 0 also |Adj X| = |X|^{n - 1} then |Adj X| ≠ 0

If X^-1 then |X| ≠ 0

I implies II and II implies I

∴ Both I and II are equivalent

Note:

X^-1 means X is invertible

|X| determinant of X

∀ a, b ∈G, aR₁b iff ∃g ∈ G such that a=g⁻¹bg

Reflexive:

aR₁a

a=g⁻¹ag

ga=gg⁻¹ag //Left multiplication by g

gag⁻¹=agg⁻¹ //Right multiplication by g

gag⁻¹=a

a = gag⁻¹

we have aR₁a. So, the relation is reflexive.

Symmetric:

If aR₁b, then ∃g ∈ G such that gag⁻¹ = b then a=g⁻¹bg, so bR₁a. Hence the relation is symmetric.

Transitive:

If aR₁b and bR₁c there are g, h ∈ G such that b=gag⁻¹ and c=hbh⁻¹. Then c = hga(hg)⁻¹ so aR1c.

Hence the relation is transitive.

R1 is an equivalence relation.

∀ a, b ∈ G, aR₂b iff ∃g ∈ G such that a=b⁻¹

Reflexive:

aR₂a,

a=a⁻¹. this may not be true. So, the relation is not reflexive.

R₂ is not an equivalence relation.

R₁ is true and R₂ is false.

Strict 2PL allows only schedules whose precedence graph is acyclic i.e. schedule is Conflict Serial.

In 2PL, transactions do not release exclusive locks until the transaction has committed or aborted i.e. schedule is recoverable.

Time stamp ordering schedule with Thomas write rule generate View serial schedule with BLIND WRITE. Because of BLIND WRITE it won't be Conflict Serial.

Option 3 is correct.

A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit.

In Hamiltonian cycle is a Hamiltonian circuit in which initial and final vertex are same.

In an undirected complete graph on n vertices, there are n permutations are possible to visit every node. But from these permutations, there are: n different places (i.e., nodes) you can start; two (clockwise or anticlockwise) different directions you can travel. So, any one of these n! cycles is in a set of 2n cycles which all contain the same set of edges.

So, there are = $\frac{{n!}}{{2n}} = \frac{{\left( {n - 1} \right)!}}{2}$ distinct Hamilton cycles.

\(\begin{array}{*{20}{c}} {{\rm{lim}}}\ {x \to 3} \end{array}\frac{{{x^4} - 81}}{{2{x^2} - 5x - 3}}\)

$\frac{{{3^4} - 81}}{{{{2.3}^2} - 5.3 - 3}} = \frac{0}{0}$

Applying L Hospital’s rule

\(\begin{array}{*{20}{c}} {{\rm{lim}}}\ {x \to 3} \end{array}\frac{{4{x^3}}}{{4x - 5}}\)

$\frac{{{{4.3}^3}}}{{4.3 - 5}} = \frac{{108}}{7}$

Properties of B+ trees:

• B+ tree is height balance tree.
• Non leaf node has pointer to a node (leaf or non-leaf) and not pointer to data record
• Key value in each node is in sorted order.
• Leaf node has pointer to next leaf node.

Structure of non-leaf(internal) node of B+ tree:

Structure of leaf of B+ tree:

Option 2 is not correct.

Regular language L = {x|x = a^2+3k or x = b^10+12k k ≥ 0}.

L = {a², a⁵, a⁸, a¹¹ … ∪ b¹⁰, b²², b³⁴…}

Pumping Lemma:

Let L be an infinite regular language. Then there exists some positive integer m such that any w ϵ L with |w|≥ m can be decomposed as

w = xyz

with |xy|≤ m such that w_i = xyⁱz

is also L for all i = 0, 1, 2, …

Therefore, minimum Pumping Length should be 11, because string with length 10 (i.e., w = b¹⁰) does not repeat anything, but string with length 11 (i.e., w = b¹¹) will repeat states.

Hence option 1, 2, and 3 are eliminated.

Therefore 24 can be the pumping lemma length.

• Simple Mail Transfer Protocol (SMTP) is the standard protocol for sending emails across the Internet.

• IMAP and POP3 are the Internet mail protocols used for retrieving emails.

• MIME allows the users to exchange different kinds of data files in an email: audio, video, images, etc.

• SMPT, POP3 and SMTP, IMAP are the possible correct answer in which only SMTP, POP3 is present in option 2.

Let us consider n = 1

Since n > 0 else part gets executed

convert(1/2) = convert(0) // integer division in C

Now**, n = 0**

But base condition is n < 0 again else part gets executed

convert(0/2) = convert(0) // recursive calls until stack memory gets exhausted

This code will never satisfy base condition and will not terminate until stack memory gets exhausted

Since this option is not available choose the best possible option

Option d → “It will not print anything and will not terminate”

It is partially correct since it will not print anything but also gets terminated

Note:

Answer key in GATE 2019: D

Output of the code is 52.

Important Points:

Initialization statement is executed only once.

Incremental statement is executed at the end of every iteration

Subnet mask: 255.255.255.252→ 1111 1111. 1111 1111. 1111 1111. 1111 1100

M’s IP address: 100.10.5.2 →        0110 0100. 0000 1010. 0000 0101. 0000 0010

Subnet Mask & M’s IP address → 0110 0100. 0000 1010. 0000 0101. 0000 0000

∴ Subnet Id = 100.10.5.0

N’s IP address: 100.10.5.5 →        0110 0100. 0000 1010. 0000 0101. 0000 0101

Subnet Mask & N’s IP address → 0110 0100. 0000 1010. 0000 0101. 0000 0100

∴ Subnet Id = 100.10.5.4

P’s IP address: 100.10.5.6 →        0110 0100. 0000 1010. 0000 0101. 0000 0110

Subnet Mask & P’s IP address → 0110 0100. 0000 1010. 0000 0101. 0000 0100

∴ Subnet Id = 100.10.5.4

N and P belongs to same subnet 100.10.5.4

Tips and Tricks:

& → bitwise AND

Since Network Mask is 255.255.255.252, not have to check first 3-byte because subnet id will same as first 3 byte of IP address. Only 4th byte need to bitwise AND with given IP address

• It is mentioned that X (source) and Y (destination) both are in the same subnet. Therefore, local gateways aren’t needed.
• The sender (X) knows its own IP address and MAC address. X also knows the IP address of the target (Y). Find MAC address of Y.
• IP asks ARP to create an ARP request message, filling in X's IP and MAC address and Y's IP address. The destination MAC address is set to all 0’s.
• The message is passed to Data Link layer where it is encapsulated in a frame using MAC address of X as the source address and physical broadcast address (FF:FF:FF:FF:FF:FF)  as the destination address.
• Every host in subnet receives the request message because we have used broadcast MAC address in the destination address. All machines except Y (we have specified Y's IP address in our ARP request message) drop the ARP request message.
• Y replies with an ARP reply message that contains its MAC address. When X receives this message, it gets to know the MAC address of Y.

Important Points:

Host uses its own IP address and network mask to decide if target IP address is in its own network or not.

If it is in its network, it uses ARP to resolve the MAC address.

If target IP address is not in its network, it takes the help of default gateway to resolve MAC address using ARP.

Let X = f₁.f₂

= (0, 2, 5, 8, 14).(2, 3, 6, 8, 14, 15)

= (2, 8, 14)

X ⊕ f₃

= (2, 8, 14) ⊕ (2, 7, 11, 14)

= (2, 8, 14).(2, 7, 11, 14)’ + (2, 8, 14)’.(2, 7, 11, 14)

= (2, 8, 14).(0, 1, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15) + (0, 1, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15).(2, 7, 11, 14)

= (8) + (7, 11)

=(7, 8, 11)

(f₁.f₂) ⊕ f₃ = ∑ (7, 8, 11)

• {waⁿbⁿw^R |w ϵ {a, b}^*, n ≥ 0} is accepted by a non-deterministic pushdown automaton and hence it is a context-free language
• {ww^R |w ϵ {a, b}^*} is accepted by a non-deterministic pushdown automaton and hence it is context-free language.
• {waⁿw^Rbⁿ|w ϵ {a, b}^*, n ≥ 0} is not accepted by a pushdown automaton and hence it is not a context-free language.
• i = n, 2n, 3n, 4n, etc. forms and arithmetic series. aⁿbⁿ, aⁿb²ⁿ and aⁿb³ⁿ is accepted by a deterministic pushdown automaton and context-free language are closed under union and hence aⁿbⁿ ∪ aⁿb²ⁿ ∪ aⁿb³ⁿ is a context-free language. Hence {aⁿbⁱ |i ϵ {n, 3n, 5n}, n ≥ 0} is a context-free language.

X = (PQRS)

Set of functional dependencies

F = {QR → S, R → P, S → Q}

QR → {Q, R, S, P}

SR → {S, R, P, Q}

QR and SR are keys of Relation schema X

R → P …

part of key (R) → non key(P)

It is partial dependency and hence not in 2^nd normal form and therefore not in BCNF (Given)

X is decomposed into two schemas Y and Z, where Y = (PR) and Z = (QRS)

For Y = (PR)

R → P

Y is in BCNF because binary attribute (R is a key).

For Z = (QRS)

QR → S

S → Q

SR → {R, S, Q}

QR → {R, Q, S}

QR and SR are keys of Relation schema X

Z is not in BCNF because

S → Q and S is not Super key.

∴ statement I is incorrect

Dependency Preserving:

R → P is in Y

QR → S in Z

S → Q is in Z

Hence, it is dependency preserving.

Lossless:

Y ∩ Z = R which is key of Y.

Therefore, it is Lossless

Statement II is correct.

Hence, option 3 is the answer

Memory is word addressable.

1 word = 4 bytes

Virtual Address (VA) = 64 bits

∴ Virtual Address Space (VAS)= 2⁶⁴ words

Physical Address (PA) = 48 bits

∴ Physical Address Space (PAS) = 2⁴⁸ words

Page size (PS) = 8 KB = 2¹¹ words

∴ page offset = 11 bit

∴ number of pages possible = $\frac{{VAS}}{{PS}} = \frac{{{2^{64}}}}{{{2^{11}}}} = {2^{53}}$

∴ number of frames possible = $\frac{{PAS}}{{PS}} = \frac{{{2^{48}}}}{{{2^{11}}}} = {2^{37}}$

VA = Page number + page offset

Translation Lookaside Buffer (TLB)

Entries in TLB = 128 = 2⁷

If a page number is found in TLB then there will be a hit for all the words (Word addresses) of that Page.

1 - page hit implies 2¹¹ distinct virtual address hits.

So 2⁷page hit implies 2⁷ × 2¹¹=2⁸ × 2¹⁰= 256 × 2¹⁰ virtual address hits.

Therefore, at most 256 × 2¹⁰ distinct virtual addresses can be translated without any TLB miss.

Tips and Tricks:

distinct virtual addresses can be translated without any TLB miss is

the number of entries in TLB × page size

• Every Recursively enumerable language has a Turing Machine, and a set of all Turing Machine's is countable. Therefore, the set of all Recursively enumerable languages is countable.
• There exists a one to one equivalence for all valid C programs and all valid TM encodings. Since the set of all valid TM encodings is countable, it means that the set of all syntactically valid C programs is also countable.
• Set of all languages is uncountable and the set of all Regular Languages is countable. So, the set of all non-regular languages should be uncountable as the union of two countable sets cannot make an uncountable set.

S3 and S4 are uncountable sets.

Important Points:

Every TM can be encoded with 0's and 1's, that is, every TM can be represented by a unique binary number.

Σ = {0,1} then set of all binary strings = Σ^∗. Σ^∗ is countable → Set of all TM's is countable.

∀x [(∀z z|x ⇒ ((z=x) ∨ (z=1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒((w=z) V (z=1)))]

Let, X ≡ (∀z z|x ⇒ ((z =x) ∨ (z=1)))

Y ≡ ∃w (w > x)

Z ≡ (∀z z|w ⇒ ((w = z) ∨ (z=1))

∀x [X ⇒ Y ⇒ Z]

X is true: If x is prime number

Y is true: If there exist a w which is greater than x

Z is true. If w is prime

S1 = {1,2,3, ... , 100}

Let x = 97

z = 97

∴ z|x ⇒ (z = 1) ≡ T ⇒ T ≡ T

prime number greater than 97 is 101

But S1 is not included in set. Hence there doesn’t exist w which is greater than x

T ⇒ F.Z ≡ T ⇒ F ≡ F

Therefore, S1 does not satisfy φ

S2. Set of all positive integers satisfy φ

S3. Set of all integers

If x is negative, X ≡ T

F ⇒ Y.Z ≡ T

Also, set of all positive integers satisfy φ

Therefore, option 3 is correct.

Concepts:

Synthesized attributes:

A Synthesized attribute is an attribute of the non-terminal on the left-hand side of a production. Synthesized attributes represent information that is being passed up the parse tree. The attribute can take value only from its children.

S-attributed SDT

If an SDT uses only synthesized attributes, it is called as S-attributed SDT.

Inherited attributes:

An attribute of a nonterminal on the right-hand side of a production is called an inherited attribute. The attribute can take value either from its parent or from its siblings.

L-attributed SDT

If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT.

In SDT:

D → T L {X₁.type = X₂.type}

L.type = T.type (Inherited attributed )

∴ X₁ = L and X₂ = T

T can be int or float

In SDT:

L → L₁, id {X₃.type = X₄.type}

L₁.type = L.type (Inherited attributed)

∴ X₃ = L₁ and X₄ = L

Hence option 1 is correct.

Total number of unsorted arrays is n and each array contain n distinct element.

Time complexity to find median from an array is O(n).

Since there is ‘n’ such array. Therefore, total time complexity to find medians of all arrays is O(n²)

Store the ‘n’ medians in an array. Find the medians of the array with time complexity of 0(n)

Total Time complexity:

T(n) = O(n²) + O(n) = O(n²)

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.

I. G has a unique minimum spanning tree if no two edges of G have the same weight

This statement is true.

Example:

Graph G(V, E)

G(V, V – 1) → minimum spanning tree

If edge weights are distinct then there exist unique MST.

II. G has a unique minimum spanning tree if, for every cut of G, there is a unique minimum-weight edge crossing the cut

This statement is also true.

Theorem:

If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree, but converse may not be true.

The cut property states that if an edge has the minimum weight among all the edges crossing a particular cut in the graph, then it will be part of any minimum spanning tree. If, for every cut in the graph, there is a unique minimum-weight edge crossing that cut, then there can be only one set of edges that forms the minimum spanning tree. This ensures the uniqueness of the minimum spanning tree in the graph.

Hence, the correct answer is option 3.

All instances of ‘R’ are currently in use. Therefore, available resource = 0

Additional need of process p and q are 0. Therefore, process p and q will release the instances X_p and X_q held by it after its execution.

Available resource = X_p + X_q

To guarantees that no other process apart from p and q can complete execution

Available Resource < minimum of additional resource needed

X_p + X_q < Min {Y_k | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

Correct answer is 

 Key Points

I. The smallest element in a max-heap is always at a leaf node - This statement is generally true. A max-heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, for any given node I, the value of I is greater than or equal to the values of its children. Therefore, in general, the leaf nodes should contain the smallest elements. However, the smallest element isn't guaranteed to be in a specific leaf node; it could be in any of the leaf nodes.

II. The second largest element in a max-heap is always a child of the root node - This statement is true. In a max heap, the root node is the maximum element, and its children are the next candidates for the maximum values. Therefore, the second largest element must be a child of the root node.

III. A max-heap can be constructed from a binary search tree in Θ(n) time - This statement is true. A binary search tree can be traversed in-order to create a sorted list in Θ(n) time. Then we can build a max-heap from this sorted list in Θ(n) time.

IV. A binary search tree can be constructed from a max-heap in Θ(n) time - This statement is false. Constructing a binary search tree from a heap is more complex and would take O(n log n) time because each insertion into a binary search tree can take up to O(log n) time and there are n such insertions, hence resulting in O(n log n) time complexity.

So, the true statements are I, II, and III.

Additional Information

Max-heap: 

• Smallest element (12) of the max heap is always at the leaf.
• Second largest element (25) in a max heap is always a child of the root node

Binary Search Tree:

INORDER: 14, 15, 18, 20, 22, 23, 25, 30

Traversal time complexity = O(n)

Store the element in an array in reverse order

Filling the array in reverse order. Time complexity = Θ(n)

Total time complexity = Θ(n) + Θ(n) = Θ(n)

MAX heap:

Statement I, II and III are correct

Important Points:

A binary search tree can be constructed from a max heap in Θ(n²) time

Assume that distinct elements are present