Official Paper

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

65 questions · 180 minutes · with answers · free

Attempt as Timed Mock Test

General Aptitude (10 questions)

1

The ratio of boys to girls in a class is 7 to 3.

Among the options below, an acceptable value for the total number of students in the class is:

  1. ((a))

    50

  2. ((b))

    37

  3. ((c))

    73

  4. ((d))

    21

Show Answer
Answer: ((a))

50

Given:

The ratio of boys and girls in a class is 7 : 3

Calculation:

Let be assume boys and girls in a class is 7x and 3x respectively.

⇒ The sum of boys and girls = 7x + 3x = 10x

⇒ The total number of strength of the class will be multiple of 10 so 50 will be the right answer

∴ The required result will be 50.

2

A polygon is convex if, for every pair of points, P and Q belonging to the polygon, the line segment PQ lies completely inside or on the polygon.

Which one of the following is NOT a convex polygon?

  1. ((a))

  2. ((b))

  3. ((c))

  4. ((d))

Show Answer
Answer: ((a))

Given:

Different types of figures

Calculation:

⇒ In any two points are inside in polygon, then line by joining these points will also be inside same polygon.

⇒ The polygon in the first image is not convex because if you take any two corner points then it will not be inside the polygon.

∴ The required result will be an option "1".

3

Consider the following sentences:

  1. Everybody in the class is prepared for the exam.
  2. Babu invited Danish to his home because he enjoys playing chess.

Which of the following is the CORRECT observation about the above two sentences?

  1. ((a))

    1 is grammatically correct and 2 is unambiguous

  2. ((b))

    1 is grammatically correct and 2 is ambiguous

  3. ((c))

    1 is grammatically incorrect and 2 is unambiguous

  4. ((d))

    1 is grammatically incorrect and 2 is ambiguous

Show Answer
Answer: ((b))

1 is grammatically correct and 2 is ambiguous

The correct answer is '1 is grammatically correct and 2 is ambiguous'.

Key Points

  • Everybody in the class is prepared for the exam. This statement i.e. statement 1 is grammatically correct.
  • Babu invited Danish to his home because he enjoys playing chess. This statement i.e. statement 2 is ambiguous as there is no guarantee that Danish knows playing chess. Moreover, it is stated that Babu invited Danish to his home but we can not conclude that he called him to play chess as it has been simply mentioned that Babu enjoys playing chess. There are many possible meanings or derivations of this statement.

Important Points

  • Ambiguous means having or expressing more than one possible meaning, sometimes intentionally.
4

A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse of folding, will look like ______.

  1. ((a))

  2. ((b))

  3. ((c))

  4. ((d))

Show Answer
Answer: ((d))

After unfolding the folded figure;

Hence, option (4) is the correct answer.

5

______ is to surgery as writer is to ______

Which one of the following options maintains a similar logical relation in the above sentence?

  1. ((a))

    Hospital, library

  2. ((b))

    Plan, outline

  3. ((c))

    Medicine, grammar

  4. ((d))

    Doctor, book

Show Answer
Answer: ((d))

Doctor, book

Doctor does surgery.

Similarly;

Writer writes book.

Hence, "Doctor, book" is the correct answer.

6

We have 2 rectangular sheets of paper. M and N, of dimensions 6 cm × 1 cm each. Sheet M is rolled to from an open cylinder by bringing the short edges of the sheet together. Sheet N is cut into equal patches and assembled to from the largest closed cube. Assuming the ends of the cylinder are closed, the ratio of the volume of the cylinder to that cube is ______

  1. ((a))

    3π\frac{3}{\pi }

  2. ((b))

    9π\frac{9}{\pi }

  3. ((c))

    π2\frac{\pi }{2}

  4. ((d))

    3π

Show Answer
Answer: ((b))

9π\frac{9}{\pi }

Given:

Two rectangular sheets M and N have the dimension 6 cm × 1 cm each,  in which cylinder will be formed by bringing the short edges of the sheet together. Given that ends of the cylinder are closed.

Concept:

Volume of cylinder = π × r2 × h

The volume of the cube = a3

Calculation:

Let be assume the side of the cube is a,

⇒ The area of the sheet N = 6 × a2

⇒ 6 × 1 = 6 × a2

⇒ a = 1

⇒ Volume of the cube = a3 = 13 = 1

⇒  The circumference  = 6

⇒ 2 × π × r = 6, r = 3/π and height of the cylinder = 1 cm

⇒ Volume of the cylinder = π × (3/π)2 × 1 = 9/π 

⇒ The required ratio = 9/π : 1

∴ The required result will be 9/π .

7
ItemsCost Rs.Profit %Marked Price Rs.
P5,400---5,860
Q---2510,000
<br>

Details of prices of two items P and Q are presented in the above table. The ratio of cost of item P to cost of item Q is 3 ∶ 4. Discount is calculated as the difference between the marked price and the selling price. The profit percentage is calculated as the ratio of the difference between selling price and cost, to the cost

(profit % = Selling price−CostCost\frac{{Selling \ price - Cost}}{{Cost}}× 100).

The discount on item Q, as a percentage of its marked price, is ______

  1. ((a))

    25

  2. ((b))

    12.5

  3. ((c))

    10

  4. ((d))

    5

Show Answer
Answer: ((c))

10

Given:

The Marked price of Q is 10,000

Calculation:

⇒ The cost price of Q = 5400 × (4/3) = 7200

⇒ The selling price of Q = 7200 × (5/4) = 90,00

⇒ Discount % on Q = (10000 - 9000)/10000 × (100) = 10%

∴ The required result will be 10%.

8

There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag.

The probability that at least two chocolates are identical is ______

  1. ((a))

    0.8125

  2. ((b))

    0.6976

  3. ((c))

    0.3024

  4. ((d))

    0.4235

Show Answer
Answer: ((b))

0.6976

Data:

To find the probability that no two chocolate are identical = P(k)

To find the probability that at least two chocolates are identical = P(x):

Formula:

P(x) = 1 - P(k)

Calculation

No two cholocate identical:

From 1st bag = Probability = 1010\frac{10}{10}

From 2nd bag = Probability = 910\frac{9}{10}

From 3rd bag = Probability = 810\frac{8}{10}

From 4th bag = Probability = 710\frac{7}{10}

From 5th bag = Probability = 610\frac{6}{10}

P(k) = 10×9×8×7×610×10×10×10×10=0.3024\frac{10 \times 9 \times 8 \times7\times6}{10\times 10 \times10 \times 10 \times10} = 0.3024

P(x) = 1 - P(k) = 1 - 0.3024

∴ The required result will be P(x) = 0.6976.

9

Given below are two statements 1 and 2, and two conclusions I and II.

Statement 1. All bacteria are microorganisms.

Statement 2. All pathogens are microorganisms

Conclusion I: Some pathogens are bacteria

Conclusion II: All pathogens are not bacteria.

Based on the above statements and conclusions, which one of the following options is logically CORRECT?

  1. ((a))

    Neither conclusion I nor II is correct.

  2. ((b))

    Only conclusion I is correct

  3. ((c))

    Either conclusion I or II is correct.

  4. ((d))

    Only conclusion II is correct

Show Answer
Answer: ((a))

Neither conclusion I nor II is correct.

The least possible Venn diagram is:

Conclusion I: Some pathogens are bacteria → False (There is no direct relation between bacteria and pathogens)

Conclusion II: All pathogens are not bacteria → False (There is no direct relation between bacteria and pathogens, No definite relation)

Hence, Neither I nor II is correct.

10

Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity: poverty and income inequality.

Which one of the following statements summarizes the passage?

  1. ((a))

    AOM are addressing the core problems and are likely to succeed.

  2. ((b))

    If obesity reduces, poverty will naturally reduce, since obesity causes poverty.

  3. ((c))

    The proposed AOM addresses the core problems that cause obesity.

  4. ((d))

    AOM are addressing the problem superficially.

Show Answer
Answer: ((d))

AOM are addressing the problem superficially.

The correct answer is AOM are addressing the problem superficially.

Key Points

  • The passage talks about the core problems that cause obesity: poverty and income inequality and how measures like AOM addresses such problems.
  • But, AOM are not addressing the main problems directly. It is a kind of generic step taken to address obesity. So, AOMs are addressing these problems superficially only and not addressing the real problems.
  • Thus, we can conclude that the statement - AOM are addressing the problem superficially, summarizes the passage.
  • Hence, option 4 is the most appropriate answer choice.

Computer Science and Information Technology (55 questions)

11

Suppose that L1 is a regular and L2 is a context-free language, Which one of the following languages is NOT necessarily context-free?

  1. ((a))

    L1 ⋅ L2

  2. ((b))

    L1 ∪ L2

  3. ((c))

    L1 ∩ L2

  4. ((d))

    L1 - L2

Show Answer
Answer: ((d))

L1 - L2

Concepts:

Operation under which context-free language is not closed: Intersection, complementation, set difference

Operation under which context-free language is closed: Union, Kleene Closure, and Concatenation.

Context-free language is closed under Intersection with regular language.

Explanation:

L1 is a regular and L2 is a context-free language.

Every regular language is context-free language.

Option 1: context-free language

L1.L2{L_1}.{L_2} it is the context-free language because it is closed under Concatenation.

Option 2:context-free language

L1 ∪ L2 it is the context-free language because it is closed under Union.

Option 3: context-free language

L1∩;L2{L_1} \cap ;{L_2} it is the context-free language because context-free language is closed under Intersection with regular language.

Option 4: may not be context-free language

L1 - L2  it may not be context-free language because it is not closed under complementation.

12

Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary of n elements. Which one of the following choices is correct?

  1. ((a))

    t > 2n - 2

  2. ((b))

    t>3⌈n2⌉t > 3\left\lceil {\frac{n}{2}} \right\rceil  and t ≤ 2n - 2

  3. ((c))

    t > n and t≤3⌈n2⌉t \le 3\left\lceil {\frac{n}{2}} \right\rceil

  4. ((d))

    t>⌈log⁡2(n)⌉t > \left\lceil {{{\log }_2}(n)} \right\rceil  and t ≤ n

Show Answer
Answer: ((c))

t > n and t≤3⌈n2⌉t \le 3\left\lceil {\frac{n}{2}} \right\rceil

Answer: Option 3

Explanation:

Recurrence Relation For no of comparison for finding Minimum and Maximum of an arbitrary array: T(n) = 2T(n/2) + 2 using divide and conquer tournament method.

after solving

T(n) =  3(n2)−23\left( {\frac{n}{2}} \right) - 2

(Worst case)

Option 1: t > 2n - 2

It is not correct.

Option 2: ​t>3⌈n2⌉t > 3\left\lceil {\frac{n}{2}} \right\rceil  and t ≤ 2n - 2

It is not correct. because lowest upper bound  t≤3⌈n2⌉t ≤ 3\left\lceil {\frac{n}{2}} \right\rceil

Option 3: t>n and t≤3⌈n2⌉t ≤ 3\left\lceil {\frac{n}{2}} \right\rceil

It is correct. at least n comparison required to find maximum and Minimum and max will be 3⌈n2⌉ 3\left\lceil {\frac{n}{2}} \right\rceil .

Option 4: t>⌈log⁡2(n)⌉t > \left\lceil {{{\log }_2}(n)} \right\rceil  and t≤ n

It is not correct.

13

Consider the following three functions.

f1 = 10n f2 = nlogn f3 = n√n

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

  1. ((a))

    f1 , f2, f3

  2. ((b))

    f2, f1, f3

  3. ((c))

    f3, f2, f1

  4. ((d))

    f2, f3, f1

Show Answer
Answer: ((d))

f2, f3, f1

Explanation:

f1 = 10n 

By taking log

f1 = n× log(10)

f2 = nlogn

By taking log

f2 = logn × logn

f3 = n√n

By taking log 

f3 = √n × logn 

asymptotic growth rate: f2 < f3  < f1

Therefore option 4 is correct

Important Points

Take n equal to very large number  to verify the result

14

Consider the following statements.

S1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.

S2 : The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?

  1. ((a))

    S1 is true and S2 is true

  2. ((b))

    S1 is false and S2 is true

  3. ((c))

    S1 is false and S2 is false

  4. ((d))

    S1 is true and S2 is false

Show Answer
Answer: ((a))

S1 is true and S2 is true

Answer: Option 1

Explanation:

Statement 1:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.

Consider following example 

Fun( int n )

{

 if( n==0 || n==1) 

  return n;

else {

return Fun(n/2) + Fun(n/2) ;

}

Suppose function call made as Fun(8). now recursion tree will be  

The Function call sequence will be (in terms of n): 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1 ( Same as pre-order traversal of the tree )

The Function Returning Sequence will be : 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8 ( Same as post-order traversal of the tree)

Hence This Statement is correct.

Statement 2:

This Statement is also correct.

15

Consider the following statements.

S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).

S2 : For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n.

Which one of the following option is correct?

  1. ((a))

    S1 is true and S2 is false

  2. ((b))

    S1 is false and S2 is true

  3. ((c))

    S1 is true and S2 is true

  4. ((d))

    S1 is false and S2 is false

Show Answer
Answer: ((c))

S1 is true and S2 is true

Answer: Option 1

Explanation:

Statement 1:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).

As you can see in the diagram Not all Unambiguous grammars are SLR(1) but All SLR(1) grammars are Unambiguous.

This Statement is True.

Statement 2:For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n.

This Statement is also True. There exists a standard algorithm for general Context-free grammars known as the CYK algorithm whose time complexity is O(n3).

Note:

  • LR parsers have linear time(O(n)) complexity.
16

Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?

  1. ((a))

    21

  2. ((b))

    528

  3. ((c))

    D2

  4. ((d))

    15

Show Answer
Answer: ((d))

15

Concept:

Step 1: Conversion: base 3 to decimal

Step 2: Conversion: decimal to Hexadecimal

Calculation:

Step 1:

Conversion: base 3 to decimal

(210)3 = 2 × 32 + 1 × 31 + 0 × 30

= 18 + 3 = 21

Step 2:

Conversion: decimal to Hexadecimal

1621
1615
01

 

Read the remainder from bottom to top: (15)16

17

Let p and q be two propositions. Consider the following two formulae in propositional logic.

S1 : (¬p ∧ (p ∨ q)) → q

S2 : q → (¬p ∧ (p ∨ q))

Which one of the following choices is correct?

  1. ((a))

    Neither S1 nor S2 is a tautology.

  2. ((b))

    S1 is not a tautology but S2 is a tautology.

  3. ((c))

    Both S1 and S2 are tautologies.

  4. ((d))

    S1 is a tautology but S2 is not a tautology.

Show Answer
Answer: ((d))

S1 is a tautology but S2 is not a tautology.

Data:

¬ ≡ NOT ≡ ̅ 

OR ≡ ∨ ≡ +

AND ≡ ∧ ≡ .

Formula:

a → b ≡ a̅ + b

Calculation:

S1 : (¬p ∧ (p ∨ q)) → q 

S1 ≡ (p̅.(p + q) → q

S1 ≡ (p̅.p + p̅.q) → q

S1 ≡ (p̅.q) → q

S1 ≡ p‾.q‾+q\overline{\overline p.q} + q

S1 ≡ p + q̅ + q ≡ p + 1 ≡ 1

S1 is a tautology

S2 ≡  q → (¬p ∧ (p ∨ q))

S2 ≡ q → (p̅.(p + q))

S2 ≡ q̅  + (p̅.p + p̅.q)) 

S2 ≡ q̅ + p̅.q ≡ p̅ + q̅  

S2 is not a tautology.

Therefore option 4 is correct

18

Consider the following two statements.

S1 : Destination MAC address of an ARP reply is a broadcast address.

S2 : Destination MAC address of an ARP request is a broadcast address.

Which one of the following choices is correct?

  1. ((a))

    S1 is tue and S2 is false.

  2. ((b))

    Both S1 and S2 are false.

  3. ((c))

    S1 is false and S2 is true.

  4. ((d))

    Both S1 and S2 are true.

Show Answer
Answer: ((c))

S1 is false and S2 is true.

Answer: Option 3

Concept:

Address Resolution Protocol:

  • ARP resolves an IP address to a MAC address.
  • The purpose of the ARP request packet is to query all the other hosts and routers on the subnet to determine the MAC address corresponding to the IP address that is being resolved.
  • The ARP Request Packet, broadcast to all other hosts and routers on the subnet using MAC broadcast address, namely, FF-FF-FF-FF-FF-FF.
  • The ARP reply will be a unicast packet that contains the desired mapping.

Explanation:

Statement 1:Destination MAC address of an ARP reply is a broadcast address.

This is not correct as the Destination MAC address of ARP reply will be a unicast address as ARP reply will be a unicast packet.

Statement 2: Destination MAC address of an ARP request is a broadcast address.

This is correct.

19

Consider the following array.

2332456972738997
<br>

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort above array in ascending order?

  1. ((a))

    Insertion sort

  2. ((b))

    Selection sort

  3. ((c))

    Quicksort using the last element as pivot

  4. ((d))

    Merge sort

Show Answer
Answer: ((a))

Insertion sort

Insertion sort:

In Insertion sort, the best-case takes Θ (n) time, the best case of insertion sort is when elements are sorted in ascending order. In that case, the number of comparisons will be n - 1 = 8 - 1 = 7

It is the least  number of comparisons (among the array elements) to sort the above array in ascending order:

The number of swaps needed is zero.

Additional Information

In Insertion sort, the worst-case takes Θ (n2) time, the worst case of insertion sort is when elements are sorted in reverse order. In that case the number of comparisons will be like:

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n2) time complexity.

20

A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?

  1. ((a))

    Θ(1)

  2. ((b))

    Θ(n log n)

  3. ((c))

    Θ(log n)

  4. ((d))

    Θ(n)

Show Answer
Answer: ((a))

Θ(1)

Explanation:

  • If an element in a binary search tree is smaller than any other element in the binary search tree then it is smaller than the maximum element.
  • All the elements in the binary search tree is distinct.
  • Compare only two elements in the binary search tree to find such elements.
  • Therefore time complexity is θ(1).
21

In the context operating systems, which of the following statements is/are correct with respect to paging?

  1. ((a))

    Paging incurs memory overheads.

  2. ((b))

    Paging helps solve the issue of external fragmentation.

  3. ((c))

    Page size has no impact on internal fragmentation.

  4. ((d))

    Multi-level paging is necessary to support pages of different sizes.

Show Answer
Answer: ((a))

Paging incurs memory overheads.

Key Points

  • Pages are divided into fixed-size slots and hence no external fragmentation. But applications smaller than page size cause internal fragmentation
  • Page tables take extra pages in memory. Therefore incur an extra cost

Therefore option 1 and 2 are correct

22

Let ⟨M⟩\left\langle M \right\rangle  denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

  1. ((a))

    L = { <M> | M is a PDA such that L(M) = ∑*}

  2. ((b))

    L = { <M> | M is a DFA such that L(M) = Φ}

  3. ((c))

    L = { <M> | M is a PDA such that L(M) = Φ}

  4. ((d))

    L = { <M> | M is a DFA such that L(M) = ∑*}

Show Answer
Answer: ((a))

L = { <M> | M is a PDA such that L(M) = ∑*}

Answer: Option 1

Explanation:

Option 1:L = { ⟨M⟩\left\langle M \right\rangle  | M is a PDA such that L(M) = ∑*}

This is not Recursive. As completeness Problem is Undecidable for CFL and Hence no algorithm exists to decide whether or not the Language of PDA is ∑*.

Option 2: L = { ⟨M⟩\left\langle M \right\rangle  | M is a DFA such that L(M) = Φ}

This is Recursive. for DFA accept empty language Algorithm exists

Option 3: L = { ⟨M⟩\left\langle M \right\rangle  | M is a PDA such that L(M) = Φ}

This is also Recursive. for a CFL to checking for empty language problem is decidable. Hence there exists an algorithm to decide whether a PDA accepts empty language or not.

Option 4:L = { ⟨M⟩\left\langle M \right\rangle  | M is a DFA such that L(M) = ∑*}

This is also Recursive. Completeness problem for regular language is decidable.

23

Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery.

Which of the following statements is/are correct?

  1. ((a))

    The same undo and redo list will be used while recovering again.

  2. ((b))

    The database will become inconsistent.

  3. ((c))

    All the transactions that are already undone and redone will not be recovered again.

  4. ((d))

    The system cannot recover any further.

Show Answer
Answer: ((a))

The same undo and redo list will be used while recovering again.

Answer: Option 1

Explanation:

Option 1:The same undo and redo list will be used while recovering again.

This Option is correct. Because in log files operations are idempotent, doing undo-redo operations multiple times yields the same results.

Option 2:The database will become inconsistent.

This option is not correct.

Option 3: All the transactions that are already undone and redone will not be recovered again.

This Option is not correct because transactions that are already undone and redone will be recovered with undo and redo list; performing undo and redo again will produce the same result in the Database.

Option 4: The system cannot recover any further.

This Option is not correct.

24

Which of the following standard C library functions will always invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?

  1. ((a))

    strlen

  2. ((b))

    malloc

  3. ((c))

    exit

  4. ((d))

    sleep

Show Answer
Answer: ((a))

strlen

strlen:

This is a function defined in the standard C library and doesn’t require any system call to perform its function of calculating the string length.

malloc: 

This is a function defined in the standard C library and it does not always invoke the system call. When a process is created, a certain amount of heap memory is already allocated to it, when required to expand or shrink that memory, it internally uses sbrk/brk system call on Unix/Linux

exit:

This is a function defined in standard C library and it always invokes system call every time, flushes the streams, and terminates the caller.

sleep:

This is not even a standard C library function, it is a POSIX standard c library function. Unix and Windows use different header files for it.

Therefore option 3 and 4 are correct options

25

Consider a linear list based implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory foo.

Which of the following operations will necessarily require a full scan of foo for successful completion?

  1. ((a))

    Renaming of an existing file in foo

  2. ((b))

    Opening of an existing file in foo

  3. ((c))

    Deletion of an existing file from foo

  4. ((d))

    Creation of a new file in foo

Show Answer
Answer: ((a))

Renaming of an existing file in foo

Answer: Option 1 and Option 4

Explanation:

Option 1: Renaming of an existing file in foo.

This Option is correct as for the Renaming operation of a file in a directory the New name must not create conflict to any of the existing file names. Hence a full scan is required for successful completion.

Option 2: Opening of an existing file in foo.

This option is not correct as Opening the file does not require a full scan.

Option 3:Deletion of an existing file from foo.

This Option is not Correct. as Deletion of a file does not require a full scan.

Option 4: Creation of a new file in foo.

This Option is correct as While Creating a new file we need to check whether the newly created file name must not create conflict to any of the existing file names. Hence a full scan is required for successful completion.

26

In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______

27

Consider the following undirected graph with edge weights as shown:

<br>

The number of minimum-weight spanning trees of the graph is ______

28

The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter 2. For a randomly picked component of this type, the probability that, its lifetime exceeds the expected lifetime (rounded to 2 decimal places) is ______.

29

There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that:

  • The fastest computer gets the toughest job and the slowest computer gets the easiest job.
  • Every computer gets at least one job.

The number of ways in which this can be done is ______

30

Consider the following expression

lim⁡x→−32x+22−4x+3\mathop {\lim }\limits_{x \to -3} \frac{{\sqrt {2x + 22} - 4}}{{x + 3}}

The value of the above expression (rounded to 2 decimal places) is ______

31

Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); s = pop();

Consider the following sequence of operations on an empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();

The value of s + q is ______

32

Consider a computer system with a byte-addressable primary memory of size 232 bytes. Assume the computer system has a direct-mapped cache of size 32 KB (1 KB = 210 bytes), and each cache block is of size 64 bytes.

The size of the tag field is ______ bits.

33

A relation r(A, B) in a relational database has 1200 tuples. The attribute A has integer values ranging from 6 to 20, and the attribute B has integer values ranging from 1 to 20. Assume that the attributes A and B are independently distributed. The estimated number of tuples in the output of σ(A>10)∨(B=18)(r) is ______

34

Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127.

S: 1 E:   10000001    F : 11110000000000000000000

Here S, E and F denote the sign, exponent and fraction components of the floating point representation.

The decimal value corresponding to the above representation (rounded to 2 decimal places) is ______

35

Three processes arrive at time zero with CPU bursts of 16, 20, and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting for these three processes in a non-preemptive scheduler (rounded to the nearest integer) is ______ milliseconds.

36

Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:

P → D* E*

D → int ID {record that ID.lexeme is of type int}

D → bool ID { record that ID.lexeme is of type bool}

E → E1 + E2 {check that E1.type = E2.type = int; set E.type := int}

E → !E1 {check that E1.type = bool; set E.type := bool}

E → ID {set E.type := int}

With respect to the above grammar; which one of the following choices is correct?

  1. ((a))

    The actions will lead to infinite loop.

  2. ((b))

    The actions can be used to correctly type-check any syntactically correct program.

  3. ((c))

    The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.

  4. ((d))

    The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.

Show Answer
Answer: ((d))

The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.

Answer: Option 4

Explanation:

Option 1:The actions will lead to an infinite loop.

This statement is not correct.

Option 2:The actions can be used to correctly type-check any syntactically correct program.

This statement is not correct. Because These SDT actions can not type-check boolean expressions or float expressions.

for example :

float a=3.46;

bool b = 0,c;

c = a+b; 

Option 3:The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.

This statement is not correct. Because the SDT actions can not be used to correctly type check boolean expressions.

for example : 

bool a = 0;

bool b = 1;

bool c = a+b;

Option 4:The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.

This statement is Correct. Because These SDT actions can be used to correctly type check both integer variables and integer expressions as well.

37

The following relation records the age of 500 employees of a company, where empNo (Indicating the employee number) is the key:

empAge(empNo, age)

Consider the following relational algebra expression:

πempNo(empAge ⋈ (age>age1) ρempNo 1, age1(empAge))

What does the above expression generate?

  1. ((a))

    Employee numbers of only those employees whose age is the maximum.

  2. ((b))

    Employee numbers of all employees whose age is not the minimum.

  3. ((c))

    Employee numbers of only those employees whose age is more than the age of exactly one other employee.

  4. ((d))

    Employee numbers of all employees whose age is the minimum.

Show Answer
Answer: ((b))

Employee numbers of all employees whose age is not the minimum.

Answer: Option 2

Explanation:

Consider the empAge(empNo, age) Table

empNoage
10022
10121
10223
10324
10425
10526
20022
20121
20223
20324
20425
20526
20627

We run the following Query on above Table 

IIempNo(empAge ⋈ (age>age1) ρempNo 1, age1(empAge))

We get Output Table as 

empNo
100
102
103
104
105
200
202
203
204
205
206

Hence the Output is "Employees whose age greater than at least one employee" or "Employees whose age is no minimum".

38

Consider a 3-bit counter, designed using T flip-flop, as shown below:

Assuming the initial state of the counter given by PQR as 000, what are the next three states?

  1. ((a))

    001, 010, 000

  2. ((b))

    001, 010, 111

  3. ((c))

    011, 101, 111

  4. ((d))

    011, 101, 000

Show Answer
Answer: ((d))

011, 101, 000

Answer: Option 3

Concept:

XOR Operation :

PQP⊕Q
000
011
101
110

Explanation:

TP = R Hence P+ = R⊕ P

TQ = P̅  Hence Q+ = P̅ ⊕ Q

TR = Q̅ Hence R+ = Q̅ ⊕ R

PQRP+=R⊕ PQ+=P̅ ⊕ QR+=Q̅ ⊕ R
000011
011101
101000

Next 3 states are 000 → 011 →101 → 000

39

Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is d8d7d6d5c8d4d3d2c4d1c2c1, where the data bits and the check bits are given in the following tables:

Data bits
d8d7d6d5d4d3d2d1
110x0101

 

c8c4c2c1
Y010
<br>

Which one of the following choices gives the correct values of x and y?

  1. ((a))

    x is 1 and y is 0.

  2. ((b))

    x is 1 and y is 1.

  3. ((c))

    x is 0 and y is 1.

  4. ((d))

    x is 0 and y is 0.

Show Answer
Answer: ((d))

x is 0 and y is 0.

Answer: Option 4

Data: 

Data bits
d8d7d6d5d4d3d2d1
110x0101

 

c8c4c2c1
y010

Codeword =  d8d7d6d5c8d4d3d2c4d1c2c1

Codeword = 

110xy0100110
B12B11B10B9B8B7B6B5B4B3B2B1

 

C1=B1 ⊕ B3 ⊕ B5 ⊕ B7 ⊕ B9 ⊕ B11 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ x ⊕ 1; for even parity x=0

C2 = B2 ⊕ B3 ⊕ B6 ⊕ B7 ⊕ B10 ⊕ B11 = 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1;

C4 = B4 ⊕ B5 ⊕ B6 ⊕ B7 ⊕ B12 = 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1; 

C8 = y ⊕ 0⊕ 0 ⊕ 1⊕  ⊕ 1; for even parity y = 0 (putting x = 0)

40

Consider the following recurrence relation.

\(T(n) = \left{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.\)

Which one of the following option is correct?

  1. ((a))

    T(n) = Θ(n log n)

  2. ((b))

    T(n) = Θ(n5/2)

  3. ((c))

    T(n) = Θ((log n)5/2)

  4. ((d))

    T(n) = Θ(n)

Show Answer
Answer: ((d))

T(n) = Θ(n)

Answer: Option 4

Explanation:

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

T(n) = 7n(1+;910+81100+…+;(910)log⁡2n)7n\left( {1 + ;\frac{9}{{10}} + \frac{{81}}{{100}} + \ldots + ;{{\left( {\frac{9}{{10}}} \right)}^{{{\log }_2}n}}} \right) ( for left most subtree base of log is 2 But for rightmost subtree base will be (5/2))

For rightmost subtree:

T(n) =  7n(1+;910+81100+…+;(910)log⁡5/2n)7n\left( {1 + ;\frac{9}{{10}} + \frac{{81}}{{100}} + \ldots + ;{{\left( {\frac{9}{{10}}} \right)}^{{{\log }_{5/2}}n}}} \right)

T(n) = 7n(1-nlog⁡20.9{\log _2}0.9)

T(n) = O(n) 

and similarly for right most subtree 

T(n) = Ω(n) 

hence T(n) = θ(n)

41

Consider the following context-free grammar where the set of terminals is {a, b, c, d, f}.

S → d a T | R f

T → a S | b a T | ϵ

R → c a T R | ϵ

The following is a partially-filled LL(1) parsing table.

Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?

  1. ((a))

    (1) S → R f (2) S → R f (3) T → ϵ (4) T → ϵ

  2. ((b))

    (1) blank (2) S → R f (3) blank (4) blank

  3. ((c))

    (1) S → R f (2) blank (3) blank (4) T → ϵ

  4. ((d))

    (1) blank (2) S → R f (3) T → ϵ (4) T → ϵ

Show Answer
Answer: ((a))

(1) S → R f (2) S → R f (3) T → ϵ (4) T → ϵ

Answer: Option 1

Explanation:

For LL1 parsing we need to calculate first and follow set for all Non-terminals in the grammar.

Non-TerminalFirst Set
S{d, c, f}
T(a, b, ϵ}
R{c, ϵ}

 

Non-TerminalFollow Set
S{c, f, $}
T{c, f, $}
R{f}

 

at 1: S->Rf will be stored.

at 2: again S-> Rf will be stored. 

Because in first set(Rf) = c,f

at 3:T-> ϵ will be stored.

at 4: again T-> ϵ will be stored.

Because first set(T) = {a, b, ϵ}, In the column for 'a' and 'b' corresponding matching Rules are mentioned But first set also contains ϵ then ϵ-corresponding Rules will be filled according to follow set(T) = { c, f, $} in the LL1 table.

42

Let ri(z) and wi(z) denote read and write operations respectively on a data item z by a transaction Ti. Consider the following two schedules.

S1 : r1(x) r1(y) r2(x) r2(y) w2(y) w1(x)

S2 : r1(x) r2(x) r2(y) w2(y) r1(y) w1(x)

Which one of the following options is correct?

  1. ((a))

    S1 is conflict serializable, and S2 is not conflict serializable.

  2. ((b))

    S1 is not conflict serializable, and S2 is conflict serializable.

  3. ((c))

    Both S1 and S2 are conflict serializable.

  4. ((d))

    Neither S1 nor S2 is conflict serializable.

Show Answer
Answer: ((b))

S1 is not conflict serializable, and S2 is conflict serializable.

Answer: Option 2

S1: r1(x) r1(y) r2(x) r2(y) w2(y) w1(x)

Precedence Graph:

S2:r1(x) r2(x) r2(y) w2(y) r1(y) w1(x)

Precedence Graph:

There exists a Cycle in Precedence of S1. Hence S1 is not Conflict Serializable.

Whereas S2 is Conflict Serializable.

43

Consider the relation R(P, Q, S, T, X, Y, Z, W) with the following functional dependencies.

PQ → X; P → YX; Q → Y; Y → ZW

Consider the decomposition of the relation R into the constituent relations according to the following two decomposition schemes.

D1 : R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)]

D2 : R = [(P, Q, S); (T, X); (Q, Y); (Y, Z, W)]

Which one of the following options is correct?

  1. ((a))

    D1 is a lossy decomposition, but D2 is a lossless decomposition.

  2. ((b))

    Both D1 and D2 are lossless decompositions.

  3. ((c))

    Both D1 and D2 are lossy decompositions.

  4. ((d))

    D1 is a lossless decomposition, but D2 is a lossy decomposition.

Show Answer
Answer: ((d))

D1 is a lossless decomposition, but D2 is a lossy decomposition.

Answer: Option 4

Concept:

Lossless Decomposition:

for a Decomposition of two Relation, R1 and R2 to be lossless 2 condition needs to be satisfied that is

1. R1 ∩ R2 → R1 or R2 i.e. common attributes must be key to either of the relation. 2. attributes of R1 ∪ attributes of R2 ≡ attributes of R

Explanation:

D1 : R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)]

lets first take 2 relations R1(P, Q, S, T )  R2(P, T, X) 

common attributes are PT and PT → TX ( according to augmentation property )

so relation becomes R1(P, Q, S, T, X) R2(Q, Y) 

The common attribute is Q and Q→ Y is key to R2 Hence (P, Q, S, T, X, Y)

 So now relation becomes R1(P, Q, S, T, X, Y) R2(Y, Z, W)

 The common attribute is Y and Y is key to R2.

Hence all attributes get combined into one relation and hence this Decomposition is lossless.

D2 : R = [(P, Q, S); (T, X); (Q, Y); (Y, Z, W)]

If you observe relation (T, X); Its attributes not common to any other relations.

even if we combined all other attributes R1(P, Q, S, Y, Z, W)  R2(T, X) 

still no common attributes Hence this decomposition is lossy.

44

Let G be a group order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?

  1. ((a))

    G is always cyclic, but H may not be cyclic.

  2. ((b))

    G may not be cyclic, but H is always cyclic.

  3. ((c))

    Both G and H are always cyclic.

  4. ((d))

    Both G and H may not be cyclic.

Show Answer
Answer: ((b))

G may not be cyclic, but H is always cyclic.

Concept

According to the Lagrange theorem order of subgroups must divide the order of the group.

Property of group says if a group has prime order then it is cyclic.

Explanation:

Since the order of G is 6. Therefore  its subgroup may have order 1,2,3,6

H is one of its subgroups with condition 1< |H| <6 so H may be of order 2 or 3  which is prime 

Hence H must be cyclic

The order of G is 6 which is not prime and hence it may or may not  be cyclic 

Therefore option 2 is correct

45

Consider the two statements.

S1 : There exist random variables X and Y such that

(E[X - E(X)) (Y - E(Y))])2 > Var[X] Var[Y]

S2 : For all random variables X and Y,

Cov[X, Y] = E [|X - E[X]| |Y - E[Y]|]

Which one of the following choices is correct?

  1. ((a))

    S1 is false, but S2 is true.

  2. ((b))

    S1 is true, but S2 is false.

  3. ((c))

    Both S1 and S2 are true.

  4. ((d))

    Both S1 and S2 are false.

Show Answer
Answer: ((d))

Both S1 and S2 are false.

Answer: Option 4

Formula:

Covariance(cov):

cov(X, Y) = E[ (X - E[X]) ] [ (Y - E[Y]) ] 

Theorem:

If X and Y be Random Variables and Let the variances of X and Y exist and be finite then

cov(X,Y)2 ≤ var(X)var(Y)

Statement 1:There exist random variables X and Y such that

(E[X - E(X)) (Y - E(Y))])2 > Var[X] Var[Y]

This is not correct. The Square of covariance is less than equal to the product of variance of the two random variables not greater than.

Statement 2:For all random variables X and Y,

Cov[X, Y] = E [|X - E[X]| |Y - E[Y]|]

This is also not correct because Covariance may result in negative as well but the given expression will generate positive value.

46

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:

diam(G) = max⁡u,x∈V\displaystyle\max_{u, x\in V} {the length of shortest path between u and v}

Let M be the adjacency matrix of G.

Define graph G2 on the same set of vertices with adjacency matrix N, where

\(N_{ij} =\left{ {\begin{array}{*{20}{c}} {1 \ \ \text{if} \ \ {M_{ij}} > 0 \ \ \text{or} \ \ P_{ij} > 0, \ \text{where} \ \ P = {M^2}}\ {0, \ \ \ \ \ \text{otherwise}} \end{array}} \right.\)

Which one of the following statements is true?

  1. ((a))

    diam(G) < diam(G2) ≤ diam(G)

  2. ((b))

    ⌈diam(G)/2⌉\left\lceil {diam(G)/2} \right\rceil  < diam(G2) < diam(G)

  3. ((c))

    diam(G2) ≤ ⌈diam(G)/2⌉\left\lceil {diam(G)/2} \right\rceil

  4. ((d))

    diam(G2) = diam(G)

Show Answer
Answer: ((c))

diam(G2) ≤ ⌈diam(G)/2⌉\left\lceil {diam(G)/2} \right\rceil

Answer: Option 3

Option 1: diam(G) < diam(G2) ≤ diam(G) 

This is not correct.

consider the follwing graph G

Adjacency Matrix will be

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

The Diameter for this Graph G is 2.

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

Graph for G2 is 

and Diameter for G2 is 2 

Hence diameter of the graphs can be equal and if You observe Edges from Original graph G remains as it is G2 as well. so Diameter(G) could never be less than Diameter(G2)

Option 2: ⌈diam(G)/2⌉\left\lceil {diam(G)/2} \right\rceil < diam(G2) < diam(G)

This Option is not correct as stated above the diameter of the graphs (G and G2) can be equal as well.

Option 3:diam(G2) ≤ ⌈diam(G)/2⌉\left\lceil {diam(G)/2} \right\rceil

This Option is correct.

Let's take one more example to prove this. Graph G

and its Adjacency Matrix 

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

and its diameter is 4.

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

and its Graph G2 is 

Its diameter is 2.

Option 4:diam(G2) = diam(G)

This Option is not correct.

47

Consider the following A NSI C program.

#include <stdio.h>

int main( )

{

int i, j, count;

count = 0;

i = 0;

for (j = -3; j <= 3; j++)

{

if ((j >= 0) && (i++))

count = count + j;

}

count = count + i;

printf("%d", count);

return 0;

}

Which one of the following options is correct?

  1. ((a))

    The program will compile successfully and output 10 when executed.

  2. ((b))

    The program will compile successfully and output 8 when executed.

  3. ((c))

    The program will compile successfully and output 13 when executed.

  4. ((d))

    The program will not compile successfully.

Show Answer
Answer: ((a))

The program will compile successfully and output 10 when executed.

Answer: Option 1

Explanation:

count = 0 and i = 0

if ((j >= 0) && (i++))

{count = count + j;}

  • i will be incremented only when J≥0 and j will be added to count
j = 0j = 1j= 2j = 3
i = 1 count = 0+0i = 2 count = 0+1 =1i = 3 count=1+2 = 3i = 4 count = 3+3=6

count = count + i;

count = 6 + 4

count = 10

Hence 10 will be printed.

48

Consider the following language.

L = { w ∈ {0, 1}* | w ends with the substring 011}

Which one of the following deterministic finite automata accepts L?

  1. ((a))

  2. ((b))

  3. ((c))

  4. ((d))

Show Answer
Answer: ((d))

Option 1: Incorrect

string: 0111 is also accepted and it doesn't end with 011.

Option 2: Incorrect

string: 0110 is also accepted and it doesn't end with 011.

Option 3: InCorrect

Diagram in option needs to change

Option 4: correct

w ends with the substring 011

49

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages.

L1 = {(M) | M takes more than 2021 steps on all inputs}

L2 = {(M) | M takes more than 2021 steps on some input}

Which one of the following options is correct?

  1. ((a))

    Both L1 and L2 are undecidable.

  2. ((b))

    L1 is undecidable and L2 is decidable.

  3. ((c))

    L1 is decidable and L2 is undecidable.

  4. ((d))

    Both L1 and L2 are decidable.

Show Answer
Answer: ((d))

Both L1 and L2 are decidable.

Concept:

A language is called Decidable or Recursive if there is a Turing machine that accepts and halts on every input string w. Every decidable language is Turing-Acceptable.

Explanation:

Algorithms L1

Does not halt on all input taking more than 2021 steps → Yes

Halt on least one of the input taking less than 2021 steps → No:

Algorithms L2

Does not halt on at least one of the input taking  more than 2021 steps → Yes

Halt on all the input taking less than 2021 steps → No:

50

Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denotes the selling price of a rod whose length is i meters. Consider the array of prices:

p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18

Which of the following statements is/are correct about R7?

  1. ((a))

    R7 cannot be achieved by a solution consisting of three pieces.

  2. ((b))

    R7 = 19

  3. ((c))

    R7 = 18

  4. ((d))

    R7 is achieved by three different solutions.

Show Answer
Answer: ((a))

R7 cannot be achieved by a solution consisting of three pieces.

Answer: Option 3 and Option 4 

Data:

p[1] = 1, p[2] = 5, p[3] = 8,

p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18

Calculation: 

R7= max amount and length can be integer 

PiecesAmount
1, 1, 1, 1, 1, 1, 17
1, 1, 1, 1, 1, 210
1, 1, 1, 1, 312
1, 1, 1, 412
1, 1, 512
1, 618
1, 1, 2, 315
1, 3, 317
1,2,415
2, 2, 318
718

maximum cost possible is 18 and there are 3 solutions for R7.

51

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.

Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?

  1. ((a))

    If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

  2. ((b))

    Root of T is an articulation point in G if and only if it has 2 or more children.

  3. ((c))

    Root of T can never be an articulation point in G.

  4. ((d))

    A leaf of T can be an articulation point in G.

Show Answer
Answer: ((a))

If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

Answer: Option 2

Explanation:

Option 1: If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

 

Consider the above example U is an articulation point in graph G and x is the ancestor to U and y is the descendent of U. not all paths from X to Y in G pass through U.

Hence This statement is incorrect.

Option 2:Root of T is an articulation point in G if and only if it has 2 or more children.

This is Correct.

Consider the above example only; if we start DFS from U.

we get T as

 

U has 2 children and U is the articulation point in G.

Option 3:Root of T can never be an articulation point in G.

This is incorrect. for example, you can refer to Option 2 Same reasoning can be used to counter this option.

Option 4:A leaf of T can be an articulation point in G.

This is also incorrect. The Articulation point of G will never be a leaf of the DFS tree.

52

Consider the following Boolean expression.

F=(X+Y+Z)(X‾+Y)(Y‾+Z)F = (X + Y + Z)(\overline X + Y)(\overline Y + Z)

Which of the following Boolean expressions is/are equivalent to F‾\overline F (complement of F)?

  1. ((a))

    (X‾+Y‾+Z‾)(X+Y‾)(Y+Z‾)(\overline X + \overline Y + \overline Z )(X + \overline Y )(Y + \overline Z )

  2. ((b))

    XY‾+Z‾X\overline Y + \overline Z

  3. ((c))

    XY‾+YZ‾+X‾Y‾Z‾X\overline Y + Y\overline Z + \overline X \overline Y \overline Z

  4. ((d))

    (X+Z‾).(Y‾+Z‾)(X + \overline Z ) . (\overline Y + \overline Z )

Show Answer
Answer: ((a))

(X‾+Y‾+Z‾)(X+Y‾)(Y+Z‾)(\overline X + \overline Y + \overline Z )(X + \overline Y )(Y + \overline Z )

Formula:

(A + B)(A + C) = A + B.C

Calculation:

F=(X+Y+Z)(X‾+Y)(Y‾+Z)F = (X + Y + Z)(\overline X + Y)(\overline Y + Z)

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

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

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

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

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

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

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

F = Z.(X̅ + Y)   

Taking complement on both sides

F̅ = Z.(X‾+Y)‾\overline{Z.(\overline X + Y)}    

By Demorgan's law

F̅ = Z̅ + X.Y̅  =  X.Y̅ + Z ................. (B)

F‾=(X+Z‾).(Y‾+Z‾)...........(D)\overline F= (X + \overline Z ) . (\overline Y + \overline Z ) ...........(D)

Option C:

F=(X+Y+Z)(X‾+Y)(Y‾+Z)F = (X + Y + Z)(\overline X + Y)(\overline Y + Z)

Taking complement on both sides

F‾=X‾Y‾Z‾+XY‾+YZ‾\overline F= \overline X \overline Y \overline Z +X\overline Y + Y\overline Z

Hence option B, C and D are correct

53

A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?

  1. ((a))

    If a relation S is transitive and circular, then S is an equivalence relation.

  2. ((b))

    If a relation S is reflexive and symmetric, then S is an equivalence relation.

  3. ((c))

    if a relation S is reflexive and circular, then S is an equivalence relation.

  4. ((d))

    if a relation S is circular and symmetric, then S is an equivalence relation.

Show Answer
Answer: ((a))

If a relation S is transitive and circular, then S is an equivalence relation.

Answer: Option 3

Concept:

Equivalence Relation:

For a Relation to be Equivalence Relation, Relation has to satisfy 3 property ;

  1. Reflexive Property
  2. Symmetric property
  3. Transitive Property

Explanation:

Let's start with Option 3;

Option 3:if a relation S is reflexive and circular, then S is an equivalence relation.

It is correct.

  • S is reflexive and circular; see that if are able to derive Symmetric and transitive property from these given properties.

aRa ∈ S and aRb ∈ S => bRa ∈ S   //Using Reflexive and circular 

aRb and bRa both exist then the relation is Symmetric.

 - Now 

 aRb and bRc together => cRa and according to symmetricity ≡  aRc 

aRb and bRc together => aRc

Hence Transitivity satisfied.

Hence S is an Equivalence Relation.

Example : S = { {a,a) (b.b) (c,c) } (diagonal relation)

Option 1: If a relation S is transitive and circular, then S is an equivalence relation.

It is not correct.

Consider a example of empty relation or S = {(a,b)}; it is transitive and circular but its not Equivalence Relation.

Hence S is not an equivalence Relation.

Option 2: If a relation S is reflexive and symmetric, then S is an equivalence relation.

It is not correct. For a Relation S to be Equivalence Reflexive, Symmetric and Transitive are required.

Option 4: if a relation S is circular and symmetric, then S is an equivalence relation.

It is not correct.

Consider a example of empty relation or S = {(a,b) , (b,a), (a,a)}; It is circular and symmetric but its not Equivalence relation.

Hence S is not an equivalence Relation.

54

A TCP server application is programmed to listen on port number P on host S. A TCP client connected to the TCP server over the network.

Consider that while the TCP connection was active, the server machine S crashed are rebooted. Assume that the client does not use the TCP keepalive timer.

Which of the following behaviours is/are possible?

  1. ((a))

    If the client sends a packet after the server reboot, it will receive a RST segment.

  2. ((b))

    If the client was waiting to receive a packet, it may wait indefinitely.

  3. ((c))

    It the client sends a packet after the server reboot, it will receive a FIN segment.

  4. ((d))

    The TCP server application on S can listen on P after reboot.

Show Answer
Answer: ((a))

If the client sends a packet after the server reboot, it will receive a RST segment.

Answer: Option 1, Option 2 and Option 4

Option 1:If the client sends a packet after the server reboot, it will receive an RST segment.

This Option is correct.

Because in Absence of Keepalive timer, after reboot TCP server does not remember info regarding previous connections and If it receives a packet from the client, it may generate reset segment.

Option 2:If the client was waiting to receive a packet, it may wait indefinitely.

This Option is also correct.

There is no Keepalive timer exists, then there is a possibility that the Client may keep waiting Indefinitely for the packet from the server.

Option 3: If the client sends a packet after the server reboot, it will receive a FIN segment.

This Option is not correct.

Fin Segment is not possible in the given scenario.

Option 4:The TCP server application on S can listen on P after reboot.

Thi Option is correct.

Suppose that TCP Server dedicated to only one process then it is possible that it will start listening to the process at client even after reboot.

55

Consider two hosts P and Q connected through a router R. The maximum transfer unit (MTU) value of the link between P and R is 1500 bytes, and between R and Q is 820 bytes.

A TCP segment of size 1400 bytes was transferred from P to Q through R, with IP identification value as 0 × 1234. Assume that the IP header size is 20 bytes. Further, the packet is allowed to be fragmented i. e, Don't Fragment (DF) flag in the IP header is not set by P.

Which of the following statements is/are correct?

  1. ((a))

    TCP destination port can be determined by analysing only the second fragement.

  2. ((b))

    If the second fragment is lost, P is required to resend the whole TCP segment.

  3. ((c))

    Two fragments are created at R and the IP datagram size carrying the second fragment is 620 bytes.

  4. ((d))

    If the second fragment is lost, R will resend the fragment with the IP identification value 0 × 1234.

Show Answer
Answer: ((a))

TCP destination port can be determined by analysing only the second fragement.

Answer: Option 2 and Option 3

Explanation:

TCP Segment Size = 1400

Packet size = segment size + IP Header Size = 1400+ 20 = 1420 

At R Packet will be Fragmented 

MTU = 800 + 20 (Header) 

Hence Packet's Data (1400) will be divided in two packets = (800 + 600)

First Fragment  = (800 + 20) //Data + Header

Second Fragment  = ( 600 + 20 ) 

Option 1: The TCP destination port can be determined by analyzing only the second fragment.

This Option is not correct as Destination Port Number can be identified by looking at any packet or Fragment. not just only from Second Fragment.

Option 2:If the second fragment is lost, P is required to resend the whole TCP segment.

This is correct. If any of the Fragments is lost then the entire packet/TCP segment has to be retransmitted this one of the drawbacks of fragmentation.

Option 3:Two fragments are created at R and the IP datagram size carrying the second fragment is 620 bytes.

This is correct.

Option 4: If the second fragment is lost, R will resend the fragment with the IP identification value 0 × 1234.

This Option is not correct As If any of the Fragments is lost then the entire packet/TCP segment has to be retransmitted.

56

Consider the following pseudocode, where S is a semaphore intialized to 5 in line#2 an counter is a shared variable intialized to 0 in line#1. Assume that the increment operation in line#7 is not atomic.

  1. int counter = 0;
  2. Semaphore S = init(5);
  3. void parop(void)
  4. {
  5. wait (S);
  6. wait (S);
  7. counter++;
  8. signal (S);
  9. signal (S);
  10. }

If five threads execute the function parop concurrently, which of the following program behavior (s) is/are possible?

  1. ((a))

    There is a deadlock involving all the threads.

  2. ((b))

    The value of counter is 5 after all the threads successfully complete the execution of parop.

  3. ((c))

    The value of counter is 1 after all the threads successfully complete the execution of parop.

  4. ((d))

    The value of counter is 0 after all the threads successfully complete the execution of parop.

Show Answer
Answer: ((a))

There is a deadlock involving all the threads.

Answer: Option 1, Option 2 and Option 3

Explanation:

Increment operation in Line 7 is not atomic means while incrementing the variable process/thread can be preempted.

Increment Generally performed below mentioned 3 steps in assembly language.

load R1, counter; // load value of counter from memory to register R1

add R1,#1;           //add 1 to the content of register R1.

store R1, counter;  //Store incremented value in counter (Memory)

Option 1:There is a deadlock involving all the threads.

This Option is Correct.

Now Thread 1 executes till line 5 and preempts; Now S=4,

Thread 2 executes till line 5 and preempts; Now S=3,

Thread 3 executes till line 5 and preempts; Now S=2,

Thread 4 executes till line 5 and preempts; Now S=1,

Thread 0 executes till line 5 and preempts; Now S=0 and if any of threads Resumes; they all will perform unsuccessful down operation and all will be blocked no one to wake up the threads. This is a Deadlock situation.

Option 2:The value of the counter is 5 after all the threads successfully complete the execution of parop.

This Option is Correct.

Option 3:The value of the counter is 1 after all the threads successfully complete the execution of parop.

This Option is Correct.

Thread 1 start execution and line 7, it performs the following

load R1, counter;

add R1,#1; //R1 contains 1

and now it preempts 

Thread 2 start execution and finishes.

Thread 3 start execution and finishes

Thread 4 start execution and finishes

Thread 5 start execution and finishes.

and Now Thread 1 Resumes.

store R1, counter;  // it overwrite counter as 1;

Option 4:The value of the counter is 0 after all the threads successfully complete the execution of parop.

This is incorrect. Counter =0 not possible after all the threads successfully complete, Minimum value possible is 1.

57

Consider a dynamic hashing approach for 4-bit integer keys:

  1. There is a main hash table of size 4.
  2. The 2 least significant bits of a key is used to index into the main hash table.
  3. Initially, the main hash table entries are empty.
  4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
  5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
  6. to resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on 4th least significant bit.
  7. A split is done only if it is needed, i. e. only when there is a collision.

Consider the following state of the hash table.

<br>

Which of the following sequence of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

  1. ((a))

    10, 9, 6, 7, 5, 13

  2. ((b))

    5, 9, 4, 13, 10, 7

  3. ((c))

    9, 5, 13, 6, 10, 14

  4. ((d))

    9, 5, 10, 6, 7, 1

Show Answer
Answer: ((a))

10, 9, 6, 7, 5, 13

Answer: Option 1

Explanation:

Option 2 and Option 3 are directly eliminated because slot 10 should have exactly 2 keys and in option 2 slot 10 have only one key and in option 3 slot 10 have 3 keys.

Hence Option 2 and Option 3 are rejected.

Consider Option 1: 10, 9, 6, 7, 5, 13

00011011

Insert 10 (1010) 

<br>

 Insert 9 (1001)

Insert 6 (0110) 

at 10 binary tree will be constructed according to 3rd least significant bit

Insert 7 (0111)

Insert 5 (0101)

Insert 13 (1101)

now again collision will occur at 01 and according to the 3rd least significant bit and 4th least significant bit binary tree will be constructed.

and Above HashTable same as the given Hash table. If you see in Option 4; 1 (0001) is also mentioned which clearly not present in the HashTable as well.

58

Consider the following ANSI C function:

int SimpleFunction (int y[], int n, int x)

{

int total = y[0], loopIndex;

for (loopIndex = 1; loopIndex <= n - 1; loopIndex++)

total = x * total + y[loopIndex];

return total :

}

Let Z be an array of 10 elements with Z[i] = 1, for all i such that 0 ≤ i ≤ 9. The value returned by SimpleFunction (Z, 10, 2) is ______

59

Consider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following:

  1. The time taken for processing the data frame by the receiver is negligible.
  2. The time taken for processing the acknowledgement frame by the sender is negligible.
  3. The sender has infinite number of frames available for transmission.
  4. The size of the data frame is 2,000 bits and the size of the acknowledgment frame is 10 bits.
  5. The link data rate in each direction is 1 Mbps (= 106 bits per second).
  6. One way propagation delay of the link is 100 milliseconds.

The minimum value of the sender's window size in terms of the number of frames, (rounded to the nearest integer) needed to achieve a link utilization of 50% is ______

60

Consider the following C code segment:

a = b + c;

e = a + 1;

d = b + c;

f = d + 1;

g = e + f;

In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes of nodes in the DAG is ______

61

In a pushdown automaton P = (Q, ∑, Γ, δ, q0, F), a transition of the form,

where p, q ∈ Q, a ∈ Σ ∪ {ϵ}, and X, Y ∈ Γ ∪ {ϵ}, represents

(q, Y) ∈ δ(p, a, X).

Consider the following pushdown automaton over the input alphabet ∑ = {a, b} and stack alphabet Γ = {#, A}.

<br>

The number of strings of length 100 accepted by the above pushdown automaton is ______

62

Consider the following matrix.

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

The largest eigenvalue of the above matrix is ______

63

A five-stage pipeline has stage delays of 150, 120, 150, 160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds each.

The total time to execute 100 independent instructions on this pipeline, assuming there are no pipeline stalls, is ______ nanoseconds.

64

A sender (S) transmits a signal, which can be one of the two kinds: H and L with probabilities 0.1 and 0.9 respectively, to a receiver (R).

In the graph below, the weight of edge (u, v) is the probability of receiving v when u is transmitted, where u, v ∈ {H, L}. For example, the probability that the received signal is L given the transmitted signal was H, is 0.7.

<br>

If the received signal is H, the probability that the transmitted signal was H (rounded to 2 decimal places) is ______

65

Consider the following instruction sequence where register R1, R2 and R3 are general purpose and MEMORY[X] denotes the content at the memory location X.

InstructionSemanticsInstruction Size (bytes)
MOV R1, (5000)R1 ← MEMORY[5000]4
MOV R2, (R3)R2 ← MEMORY[R3]4
ADD R2, R1R2 ← R1 + R22
MOV (R3), R2MEMORY[R3] ← R24
INC R3R3 ← R3 + 12
DEC R1R1 ← R1 – 12
BNZ 1004Branch if not zero to the given absolute address2
HALTStop1

 

Assume that the content of the memory location 5000 is 10, and the content of the register R3 is 3000. The content of each of the memory locations from 3000 to 3010 is 50. The instruction sequence starts from the memory location 1000. All the numbers are in decimal format. Assume that the memory is byte addressable.

After the execution of the program, the content of memory location 3010 is ______

Attempt this paper under real exam conditions

Timed interface, section switching, instant scoring, and question-by-question analytics — free.

Start Timed Attempt