GATE CS 2020 Official Paper (Previous Year Paper)

The correct answer is Option 4) i.e. within, for

After reading the sentence we can easily comprehend that Raman is confident that he will be able to speak English under a certain time limit, so we need a Preposition that will convey this meaning. The available options for the first blank are 'for', 'during' and 'within', we can easily negate for and during because 'for' is used to represent a duration of time and 'during' is any time between the start and finish of a set length of time. Hence, we are left with 'within' which is the most appropriate choice as it means under a certain time limit.

Now for the second blank 'for' is the most apt option because 'last three weeks' is a duration of time and we use "For" when we measure the duration – when we say how long something lasts.

Complete Sentence: Raman is confident of speaking English within six months as he has been practising regularly for the last three weeks.

The correct answer is Option 1) i.e. extremely poor

In the sentence given above, we have two independent clauses which are joint by coordinating conjunction 'but'. The word 'but' is one of the seven coordinating conjunctions in English (the others are and, or, so, for, nor, and yet). It’s used to connect two statements that contrast or contradict each other in some way. Now the first part of the sentence is positive in nature so the second part must contradict this, so the only contradicting option we have is 'extremely poor'.

Let's see some examples in order to develop more clarity:

• learning Mathematics is difficult but fun!
• She is the smartest girl in the class but I don't like her.

Complete Sentence: His knowledge of the subject was excellent but his classroom performance was extremely poor.

The correct answer is option 1) i.e. Flyer.

From the first part of the analogy, we can conclude that a noun is needed after its corresponding verb. Similarly, 'fly' is our verb and we need a corresponding noun i.e. 'flyer' ( flying and flew is a verb and flighter is not a word).

The noun form of the verb 'Fly' is 'Flyer'. 

Hence it is the correct fit in the second part of the given analogy.

The correct answer is option 4) i.e. Billions of people are affected by melting glaciers.​ 

• Option 1 can be negated from the get-go as there is nothing conclusive about this statement, the statement "Nation-states do not have environmental concerns" is no-where mentioned in the passage. The passage is just suggesting that nation-states need to rethink their carbon footprint for political concerns, if not for environmental ones.
• Option 2 can be negated in a similar fashion as the nation-states are only accountable for man-made emissions and reducing carbon footprint as per the passage.
• Option 3 can be negated as nothing is mentioned in the passage that Billions of people are responsible for man-made emissions.
  

Option 4 follows directly from the first sentence of the passage. *"*The dawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for freshwater." After reading this sentence we can conclude that billions of people are affected by melting glaciers as they depend on it.

Option 1: 1-a-c-2

Total cost = 200 + 100 + 100 = 400

Option 2: 1-f-b-2

Total cost = 100 + 0 + 200 = 300

Option 3: 1-b-2

Total cost = 300 + 200 = 500

Option 4: 1-f-e-2

Total cost = 100 + 100 + 200 = 400

Therefore, the cheapest route from node 1 to node 2 is 1-f-b-2.

Explanation:

The correct answer is option 4) i.e. GST is imposed at the point of usage of goods and services.​ 

• Option 1 can be negated from the get-go as GST is not imposed on production, it is imposed on the supply of goods and services.
• Option 2 can be negated in a similar fashion as the GST subsumes all indirect taxes except few.
• Option 3 can be negated as it has been mentioned clearly in the passage that- "GST also has a few components specific to state governments, central government and Union Territories (UTs)."

Option 4 follows directly from the second line of the passage. "It is a destination-based tax imposed on goods and services used,".** Here the term "at the point of usage of goods and services." implies that it is a destination-based tax.

 Q + S = 9 + 81 = 90

Area of a circle with radius a = πa²

Area of a circle with radius b = πb2

The diameter of the shaded circle = (b - a) 

Area of shaded circle = $\pi(\frac{b-a}{2})^2 = \pi \frac{(b-a)^2}{4}$

Painted area = total area of shaded circle = $n \pi \frac{(b-a)^2}{4}$

Area of angular space =  πb2  – πa2 = π (b2 – a2 )

Area of angular space = Painted area  + Unpainted area

Unpainted area = Area of angular space – Painted area

Unpainted area = $\pi (b^2 - a^2) -n \pi \frac{(b-a)^2}{4}$

Unpainted area = $\pi[(b^2 -a^2) - \frac{n}{4}(b-a)^2]$

Concept:

The sum of the interior angles of a triangle is equal to 180^o

Straight lines perpendicular to each other in an X-Y plane

Calculation:

A + α + β = 180^o

90^o + α + β = 180o

α + β = 90o

Data:

Expenditure per year = 500 × 10⁶ Rs.

Revenue in 2014 = 500 × 10⁶ Rs.

Revenue in 2015 = 700 × 10⁶ Rs.

Revenue in 2016 = 800 × 10⁶ Rs.

Revenue in 2017 = 600 × 10⁶ Rs.

Revenue in 2018 = 400 × 10⁶ Rs.

Formula:

% profit = $\frac{Total ; profit}{Total ; expenditure} \times 100$

Calculation

Total expenditure = number of years × expenditure per year

∴ Total expenditure = 5 × 500 × 10⁶ = 2500 × 10⁶ Rs.

Total Revenue = (500 + 700 + 800 + 600 + 400) × 10⁶ Rs.

∴ Total Revenue = 3000 × 10⁶ Rs

Total profit = Total Revenue - Total expenditure = 500 × 106

% profit = $\frac{500 \times 10^6}{2500 \times 10^6} \times 100 = 20$

Concept:

A function f(x) is said to be increasing in the given interval if it’s first order differential $f'\left( x \right) \ge 0$ holds for every point in the given interval.

Calculation:

Function I:

$f\left( x \right) = {e^{ - x}}\therefore f'\left( x \right) = ; - {e^{ - x}}$

$\because {f'}\left( 0 \right) = - 1 < 0$

Therefore, the function is non increasing.        

Function II:

$f\left( x \right) = ;{x^2} - \sin x,;f'\left( x \right) = 2x - \cos x$

$f'\left( 0 \right) = ;0 - \cos 0 = - 1 < 0$

Therefore, this function is also non increasing.

Furthermore, since cosine function is periodic function, it cannot be strictly increasing in the given range

Function III:

$f\left( x \right) = \sqrt {{x^3} + 1}$

${\rm{f'}}\left( {\rm{x}} \right) = \frac{{3{x^2}}}{{2\sqrt {{x^3} + 1} }}$

$f'\left( 0 \right) = 0,;f'\left( 1 \right) > 0$

Therefore, the function is increasing in the given interval.

Therefore $f\left( x \right) = \sqrt {{x^3} + 1}$ function is the only increasing everywhere in [0, 1]

Hence Option(1) is the correct answer.

Recurrence relation:

$T\left( n \right) = T\left( {{n^{\frac{1}{{\rm{a}}}}}} \right) + 1,{\rm{;}}T\left( b \right) = 1$

where ‘a’ and ‘b’ are parameters of order ω(1)

Using substitution method to solve recurrences,

${\rm{T}}\left( {\rm{n}} \right) = {\rm{;T}}\left( {{{\rm{n}}^{\frac{1}{a}}}} \right) + 1$

$= {\rm{T}}\left( {\left( {{{\rm{n}}^{\frac{1}{{{{\rm{a}}^2}}}}}} \right) + 1} \right) + 1$ 

$= {\rm{T}}\left( {{{\rm{n}}^{\frac{1}{{{{\rm{a}}^2}}}}}} \right) + 2$ 

$= \left( {{\rm{T}}\left( {{{\rm{n}}^{\frac{1}{{{{\rm{a}}^3}}}}}} \right) + 1} \right) + 2$ 

$= {\rm{T}}\left( {{\rm{n}}\frac{1}{{{{\rm{a}}^3}}}} \right) + 3$ 

Continuing this for ‘m’ iterations, we get

${\rm{T}}\left( {\rm{n}} \right) = {\rm{T}}\left( {{{\rm{n}}^{\frac{1}{{{{\rm{a}}^{\rm{m}}}}}}}} \right) + {\rm{m}}$ 

Put $\left( {{n^{\frac{1}{{{a^m}}}}}} \right) = b$

Taking log on both sides

$\frac{1}{{{a^m}}}\log n = \log b$ 

${a^m} = \frac{{\log n}}{{\log b}}$

$m = lo{g_a}lo{g_b};n$

Now,

$T\left( n \right) = T\left( {{n^{\frac{1}{{{a^m}}}}}} \right) + m$ 

$T\left( n \right) = {\rm{;}}b + ;lo{g_a}lo{g_b};n$

So, the asymptotic order of T(n) is Θ(log_alog_b n)

Statement I: TRUE

In daisy chaining method of interrupt handling, the devices are connected serially in such a manner that nearest device to the CPU has the highest priority, followed by the next device and so on.

Statement II: FALSE

In vectored interrupt, vector address is given to the CPU to identify the source of interrupt. For example, in 8085 µP, RST 4.5 is a vectored interrupt. Here, 4.5 is the interrupt vector which gives the vector address as 4.5 × 8 = (36)₁₀ = (0024)₁₆

Statement III: TRUE.

In polling method, the CPU polls each device to check status bits to find out if the device has raised any interrupt. It is a software method.

Statement IV: FALSE

In DMA mode, either the CPU or the DMA controller would gain control of the system bus a time, but not both. Accordingly, the CPU would be either in busy state or Hold state. It would be in busy state until I/O device prepares the data and would go to Hold state when I/O device starts transferring data to main memory via DMA controller.

Concept:

While executing a micro-instruction such as R0 ← R1 + R2, the CPU performs various micro-operations. Each of this micro-operation is performed in one time cycle.

Execution:

Step 1:

Fetch the instruction. Initially, the address of the instruction to be executed in Program Counter (PC). It is moved from PC to Memory Address Register (MAR). This is done via micro-operation PC_r, MAR_w, MEM_r

Step 2:

Once the instruction has been fetched, in next single time cycle, it is placed into Memory Data Register (MDR) and then to Instruction Register (IR). This is done via micro-operation MDR_r, IR_w

Step 3:

Operand Fetching and Decoding of contents from Register R1 and place it into temporary register Temp₁ via micro- operation R1_r, TEMP1_w

Step 4:

Contents of Register R2 is decoded and ALU performs the addition of fetched content of Temp1 and R2 and place it into Temp2 via micro-operation R2_r, TEMP1_f, ALU_add, TEMP2_w

Step 5:

Finally, the content of Temp₂ is moved into the target register R₀ via micro-operation TEMP2_r, R0_w

Concept:

A binary tree can be traversed in three ways:

1. Preorder = (Root, Left subtree, Right Subtree)
2. Inorder = (Left subtree, Root, Right Subtree)
3. Postorder = (Left Subtree, Right subtree, Root)

 

Explanation:

In case of Binary Search Trees (BST), inorder traversal always sorts the tree nodes into ascending order.

Inorder traversal is 10, 11, 12, 15, 16, 18, 19, 20

Pre-order traversal is 15, 10, 12, 11, 20, 18, 16, 19.

In preorder traversal, the first node would be tree root and values less than root would be part of left

subtree and values greater than root node would form right subtree. So the resultant BST is:

Required Binary Search Tree:

Post order traversal: 11, 12, 10, 16, 19, 18, 20, 15

Concept:

AVL tree is a height balanced binary search tree.

Insertion in AVL takes Θ (log n) time and height of an AVL tree with n nodes is log n.

Calculation:

The given AVL tree already has n nodes. Now each successive insertion would involve two operations: Θ(log n) to find the appropriate place to insert and another Θ(log n) to do any rotation if required. So in worst case, each successive insertion requires 2 log n operation i.e. Θ (log n).

Therefore, n² insertions would require Θ (n² log n).

Concept:

The regular expression should generate all possible binary strings with odd number of 1’s and doesn’t generate the other strings.

Option 1: Incorrect

Regular Expression: ((0 + 1)*1(0 + 1)*1)10

String: 11110

It can generate strings (11110) with even number of 1’s also

Option 2: Incorrect

Regular Expression: (01010*)01

It will generate string only ending with ‘1’

String: 1110

It cannot generate ‘1110’ substring.

Option 3: Incorrect

Regular Expression: 10*(01010*)*

It will generate string only starting with ‘1’

String: 0111

It cannot generate ‘0111’ substring.

Option 4: Correct

Regular expression: 0*(1010)10

It will generate all possible binary strings with odd number of 1’s and doesn’t generate the other strings.

Note:

Option 4 has been changed, since none of the option is was correct in official GATE CS 2020 paper

Marks has been given to all.

Statement I: FALSE

If L₁ ∪ L₂ is regular, then neither L₁ nor L₂ needs necessarily be regular.

Example:

Assume L₁= {aⁿ bⁿ, n ≥ 0} over the alphabet {a, b} and L₂ be the complement of L₁.

Neither L₁ nor L₂ is regular (both are DCFL) but L₁ ∪ L₂= {aⁿ bⁿ} ∪ {aⁿ bⁿ}^c = (a + b)^* is regular.

Statement II: FALSE. The infinite Union of regular languages is not regular.

Example:

Given alphabet {a, b}.

L₁= {ε}

L₂= {ab}

L₃= {aabb}

L₄= {aaabbb}

:

:

L = L₁ ∪ L₂ ∪ L₃ ∪ L₄ …

Each of the above are regular but their infinite Union gives L₁= {aⁿ bⁿ, n ≥ 0} which is not regular but DCFL.

Note:

DCFL → Deterministic context free language

Statement I: FALSE

Symbol table is the data structure, which is used in all phase, that is, from lexical analysis till code generation and optimization.

Statement II: FALSE

Recursion mandatorily requires stack memory during the runtime environment, not heap memory.

Statement III: FALSE.

Error such as ‘any variable must be declared before its use’ is semantic error and thus cannot be detected during syntax analysis.

Concept:

Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.

Explanation:

Statement I: TRUE.

L = {aⁿ |n ≥ 0} ∪ {aⁿbⁿ| n ≥ 0}

{aⁿ |n ≥ 0} is a regular language and {aⁿbⁿ| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Statement II: FALSE.

L is DCFL then it is CFL too.

Statement III: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from aⁿ or from aⁿbⁿ. Both have a common prefix.

Concept:

Best fit allocation:

The best fit allocation strategy chooses the smallest available memory partition that can satisfy the memory requirement. It creates the smallest hole.

First fit allocation:

The first fit chooses the first available memory partition that can satisfy the requirement.

Worst fit allocation:

The worst fit allocation strategy chooses the largest available memory partition that can satisfy the memory requirement. It creates the largest hole.

Next fit allocation:

It works same as First Fit, the only difference it maintain a pointer to all last allocated memory space to the process and begins it search from there if new request is arrived, unlike first fit which start will initial memory space.

Explanation:

Option 1 and Option 4 : FALSE

The hole created by first fit may or may not be larger than the hole created by next fit

Option 2: FALSE

The hole created by worst fit is always larger than or equal to the hole created by first fit

Option 3: TRUE

The hole created by best fit could never be larger than the hole created by first fit.

 Although it may be equal.

A process state diagram for a pre-emptive scheduling is:

Statement I: TRUE

A process can move from running state to ready state on interrupt or when priority expires, that is, when it is pre-empted.

Statement II: TRUE

A ready process moves to running process when it is dispatched.

Statement III: FALSE

A blocked process that is in waiting state can never move directly to running state. It must go to ready queue first.

Statement IV: TRUE.

A blocked or waiting process can move to ready state.

Important Point:

The transition from running to ready state is possible only in pre-emptive scheduling. It cannot happen in non pre-emptive scheduling.

Inner Query: SELECT AVG (cost) FROM Cataloque WHERE pno = ‘P4’ GROUP BY pno

The execution of the inner query gives the average of the cost of parts with part-id P4

Output:

 

Outer Query:

SELECT s.sno, s.sname FROM Suppliers s, Cataloque c WHERE s.sno = c.sno AND Cost > (225)

The execution of the entire query output the following table:

 

Hence, there are 4 rows in the resultant table.

Concept: 

An entity set which has determined an attribute or set of attributes to be a primary key is called a strong entity set.

If an entity set does not have enough attributes to form a primary key, it is called a weak entity set.

Explanation:

In E-R diagram, the many-to-one relationship with a weak entity set is represented by diamond with double borders.

Important Point:

The relationship with weak entity set would be represented by diamonds with double/bold borders.

The weak entity set itself would be represented by rectangle with double/bold border.

Statement I is FALSE. An IP packet gets modified after router has processed it because the Time to Live (TTL) field in IP header is decremented by 1.

Statement II is TRUE. A router need not necessarily implement a routing protocol. If no routing protocol is specified for a router, default routing with address 0.0.0.0 is implemented.

Statement III is FALSE. Re-assembly of IP fragments into a single IP packet is done only at the receiver site.

The linked list needs to be maintained in sorted order: (insertion sort on linked list)

Assume the worst case comparison:

Elements are sorted in ascending order and linked list is singly.

Insert 1^st element:

1^st element is always sorted and hence no comparison

Insert 2^nd element:

2^nd element, 1 comparison is needed

Insert 3^rd element:

3^rd element, 2 comparison is needed

:

:

Insert n^th element:

n^th element, (n – 1)    comparison is needed

For comparison:

T(n₁) = 1 + 2 + … (n – 1 ) = $\frac{{{\rm{n}}\left( {{\rm{n}} - 1} \right)}}{2} = {\rm{\theta }}\left( {{{\rm{n}}^2}} \right)$

For insertion:

Also, for every insertion, time complexity is θ 1).

T(n₂) = θ(n)

T(n) = T(n₁) + T(n₂) = θ (n²) + θ (n)

∴ T(n) = θ (n²)

Important Point:

In elements are sorted in descending order, then to insert it will give best case θ (n), since each element will take θ(1) for comparison and θ (1) for insertion.

The decidability problem of Turing Machines can directly be determined using Rice’s theorem.

L1 is undecidable. According to Rice’s theorem, emptiness problem of Turing machine is undecidable.

L2 is decidable. This is because here we have to check whether the Turing machine reaches a particular step ‘q’ on a given input in finite steps or not. This is a decidable problem.

L3 is undecidable. There is no algorithm to computationally determine whether a Turing machine accepts a recursive language or not. Some Turing machines may accept recursive languages, while other may not.

L4 is also undecidable. According to Rice’s theorem, membership problem of Turing machine is undecidable.

Concept:

Properties of Rank:

Rank of a matrix is the number of independent rows in the given matrix. Given two square matrices A and B of order n × n, we have following properties:

1. Rank of product of A and B i.e. Rank (AB) ≥ Rank (A) + Rank (B) – order of square matrix 2. Rank of sum of A and B i.e. Rank (A + B) ≤ Rank (A) + Rank (B).

Properties of Determinant**:**

Given two square matrices A and B of order n × n and their determinants Det(A) and Det(B) respectively, determinant of their product i.e Det( AB) = Det(A) * Det(B). However, the same does not hold for the addition of the given matrices.

Example:

Consider two square matrices A and B each of order 2×2.

\(A = \left[ {\begin{array}{*{20}{c}} 2&1\ 3&4 \end{array}} \right]\)

Rank of A = 2

Det (A) = 5

\(B = \left[ {\begin{array}{*{20}{c}} 1&0\ 0&1 \end{array}} \right]\)

Rank of B = 2

Det (B) = 1

\(AB = \left[ {\begin{array}{{20}{c}} 2&1\ 3&4 \end{array}} \right] \times \left[ {\begin{array}{{20}{c}} 1&0\ 0&1 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 2&1\ 3&4 \end{array}} \right]\)

Rank (AB) = 2

Det (AB) = 5

\(A + B = ;\left[ {\begin{array}{{20}{c}} 2&1\ 3&4 \end{array}} \right] + \left[ {\begin{array}{{20}{c}} 1&0\ 0&1 \end{array}} \right] \)

\(A+B = ;\left[ {\begin{array}{*{20}{c}} 3&1\ 3&5 \end{array}} \right]\)

Rank of A+B = 2

Det (A+B) = 12

Statement I is FALSE.

The rank of product matrix AB is 2. Product of Rank(A) and Rank(B) is: 2*2 = 4. Therefore, the rank of the product matrix is not equal to the product of the rank of individual matrices.

Statement II is TRUE. 

Det(AB)= 5 = Det(A) * Det(B)

Statement III is TRUE.  

Rank(A + B) = 2. Sum of rank of A and B is: 2 + 2 = 4. Therefore, the relation: Rank (A + B) ≤ Rank (A) + Rank (B) holds true

Therefore, the rank of the addition matrix is less than or equal to the sum of the rank of the individual matrices.

Statement IV is FALSE.  

Det(A+B)= 12, which is greater than the sum of the determinants of individual matrices.

The given circuit gives the output:

Z(a, b, c) = \(a + ;\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftharpoonup$}} \over b} ;c\) 

Expanding it into canonical form to obtain the minterms

Z(a, b, c) = $a\left( {b + ;\bar b} \right)\left( {c + \bar c} \right) + \left( {a + \bar a} \right)\bar b;c$ 

= $abc + ab;\bar c + a\bar b;c + a\bar b\bar c + \bar a\bar b;c$

After rearranging the canonical terms, this corresponds to min-terms: ∑ (1,4, 5, 6, 7)

Alternate solution:

The output of the circuit is \(a + \mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\leftharpoonup$}} \over b} ;c\) 

K Map for this Boolean expression

The above K Map corresponds to min-terms: ∑ (1,4, 5, 6, 7)

Concept:

 In IEEE- 754 single precision format, a floating-point number is represented in 32 bits.

 

Sign bit value 0 means positive number, and 1 means a negative number.

The floating-point number can be obtained by formula: ± 1. M × 2^(E-127)

Data:

Content of R1: 0x 42200000               (0x means Hexadecimal notation)

Content of R2: 0x C1200000

Calculation:

Content of R1 in Hex (0x) is 42200000. After converting into binary, it can be represented in IEEE- 754 format as:

 

Sign bit is 0 i.e. the number is positive

Biased Exponent (E’) = 100 0010 0 = 132

Normalized Mantissa (M) = 010 0000 0000 0000 0000 0000 = .25

Therefore, the number in register R1 = + 1.25 * 2^(132-127) = 1.25 × 32 = 40

Content of R2 in Hex (0x) is C1200000. After converting into binary, it can be represented in IEEE- 754 format as:

 

Sign bit is 1 i.e. the number is negative

Biased Exponent (E’) = 100 0001 0 = 130

Normalized Mantissa (M) = 010 0000 0000 0000 0000 0000 = .25

Therefore, the number in register R1 = - 1.25 * 2^(130-127) = -1.25 * 8 = -10

R3 = R1/R2 = 40/-10 = -4

Since the number is negative, Sign bit (MSB) = 1

Converting 4 into binary of a floating point gives: (100.0)₂

Representing it into normalized form gives:  (1.000000….) × 2²

Therefore, Mantissa is 23 bits of all 0s

Biased Exponent (E’) = E+ 127 = 2+127 = 129 = (10000001)₂

It can be represented in IEEE- 754 format as:

 

Converting it into Hex format gives: 0x C0800000

Data:

Size of main memory: 16 MB

Size of cache memory: 64 KB

Block/line size: 256 B

The cache memory has been designed as 4- way set associative.

Calculation:

The memory is Byte- addressable.

Main memory size = 16 MB = 2²⁴ B. That means physical address generated by CPU would be represented

using 24 bits.

Cache memory size = 64 KB = 2¹⁶ B

Block size = 256 B = 2⁸ B. i.e. word would be represented by 8 bits

Therefore, Number of cache lines ÷ blocks = 2¹⁶ ÷ 2⁸ = 2⁸

Since, the cache memory is 4-way set associative.

Hence, number of sets = 2⁸ ÷ 2² = 2⁶. i.e. 6 bits would be required for set/index.

Therefore, Number of bits for tag = 24 – (6 +8) = 10 bits

Hence, the 24 bit address generated by CPU would have following components:

 

Physical Address A1 = 0x 42C8A4. Converting it into binary gives:

 

Physical Address A2 = 0x 546888. Converting it into binary gives:

 

Physical Address A3 = 0x 6A289C. Converting it into binary gives:

 

Physical Address A4 =0x 5E4880. Converting it into binary gives:

 

Thus it can be observed that A2 and A3 map to same set.

Also, address A1 and A4 map to same set.

Tips and Tricks:

The following approach should be adopted to quickly solve this question and save a lot of time:-

The number of bits for tag in a K- way set associative memory can be calculated directly as:

(log₂ (Main memory size in Bytes) – log₂ (Cache memory size in Bytes)) + log₂ K

Another thing is that the question is concerned only about the set number of the given addresses. So, we need not convert first two Hex digits of the given address into binary format, because they would be part of tag bits. Similarly, the last two Hex digits need not be converted into binary as they are part of Word/Offset. Only the middle two Hex digit needs to be converted into binary. And then the 6 LSBs can be compared to check if they represent the same set or not.

Concept:

The Minimum Spanning Tree (MST) of a graph G(V, E) with v vertices has (v-1) edges.

Explanation:

T is the MST of the given graph G and now a new edge has been added to G(V, E). Now there can be two scenarios:

Case I:

The edge weight of newly added edge (u, v) is greater than the weight of every edge in MST. In this case, MST would not be altered.  (Best Case scenario)

Case II:

The edge weight of newly added edge is less than any of the weights of the edges in MST ‘T’, in that case we would replace the maximum weighted edge in T with the new edge weight and then check if it forms a cycle (Worst case). Detection of cycle in a tree with V nodes can be done in O(V) time. This is because, the number of edges in T would always be (V-1)

Concept:

A language is regular if we could find a corresponding regular expression that generates it and an finite automata that accepts it. A language is CFL, if we could construct a Push Down Automata (PDA) that accepts it.

Explanation:

L₁ = {wxyx | w, x, y ϵ (0 + 1)⁺}

L₁ is a regular language.

Since it is given that w, x, y ϵ (0 + 1)⁺}, that means w, x, y all three can be strings of {0, 1}.

L1 can be generated by a regular expression of the form:

(0+1)⁺0 (0+1)⁺0 + (0+1)⁺1 (0+1)⁺1, by putting x as 0 and 1 alternatively. Since it can be represented as a regular expression, it is a regular language.

L₂ = {xy | x, y ϵ (a + b), |x| = |y|, x ≠ y}*

L₂ is a Context Free Language.

L₂ consists of set of strings which could be split into two non-identical substrings, but of equal length. Since comparison is involved, it cannot be done with a finite automata. However, a PDA can do comparisons, so PDA would accept the above language. Thus L₂ is a CFL.

Concept:

A rule is said to be L- attributed if it used both synthesized and inherited attributes. But, in the inherited attribute, we can get attribute values from the parent or from the left siblings, but not the right sibling.

Rule 1 is L- attributed.

Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s

Explanation:

P.i = A.i + 2     ...{This is an inherited attribute, as child P is getting value from parent A}

Q.i = P.i + A.i     ...{This is also inherited attribute and Q is getting value from parent P and left sibling A}

A.s = P.s + Q.s     ...{This is synthesized attribute as Parent A is taking values from children P and Q}

Rule 2 is not L- attributed

Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i

Explanation:

X.i = A.i + Y.s     ...{Child X is taking attribute value from parent A and right sibling Y}

Therefore, this violates the conditions of L- attributed definitions.

Explanation:

The key statement in the above code is wait (b). It will keep the remaining processes blocked until value on count becomes n. Once, the value of count = n, signal (b) would be executed and then a process can enter the code section Q. Thus, none of the process will execute Q until every process has executed code section P.

Stepwise Explanation:

Initialization:  a=1, b=0, count= 0

There are n processes say, P₁, P₂, P₃, ……………., P_n.

Let’s assume P1 has executed successfully the code section P and encounters the statements:

wait (a);      

Now, ‘a’ becomes 0, so all the subsequent processes are blocked.

b= 0, count= 0.

count=count+1 ;                          [ a=0, b=0, count=1]

if (count==n) signal (b) ;              [if condition not true, so statement will not be executed]

signal (a);                                        [a= 1, b=0, count= 1. Other processes can now execute Wait(a)]

wait (b) ;                                [ b= -1, therefore P1 also gets blocked and statement would not be executed]

signal (b);                             

This statement would only run if its preceding statement is executed, which in turn would only be executed if (count==n). Therefore, none of the process would execute Q until every process has successfully executed code section P.

Concept:

In the Shortest Seek Time First (SSTF) disk scheduling algorithm, the I/O request which requires the least disk arm movement, irrespective of the direction, from the current position is selected.

Explanation:

Given the disk head is currently at cylinder number 100. Using SSTF it would next serve the request id R with cylinder number 110, because it requires least amount of arm movement. After R being served, T would be served and so on, as shown below:

Statement I is TRUE.

Request T is serviced before request P.

Statement II is FALSE.

Q is serviced before S and after T.  

Statement III is TRUE.

The direction of disk arm movement changes between servicing of Q and P, as visible from the diagram.

Statement IV is TRUE.

R is serviced before P.

Concept:

A relation is in 1NF if every values in the relation are atomic.

A relation R with nontrivial functional dependency X → A, where X is not a superkey and A is a non-prime attribute and X is not a proper subset of any key is in called to be in 2NF.

A relation R with nontrivial functional dependency X → A, where X is not a superkey and A is a prime attribute, is called to be in 3NF.

A relation R with nontrivial functional dependency X → A, where X is a superkey is called to be in BCNF.

Explanation:

Statement I:

corresponds to a relation that is in 3NF but not in BCNF, because for BCNF, X must be a superkey.

Statement II

corresponds to a relation that is only in 2NF by definition.

Statement III

corresponds to a relation that is not even in 2NF. It is in 1NF.

Statement IV corresponds to a relation that is not even in 1NF.

Concept:

Two schedules S1 and S2 are termed to be conflict equivalent if the conflict operations in both the schedules are executed in same order. The conflict operations are identified by RW, WR, and WW pairs.

Explanation:

The given Schedule in question is:

       

 

 

 

 

 

 

 

 

 

 

 

The conflict pairs are:

 R2(B)-> W1(B)

 W2(B)-> W1(B)

R1(C)-> W2(C)

R2(D)-> W1(D)

The schedule in which these pairs are executed in the same order would be conflict equivalent to this given schedule.

Only the schedule in option 1 has all these 4 pairs in the same order of execution and thus is conflict equivalent to a given schedule.

Concept:

CIDR stands for Classless Inter Domain Routing. CIDR denotes the number of bits in the Netid.  Upon subnetting, any IP address consist of three subparts: Netid (bits for identifying the network), subnetid (bits for subnetting), and Hostid (bits for address allocation to hosts)

Calculation:

Given CIDR is 17, that means Netid=17.

There are 1500 devices, so the number of bits in Hostid= 11 (because 2¹¹ ≥ 1500)

Therefore, subnet bits= 32- (17+11) = 4

Hence, in any IP address in the given network, first 17 bits be part of network, next 4 of subnet ans last 11 bits would be for host address. Host bits should be all 0s

Address I: Cannot be allotted

202.61.84.0/21= 202.61. 0 1010 100.00000000. This address is not possible because the all the 11 host bits should be zero, but it contains a 1.

Address II: Can be allotted

202.61.104.0/21= 202.61. 0 1101 000.00000000. This address is possible as all the host bits are 0 and network bits are also satisfied.

Address III: Can be allotted

202.61.64.0/21= 202.61.0 1000 000.0000000. This address is possible as all the host bits are 0 and network bits are also satisfied

Address IV: Cannot be allotted

202.61.144.0/21= 202.61. 1 0010 000. 00000000. This address is not possible because bit in Netid has become 1.

Statement I:

∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W

This is logically valid. Because, W is free of any quantifier so, ∀x would be associated with p(x) only and hence L.H.S and R.H.S are equal.

Statement II:

Ǝx(p(x) ∧ W) ≡ Ǝx p(x) ∧ W

This also logically valid. Because, W is free of any quantifier so, Ǝx would be associated with p(x) only and hence L.H.S and R.H.S are equal.

Statement III:

∀x(p(x) → W) ≡ ∀x p(x) → W

This is logically NOT valid.

L.H.S: ∀x(p(x) → W

        = ∀x(¬ p(x) ∨ W)

        = ∀x (¬ p(x)) ∨ W

         = ¬ Ǝx p(x) ∨ W

         = Ǝx p(x) → W.

This is not equal to R.H.S

Statement IV:

Ǝx(p(x) → W) ≡ ∀x p(x) → W

This is logically valid.

L.H.S: Ǝx(p(x) → W)

       = Ǝx(¬ p(x) ∨ W)

      = Ǝx(¬ p(x)) ∨ W

      = ¬ ∀x p(x) ∨ W

      = ∀x p(x) → W = R.H.S

Shortest path will remain unchanged even if the weight functions are changed.

Hence option 1 is correct.

For the range [a, b], we first need to check if a and b are present in BST.

1. Time complexity to check if element ‘a’ is present in BST = O(log n)
2. Time complexity to check if element ‘b’ is present in BST = O(log n)

For finding all the elements in the range [a, b], we have to apply in-order sorting from a to b.

In this way, we will lay every successor of a reaching to the predecessor of b and all the elements between a and b will be reported.

For k elements, the in-order sorting will take O(k) time.

Hence, O(log n) + O(log n) + O(k) = O(2logn + k) = O(logn + k)