Official Paper

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

65 questions · 180 minutes · with answers · free

Attempt as Timed Mock Test

General Aptitude (10 questions)

1

Gauri said that she can play the keyboard _____ her sister.

  1. ((a))

    as worse as

  2. ((b))

    as nicest as

  3. ((c))

    as well as

  4. ((d))

    as better as

Show Answer
Answer: ((c))

as well as

The correct answer is as well as.

Key Points

  • ‘Worse’, ‘better’ are comparative words which need the word ‘than’ for comparison.
  • As nicest as is grammatically wrong. It should have been 'as nice as.' Nicest is the superlative degree which expresses the highest form of an adjective, doesn’t fit here.
  • Thus, ‘as well as’ is the correct answer.
2

A transparent square sheet shown above is folded along the dotted line. The folded sheet will look like ____

  1. ((a))

  2. ((b))

  3. ((c))

  4. ((d))

Show Answer
Answer: ((b))

The folded sheet is;

Hence, option (2) is the correct answer.

3

If θ is the angle, in degrees, between the longest diagonal of the cube and any one of the edges of the cube, then, cos θ =

  1. ((a))

    12\frac{1}{2}

  2. ((b))

    32\frac{\sqrt3}{2}

  3. ((c))

    13\frac{1}{\sqrt3}

  4. ((d))

    12\frac{1}{\sqrt2}

Show Answer
Answer: ((c))

13\frac{1}{\sqrt3}

Concept:

The longest diagonal would be from one corner vertex to the diagonally opposite corner vertex.

The diagonal of a square face of cube, a side of the cube and the longest diagonal will form a right angled triangle with longest diagonal as the hypotenuse.

Formula used:

 cos θ = Base/Hypotenues 

Calculation:

Length of diagonal of a side = √(a2 + a2) = a√2

Length of the longest diagonal = √[a2 + (a√2)2] = a√3

Then, cos θ = Base/Hypotenues = a/a√3 = 1/√3

∴ The required result will be 1/√3.

4

If (x−12)2−(x−32)2=x+2,(x- \frac{1}{2})^2 -(x-\frac{3}{2})^2=x + 2, then the value of x is:

  1. ((a))

    4

  2. ((b))

    6

  3. ((c))

    2

  4. ((d))

    8

Show Answer
Answer: ((a))

4

Given:

The expression is (x−12)2−(x−32)2=x+2,(x- \frac{1}{2})^2 -(x-\frac{3}{2})^2=x + 2,

Concept:

a2 - b2 = (a + b) × (a - b)

Calculation:

⇒ (x - 1/2 + x - 3/2) × (x - 1/2 - x + 3/2) = x + 2

⇒ (2x - 2) × (1) = x + 2

⇒ x = 4

∴ The required result will be 4.

5

Pen : Write :: Knife : _____

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

  1. ((a))

    Cut

  2. ((b))

    Vegetables

  3. ((c))

    Sharp

  4. ((d))

    Blunt

Show Answer
Answer: ((a))

Cut

Pen is used to write.

Similarly;

Knife is used to cut.

Hence, "Cut" is the correct answer.

6

Listening to music during exercise improves exercise performance and reduces discomfort. Scientists researched whether listening to music while studying can help students learn better and the results were inconclusive. Students who needed external stimulation for studying fared worse while students who did not need any external stimulation benefited from music. 

<br>

Which one of the following statements is the CORRECT inference of the above passage?

  1. ((a))

    Listening to music has no effect on learning and a positive effect on physical exercise.

  2. ((b))

    Listening to music has a clear positive effect both on physical exercise and on learning.

  3. ((c))

    Listening to music has a clear positive effect on learning in all students. Music has a positive effect only in sonic students who exercise

  4. ((d))

    Listening to music has a clear positive effect on physical exercise. Music has a positive effect on learning only in some students. 

Show Answer
Answer: ((d))

Listening to music has a clear positive effect on physical exercise. Music has a positive effect on learning only in some students. 

The correct answer is ' Listening to music has a clear positive effect on physical exercise. Music has a positive effect on learning only in some students '.

Key Points

  • From the first statement, 'Listening to music during exercise improves exercise performance and reduces discomfort', it is clear that listening to music has a positive effect on physical exercise.
  • From the statement 'Scientists researched whether listening to music while studying can help students learn better and the results were inconclusive', it is clear that only on some students music has a positive effect.
  • Thus, we can conclude that option 4 is the most appropriate answer choice.
7

A jigsaw puzzle has  2 pieces. One of the pieces is shown above. Which one of the given options for the missing piece when assembled will form a rectangle? The piece can be moved, rotated or flipped to assemble wiht the above piece.

  1. ((a))

  2. ((b))

  3. ((c))

  4. ((d))

Show Answer
Answer: ((b))

The missing piece when assembled will form a rectangle is;

 

After combining;

Hence, option (2) is the correct answer.

8

The number of students in three classes is in the ratio 3 : 13 : 6. If 18 students are added to each class, the ratio changes to 15 : 35 : 21

The total number of students in all the three classes in the beginning was:

  1. ((a))

    110

  2. ((b))

    22

  3. ((c))

    88

  4. ((d))

    66

Show Answer
Answer: ((c))

88

Given:

The original ratio of student in three classes is 3 : 13 : 6

Calculation:

Let be assume the at the beginning students in three-class were 3x, 13x, and 6x respectively and after ratio was 15y, 35y, and 21y respectively.

⇒ 3x - 15y = -18 ..... (1)

⇒ 13x - 35y = - 18 .... (2)

⇒ 6x - 21y = - 18 .... (3)

By solving (1) and (2)

⇒ x/y = 2/1

⇒ From equation (3)

⇒ x = 4, y = 2

⇒ The total number of student in all classes = 3x + 13x + 6x = 22x = 22 × 4 = 88

∴ The required result will be 88.

9

 

The number of units of a product sold in three different years and the respective net profits are presented in the figure above. The cost/unit in year 3 was Rs. 1, which was half the cost/unit in year 2. The cost/unit in year 3 was one-third of the cost/unit in year 1. Taxes were paid on the selling price at 10%, 13%, and 15% respectively for the three years. Net profit is calculated as the difference between the selling price and the sum of cost and taxes paid in that year. 

The ratio of the selling price in Year 2 to the selling price in Year 3 is ____.

  1. ((a))

    3 : 4

  2. ((b))

    1 : 2

  3. ((c))

    1 : 1

  4. ((d))

    4 : 3

Show Answer
Answer: ((d))

4 : 3

Given:

Cost/unit in year 3 = Rs. 1

Cost/unit in year 2 = Rs. 2

Cost/unit in year 1 = Rs. 3

Calculation:

Net Profit = S.P. - (Cost + Taxes)

In year 2,

296 = S.P. - (2 x 200 + 0.13 S.P.)

S.P. = 800 Selling price in year 2 = Rs. 800

In year 3,

210 = S.P. - (300 x 1 + 0.15 S.P.)

210 = S.P. - 300 - (0.15 S.P.) 

S.P. = 210+3001−0.15{{210 + 300} \over {1-0.15}}

Selling price in year 3 = Rs. 600

Hence, Required ratio = 800: 600 = 4 : 3

10

Six students P, Q, R, S, T and U, with distinct heights, compare their heights and make the following observations.

Observation I: S is taller than R. 

Observation II: Q is the shortest of all.

Observation III: U is taller than only one student.

Observation IV: T is taller than S but is not the tallest.

The number of students that are taller than R is the same as the number of students shorter than _____.

  1. ((a))

    P

  2. ((b))

    T

  3. ((c))

    R

  4. ((d))

    S

Show Answer
Answer: ((d))

S

Six students P, Q, R, S, T, and U

1) S is taller than R.

S > R

2) Q is the shortest of all.

3) U is taller than only one student.

So, U > Q

4) T is taller than S but is not the tallest.

P > T > S

After combining:

P > T > S > R > U > Q

The number of students that are taller than R = 3

The number of students shorter than S = 3

Hence, "S" is the correct answer.

Computer Science and Information Technology (55 questions)

11

Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?

  1. ((a))

    S1 is false and S2 is true.

  2. ((b))

    S1 is true and S2 is false.

  3. ((c))

    Both S1 and S2 are true.

  4. ((d))

    Both S1 and S2 are false.

Show Answer
Answer: ((a))

S1 is false and S2 is true.

Concept:

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

Statement I: Incorrect

Diagram: change weight and  remove directions and weight is 1:

Since edge(AB) = edge(AC) = edge(BC) = minimum weight edge

While forming MST: not a single edge is present in all MST

Statement II: Correct:

If every edge in G has distinct weight, then G has a unique minimum spanning tree

Graph G(V, E)

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

If edge weights are distinct then there exist unique MST.

Hence Statement II is correct.

12

Let H be a primary min-heap consisting of n elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in H?

  1. ((a))

    θ(log n)

  2. ((b))

    θ(n)

  3. ((c))

    θ(1)

  4. ((d))

    θ(n log n)

Show Answer
Answer: ((b))

θ(n)

Key Points

  • A min-heap is a complete binary tree data structure in which the parent node has a value smaller than its children node.
  • In a min-heap, leaf nodes or the last level contains the maximum values of the array.

Explanation:

If we use the brute force technique, it will take O(n) time to find the largest element in a binary min-heap.

If we use the property of min-heap:

The min-heap property requires that the parent node be lesser than its child node(s). Due to this, we can conclude that a non-leaf node cannot be the maximum element as its child node has a lower value.

So we can narrow down our search space to only leaf nodes. In a min-heap having n elements, there is ceil(n/2) leaf nodes. The time and space complexity remains O(n) as a constant factor of 1/2 does not affect the asymptotic complexity.

Additional Information

 In a min-heap, minimum element takes θ(1).

13

Consider the following ANSI C program:

int main() {

Integer x;

return 0;

}

Which one of the following phases in a seven-phase C compiler will throw an error?

  1. ((a))

    Syntax analyzer

  2. ((b))

    Semantic analyzer

  3. ((c))

    Machine dependent optimizer

  4. ((d))

    Lexical analyzer

Show Answer
Answer: ((b))

Semantic analyzer

Code:

int main() {

Integer x;    // Integer is not keyword in C 

return 0;

}

Explanation:

Since the Integer is not defined so the compiler will treat it as an unknown reference.

Therefore Semantic Analyzer phases in a seven-phase C compiler will throw an error.

Additional Information

Integer is keyword in Java

14

The format of the single-precision floating-point representation of a real number as per the IEEE 754 standard is as follows:

signexponentmantissa
<br>

Which one of the following choices is correct with respect to the smallest normalized positive number represented using the standard?

  1. ((a))

    exponent = 00000000 and mantissa = 00000000000000000000001

  2. ((b))

    exponent = 00000001 and mantissa = 00000000000000000000000

  3. ((c))

    exponent = 00000001 and mantissa = 00000000000000000000001

  4. ((d))

    ​exponent = 00000001 and mantissa = 000000000000000000000001

Show Answer
Answer: ((b))

exponent = 00000001 and mantissa = 00000000000000000000000

Option 2) is correct answer.

Concept:

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

Sign bit (MSB)Biased Exponent (E’) (8 bits)Normalized Mantissa (M’) (23 bits)

 

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

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

Explanation: 

Smallest normalized positive number

Sign bitBiased Exponent (E’)Normalized Mantissa (M’)
00000 000100000000000000000000000

 

Smallest normalized positive = (-1)0 × 1.00...0 × 21 – 127 = 2-126  ≈1.1755 × 10–38

15

Which one of the following circuits implements the Boolean function given below?

f(x, y,z) = m0 + m1 + m3 +m4 + m5 + m6, where mi is the ith minterm.

  1. ((a))

  2. ((b))

  3. ((c))

  4. ((d))

Show Answer
Answer: ((a))

Answer: Option 1

Concept : 

  • Boolean expression  : S̅ 1S̅ 0I0 + S̅ 1 S0I1 + S1S̅ 0I2 + S1S0I3

Explanation :

Given :

F( x, y, z ) = m0 + m1 + m3 + m4 + m5 + m6

F( x, y, z ) = x’y’z’ + x’y’z + x’yz + xy’z’ + xy’z + xyz’

Now if we observe Given Question is a MCQ i.e. There will be only one Correct Option.

In given all options, Multiplexers have y, z as Select lines.

So we will try classify the input based on select line.(possible inputs) 

And other variables on input side.

So Correct options is 1. 

Alternatively 

Alternatively,

Option 4 :

Boolean expression  : y’z’x’ + y’z(1) + yz’(x) + yz(1)

= x’y’z’ + xyz’ + y’z + yz

=  x’y’z’ + xyz’ + (x+x’)y’z + (x+x’)yz

= x’y’z’ + x’y’z + x’yz + xy’z + xyz’ + xyz

= m0 + m1 + m3 + m5 + m6 + m7

This is not equivalent to given expression in the Question.

Option 3 :

Boolean Expression :  y’z’(1) + y’z(1) + yz’(x’) + yz(x)

= x’yz’ + xyz + (x+x’)y’z’ + (x+x’)y’z

= x’y’z’ + x’y’z + x’yz’ + xy’z’ + xy’z + xyz

= m0 + m1 + m2 + m4 + m5 + m7  

Again, This is not equivalent to given expression in the Question.

Option 2 : 

Boolean Expression :  y’z’(x) + y’z(1) + yz’(x’) + yz(1)

= x’yz’ + xy’z’ + y’z + yz

= x’yz’ + xy’z’ + (x+x’)y’z + (x+x’)yz

= x’y’z + x’yz’ +x’yz + xy’z’ + xy’z + xyz

= m1 + m2 + m3 + m4 + m5 + m7

Again, This is not equivalent to given expression in the Question.

Option 1 : 

Boolean Expression : y’z’(1) + y’z(1) + yz’(x) + yz(x’)

= xyz’ + x’yz + y’z’ + y’z

= xyz’ + x’yz + (x+x’)y’z’ + (x+x’)y’z

= x’y’z’ + x’y’z + x’yz + xy’z’ +xy’z + xyz’

= m0 + m1 + m3 + m4 + m5 + m6

Hence this is the Correct Option.

16

Consider the following statements S1 and S2 about the relational data model:

S1: A relation scheme can have at most one foreign key.

S2: A foreign key in a relation scheme R cannot be used to refer to tuples of R.

Which one of the following choices is correct?

  1. ((a))

    S1 is true and S2 is false.  

  2. ((b))

    Both S1 and S2 are true.  

  3. ((c))

    Both S1 and S2 are false.  

  4. ((d))

    S1 is false and S2 is true. 

Show Answer
Answer: ((c))

Both S1 and S2 are false.  

Answer: Option 3

Concept: 

Foreign Key :is the set of attributes in a particular relation whose values are belongs to primary key of same relation or other relation.

Explanation: 

Statement 1: A relation scheme can have at most one foreign key.

There is no such restriction on how many number of Foreign keys a particular relation can have. A relation can have as many number of Foreign keys as Required. 

So this statement is false.

Statement 2: foreign key in a relation scheme R cannot be used to refer to tuples of R.

There is no such constraint. Foreign key can be used to refer to primary key of the same relation. Self-referencing relations are examples of such foreign key. So this statement is also false.

So option 3 is the correct answer.

17

Consider the three-way handshake mechanism followed during TCP connection establishment between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers chosen by P and Q respectively. Suppose P sends a TCP connection request message to Q with a TCP segment having SYN bit = 1, SEQ number = X, and ACK bit = 0. Suppose Q accepts the connection request. Which one of the following choices represents the information present in the TCP segment header that is sent by Q to P?

  1. ((a))

    SYN bit = 0, SEQ number = X + 1, ACK bit = 0, ACK number = Y, FIN bit = 1

  2. ((b))

    SYN bit = 1, SEQ number = X + 1, ACK bit = 0, ACK number = Y, FIN bit = 0

  3. ((c))

    SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X, FIN bit = 0

  4. ((d))

    SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X + 1, FIN bit = 0

Show Answer
Answer: ((d))

SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X + 1, FIN bit = 0

Answer: Option 4

Concept: 

  • In TCP, for Connection Establishment 3-way handshake protocol is used.
  • FIN bit : FIN bit is set while terminating the connection.
  • Syn bit : Syn bit is used for initiating the request for connection establishment.
  • Ack bit : Ack bit is used for indicating that the segment contains the acknowledgment.
  • Sequence Number : In TCP , Sequence number used for counting each byte transferred in a particular connection and in each Segment Header, Sequence number field contains the Sequence number of first byte of data part of the Segment.
  • Ack Number: In TCP , Ack number indicates the Sequence number of Byte expected next.

Explanation:

GIven: 

Next segment will be a piggybacked Acknowledgement segment So Ack bit = 1 and  Q will increment the Sequence number ( which it received from P) put this into Ack Number field. Syn = 1 as Q will also establish the connection from Q to P and Sequence number will be Y(As given in Question).

So , SYN bit = 1 SEQ Number = Y ACK bit = 1 ACK number = X+1 FIN bit = 0. Matches with Option 4.​

18

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

  1. ((a))

    θ(n)

  2. ((b))

    θ(√n)

  3. ((c))

    θ(log2(n))

  4. ((d))

    θ(n2)

Show Answer
Answer: ((c))

θ(log2(n))

The correct answer is option 3:

Key Points

  • Binary search has the Worst-case and avg case time complexity O(log2n) and best case O(1) in an array. So, it is can also be written as θ(log2n)

and θ (1).

  • No of arithmetic operations will be θ (logn) in the worst case as every comparison needs 2 operations + and / by 2.
19

Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states? 

  1. ((a))

    {0,1}* - L

  2. ((b))

    L.L

  3. ((c))

    L - {01}

  4. ((d))

    L ∪ {01}

Show Answer
Answer: ((a))

{0,1}* - L

Answer: Option 1

Explanation:

Option 1:{0,1}* - L

Option 1 is just complement of language L. Hence Minimal DFA will contain k states for example 

L = no of 0's are evenL̅  = no of 0’s are odd

Option 2: L.L

Concatenation operation might not result in the same no of state in minimal DFA.

Consider the following simple example

let L = language with only string "11". { only 11 accepts all other must reject }

L.L= language with string “1111” clearly Minimal DFA for L.L will have more no states than L.

Option 3: L - {01}

This language may not contain the same no of states as L.

let's take an example as L = no of 0s are odd.

then we have to add additional states to reject 01.

DFA will be

Option 4: L ∪ {01}

This language also may not contain the same no of states as L.

So Only Option 1 is correct.

20

Consider the following ANSI C program.

#include<stdio.h>

int main()

{

   int arr[4][5];

   int i, j;

  for(i =0; i<4; i++)

  {

    for (j =0; j<5; j++)

    {

       arr [i][j] = 10 * i + j;

    }

  }

     print("%d", *(arr[1] + 9));

     return 0;

}

What is the output of the above program?

  1. ((a))

    14

  2. ((b))

    20

  3. ((c))

    30

  4. ((d))

    24

Show Answer
Answer: ((d))

24

code:

#include<stdio.h>

int main(){

int arr[4][5];

int i, j;

for(i =0; i<4; i++){

for (j =0; j<5; j++){

arr [i][j] = 10 +i + j;

}

}

print("%d", *(arr[1] + 9));

return 0;

}

Key Points

  1. C doesn't check array boundaries. A segmentation fault will only occur if you try to dereference a pointer to memory that your program doesn't have permission to access. Simply going past the end of an array is unlikely to cause that behavior. Undefined behavior is just that - undefined. It may appear to work just fine, but you shouldn't be relying on its safety.
  2. Your program causes undefined behavior by accessing memory past the end of the array. In this case, it looks like one of your str[i] = c writes overwrite the value in i.

Explanation:

*(arr[1] + 9) can be written as arr[1][9].

as C doesn't follow bound check and follow the row major ordering

arr[1][5] = arr[2][0]  // arr[1][4] will be first row of array and then arr[2][0] will be second row of array 

arr[1][6] = arr[2][1]

arr[1][7] = arr[2][2]

arr[1][8] = arr[2][3]

arr[1][9] = arr[2][4]

arr[2][4] = 10i + j = 102+4 = 24

Option 4 is the answer.

21

Consider the following sets, where n > 2:

S1: Set of all n x n matrices with entries from the set {a, b, c}

S2: Set of all functions from the set {0,1, 2, ..., n2 — 1} to the set {0,1,2}

Which of the following choice(s) is/are correct?

  1. ((a))

    There does not exist an injection from S1 to S2.

  2. ((b))

    There exists a bijection from S1 to S2

  3. ((c))

    There exists a surjection from S1 to S2.

  4. ((d))

    There does not exist a bijection from S1 to S2

Show Answer
Answer: ((a))

There does not exist an injection from S1 to S2.

Answer: Option 2 and Option 3 

Concept:

Injection:

It is Mapping/function between two sets A and B (f: A→ B) such that every element in A mapped to a unique element in B. ( one-one function )

Surjection:

It is Mapping/function between two sets A and B (f: A→ B) such that every element in B has a pre-image in A.(onto Function).

Bijection:

It is Mapping/function between two sets A and B such that every element in A is mapped to exactly one element in B and every element in B has an exactly one pre-image in A.

Explanation:

S1: Set of all n x n matrices with entries from the set {a, b, c}

So in an n× n Matrix total number of the position will be n2 and these positions can be filled from any element from the set { a, b, c}

Hence the total number of matrices possible = 3n2{3^{{n^2}}}

S2:Set of all functions from the set {0,1, 2, ..., n2 — 1} to the set {0,1,2}

number of all functions in S2 will be 3n2{3^{{n^2}}}.

Option 1:There does not exist an injection from S1 to S2.

This is not correct. Since the cardinality of both the sets S1 and S2 is equal. So we can draw one-to-one mapping between Set S1 and S2.

Option 2: There exists a bijection from S1 to S2.

This is correct. Since the cardinality of both the sets S1 and S2 is equal. and hence Bijective function/mapping possible between Set S1 and S2.

Option 3: There exists a surjection from S1 to S2.

This is correct. Since Bijection possible and hence Surjection also possible. Bijection implies Surjection but not vice versa.

Option 4:There does not exist a bijection from S1 to S2.

This is not correct.

22

Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?

  1. ((a))

    L1 ∩ L̅2

  2. ((b))

    L1 ∪ (L2 ∪ L̅2)

  3. ((c))

    Lˉ1∪Lˉ2‾\overline {{{\bar L}_1} \cup {{\bar L}_2}}

  4. ((d))

    (L1 ∩ L2) ∪ (L̅1 ∩ L2)

Show Answer
Answer: ((a))

L1 ∩ L̅2

Answer: Option 2 , Option 3 and Option 4

Concept:

  • CFLs are not closed under Intersection , complement operation. Means Intersection of two CFLs may or may not be CFL.
  • But Intersection of CFL with Regular is Closed.
  • CFLS are closed under operation Union. Means Union of two CFLs is CFL only.

Explanation:

Given: L1 is Regular Language , L2  is CFL.

Option 1:  L1 ∩ L̅2 

Complement of CFL may not be CFL. So

= Regular ∩\cap  (non CFL)

= Non CFL

Option 2: L1 ∪ (L2 ∪ L̅2)

"(L2 ∪ L̅2)"  will be complete language

= Regular  ∪\cup  Complete language

= Regular 

Hence Every Regular language also CFL according to Chomsky Hierarchy. This option is correct .

Option 3:  Lˉ1∪Lˉ2‾\overline {{{\bar L}_1} \cup {{\bar L}_2}}

 Lˉ1∪Lˉ2‾≡L1∩L2\overline {{{\bar L}_1} \cup {{\bar L}_2}} \equiv {L}_1 \cap {L}_2

And (CFL ∩\cap Regular Language ) is CFL only.

So this option is also correct.

Option 4: (L1 ∩ L2) ∪ (L̅1 ∩ L2) 

≡(Regular∩CFL)∪(Regular‾∩CFL)\equiv(Regular \cap CFL) \cup (\overline{Regular} \cap CFL)

≡(CFL∪CFL)\equiv ( CFL \cup CFL )

≡CFL\equiv CFL

So this option is also correct.

23

In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?

  1. ((a))

    Control Flow Graph (CFG)

  2. ((b))

    Symbol table

  3. ((c))

    Three address code

  4. ((d))

    A bstract Syntax Tree (AST)

Show Answer
Answer: ((a))

Control Flow Graph (CFG)

Answer: Option 2

Concept:

Intermediate Representation of Source Program: Means We have various stages in the Compilation process each of these stages accepts some form of source program as an input and produces a different form as output. These forms are called Intermediate Representation.

Control Flow Graph: Control flow Graph is a type of Structure of Intermediate Representation which represent entire flow of a program in terms of some variable notation.

Symbol Table: Symbol Table is a Data Structure used by various stages of compilers to capture information regarding variables, functions, classes, objects etc. Hence it is not a Intermediate Representation.

Three Address code: Three address code is a Linear form of Syntax Trees. It is generated by Code optimization phase of the compiler. It is a Intermediate Representation.

Abstract Syntax Tree: Abstract syntax Tree basically tree like structure of the source code. It is generated by Parser. It is a Intermediate Representation.

So Option 2 will be not an intermediate Representation of the source program.

24

Which of the following statement(s) is/are correct in the context of CPU scheduling?

  1. ((a))

    Implementing preemptive scheduling needs hardware support.

  2. ((b))

    Turnaround time includes waiting time.

  3. ((c))

    Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori.

  4. ((d))

    The goal is to only maximize CPU utilization and minimize throughput.

Show Answer
Answer: ((a))

Implementing preemptive scheduling needs hardware support.

Answer: Option 1,Option 2  and Option 3

Concept:

Turn Around Time:

Turn Around Time is the total time interval of a process from the moment it enters into Ready Queue to it finishes.

Throughput:

The number of Tasks that get completed in a unit time is called Throughput.

Explanation:

Option 1: Implementing preemptive scheduling needs hardware support.

The Given Statement is correct. Hardware support is needed to Preempt the running process and transfer the control back to OS.

The timer interrupt gets generated when time quanta expire and then the interrupted process will be enqueued to the ready queue and then schedule another process to the CPU.

Option 2: Turnaround time includes waiting time.

This Statement is also correct. Turn Around Time includes both waiting time and Burst time.

Waiting time = turn around time - CPU time

turn around time = waiting time + CPU time

Option 3: Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori.

This Statement is also correct. Round Robin Policy Gives each process an equal fair share of CPU irrespective of what CPU time of a process is.

It simply Schedules a process for a fixed time quanta and switches to another process when time quanta expire. 

Option 4: The goal is to only maximize CPU utilization and minimize throughput.

This Statement is incorrect. The goal of CPU Scheduling is to maximize the CPU utilization, maximization throughput and minimize the response time.

we would want to increase the no of processes that get completed per unit time. more process gets completed then we can add more process in our system. 

So we want to maximize the Throughput.

25

Choose the correct choice(s) regarding the following propositional logic assertion S:

S : ((P ∧ Q)→ R)→ ((P ∧ Q)→ (Q → R))

  1. ((a))

    The antecedent of S is logically equivalent to the consequent of S.

  2. ((b))

    S is a tautology

  3. ((c))

    S is a contradiction

  4. ((d))

    S is neither a tautology nor a contradiction.

Show Answer
Answer: ((a))

The antecedent of S is logically equivalent to the consequent of S.

Concept

  • An antecedent is the first half of a hypothetical proposition, whenever the if-clause precedes the then-clause.
  • A consequent is the second half of a hypothetical proposition.

Symbol:

∧ = AND = .

V = OR = +

¬ = NOT ≡ ̅ 

1 = TRUE

Formula:

A → B = ¬ A ∨ B = ¬ A + B

¬ (A.B) = A̅ + B̅

Calculation:

Antecedent of S:

(P ∧ Q)→ R ≡   ¬ (P.Q) + R ≡ P̅ + Q̅  + R 

Consequent of S:

(P ∧ Q)→ (Q → R) ≡ ¬ (P.Q) + (¬ Q + R

≡ P̅ + Q̅ + Q̅ + R ≡ P̅ + Q̅  + R 

Hence the antecedent of S is logically equivalent to the consequent of S.

S = ((P ∧ Q)→ R)→ ((P ∧ Q)→ (Q → R))

S = ¬ (¬ (P.Q) + R) + (¬ (P.Q) + (¬ Q + R))

S = P.Q.¬R + ¬ P + ¬ Q. + (¬ Q + R)

S = P.Q.R̅ + P̅ + Q̅  + Q̅ + R

S = P.Q.R̅ +  P̅ + Q̅ + R   

S = (P̅ + P)(P̅ + Q.R̅ ) + Q̅ + R     // A + A̅B = A+ B 

S = P̅ + Q.R̅  + Q̅ + R

S = P̅ + Q̅ + R̅  + R

S = 1  = TRUE                                     // A + A̅ = 1

S is a tautology

26

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.

The value of |A - B| is _______

27

Consider the following deterministic finite automaton (DFA).

The number of strings of length 8 accepted by  the above automaton is _____

28

If x and y are two decimal digits and (0.1101)2 = (0.8xy5)10, the decimal value of x + y is ______

29

Consider a set-associative cache of size 2 KB (1 KB = 210 bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used for accessing the cache. If the width of the tag field is 22 bits, the associativity of the cache is _______

30

Consider a computer system with DMA support. The DMA module is transferring one 8-bit character in one CPU cycle from a device to memory through cycle stealing at regular intervals. Consider a 2 MHz processor. If 0.5% processor cycles are used for DMA, the data transfer rate of the device is __________ bits per second.

31

A data file consisting of 1,50,000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is sorted on the primary key RollNo. The size of a record pointer for this disk is 7 bytes. Each student-record has a candidate key attribute called ANum of size 12 bytes. Suppose an index file with records consisting of two fields, ANum value and the record pointer to the corresponding student record, is built and stored on the same disk. Assume that the records of data file and index file are not split across disk blocks. The number of blocks in the index file is _______

32

For a given biased coin, the probability that the outcome of a toss is a head is 0.4. This coin is tossed 1,000 times. Let X denote the random variable whose value is the number of times that head appeared in these 1,000 tosses. The standard deviation of X (rounded to 2 decimal places) is _____

33

Consider the following ANSI C function:

int SomeFunction (int x, int y)

{

if ( (x == 1) I I (y == 1)) return 1;

if (x == y) return x;

if (x > y) return SomeFunction(x - y, y);

if (y > x) return SomeFunction(x, y - x);

}

The value returned by SomeFunction(15, 255) is _______.

34

Suppose that P is a 4 × 5 matrix such that every solution of the equation Px = 0 is a scalar multiple of [2 5 4 3 1]T​. The rank of P is _________

35

Suppose that f : R → R is a continuous function on the interval [-3, 3] and a differentiable function in the interval (-3, 3) such that for every x in the interval, f'(x) ≤ 2. If f(-3) = 7, then f(3) is at most _______.

36

Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties:

  1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
  2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.

Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?

  1. ((a))

    23

  2. ((b))

    21

  3. ((c))

    25

  4. ((d))

    30

Show Answer
Answer: ((a))

23

Answer: Option 1

Data:

abbccddeee

frequencies are 

LetterFrequency
a1
b2
c2
d2
e3

 

 

codes :

LettercodeFrequency
a0001
b112
c102
d0012
e013

Hence length of the encoded string = 3×1 + 2× 2 + 2× 2 + 3× 2 + 2× 3 = 23 

Note:

Those Binary codes satisfy both the condition given in the question. 

for example, consider the following codes 

a=000

b=001

c=10

d=11

e=01; then this violates the second condition because b alphabetically comes before c; b and c have the same frequency and according to question b should have length at most c and d but here the length of b is greater than c and d.

37

Assume a two-level inclusive cache hierarchy, L1 and L2, where L2 is the larger of the two. Consider the following statements.

S1: Read misses in a write through L1 cache do not result in writebacks of dirty lines to the L2.

S2: Write allocate policy must be used in conjunction with write through caches and no-write allocate policy is used with writeback caches.

Which of the following statements 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: ((d))

S1 is true and S2 is false

Answer: Option 4

Key Points

Write Allocate Policy: 

In this policy, Suppose we are trying to write into some block in the cache but the block is not available in cache i.e. write miss occurs then the block is loaded after write miss operation and the write performed in the cache. 

No-Write Allocate Policy:

In this policy, if a write miss occurs in the cache then the write operation will be performed directly in Main Memory.

Explanation:

Statement 1:Read misses in a write-through L1 cache do not result in writebacks of dirty lines to the L2.

In Write through a cache write operation will be performed on both cache and Main Memory simultaneously. so

in the case of the write-through cache, there are no dirty lines/blocks possible on Read misses. 

Hence this statement is correct.

Statement 2: Write allocate policy must be used in conjunction with write-through caches and no-write allocate policy is used with writeback caches.

This statement is not correct.

Typically Write-back cache is used with write-allocate policy and write-through caches with no-write allocate.

38

Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1’s by a 0. Consider the following example.

Input sequence: 00100011000011100

Output sequence: 00000001000001100

A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.

The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively.

Assume the initial state of the Mealy machine is 0.

What are the Boolean expressions corresponding to t and y in terms of s and b ?

  1. ((a))

    t = b

    y = sb

  2. ((b))

    t = s + b

    y = sb

  3. ((c))

    t = s + b

    y = sb̅

  4. ((d))

    t = b

    y = sb̅

Show Answer
Answer: ((a))

t = b

y = sb

Answer: Option 1

Concept:

Mealy Machine: 

In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs i.e. inputs and output mentioned on transition edges.

Explanation:

Given: 

Mealy Machine which replaces the first 1 in any subsequence of consecutive 1’s by a 0.

s = current state

t = next state

b = next incoming bit

t = output bit

consider the following Mealy Machine for the given scenario.

we need to find expression for t and y

t is next state,

at state '0' in Mealy Machine t = b

at state '1' in Mealy Machine t = b

now we left with two options Option 1 and Option 4.

y is output bit 

at state '0' in Mealy Machine both the output bit is 0, we can not be sure which is true sb or sb̅.

at state '1' in Mealy Machine one output which loops to itself s=1 and b=1 then sb=1 and output bit is also 1**.**

Hence t = b and y = sb

39

In an examination, a student can choose the order in which two questions (QuesA and QuesB) must be attempted.

  • If the first question is answered wrong, the student gets zero marks.
  • If the first question is answered correctly and the second question is not answered correctly, the student gets the marks only for the first question.
  • If both the questions are answered correctly, the student gets the sum of the marks of the two questions.

The following table shows the probability of correctly answering a question and the marks of the question respectively. 

questionProbability of answering correctlymarks
QuesA0.810
QuesB0.520
<br>

Assuming that the student always wants to maximize her expected marks in the examination, in which order should she attempt the questions and what is the expected marks for that order (assume that the questions are independent)?

  1. ((a))

    First QuesB and then QuesA. Expected marks 14

  2. ((b))

    First QuesB and then QuesA. Expected marks 22

  3. ((c))

    First QuesA and then QuesB. Expected marks 14.

  4. ((d))

    First QuesA and then QuesB. Expected marks 16.

Show Answer
Answer: ((d))

First QuesA and then QuesB. Expected marks 16.

The correct answer is option 4

Explanation

First, we answer A, then B:

Expected marks = the probability that A is wrong × 0  + the probability that A is correct  ×  probability that B is wrong  × 10

                             + the probability that A is correct ×  probability that B is correct × 30

                             =0.2 × 0+0.8 × 0.5 × 10+0.8 × 0.5 × 30

                             =0+4+12

                             =16

If first, we answer B, then A:

Expected marks = the probability that B is wrong   × 0 + the probability that B is correct  ×  probability that A is wrong  × 10

                            + the probability that B is correct ×  probability that A is correct × 30

                           = 0.5 × 0+0.2 × 0.5 × 20+0.8 × 0.5 × 30

                           = 0+2+12

                           =14

So, the Correct answer is  First QuesA and then QuesB and  Expected marks 16.

40

Consider the following ANSI C code segment:

z = x + 3 + y -> f1 + y -> f2;

for (i = 0; i < 200; i = i + 2){

if (z > i) {

P = p + x + 3;

q = q + y -> f2;

} else {

p = p + y -> f2;

q = q + x + 3;

}

}

Assume that the variable y points to a struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, g, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y -> f1 or y -> f2 ) in the optimized code, respectively, are:

  1. ((a))

    203 and 2

  2. ((b))

    403 and 102

  3. ((c))

    303 and 102

  4. ((d))

    303 and 2

Show Answer
Answer: ((d))

303 and 2

Answer: Option 4

Common Subexpression elimination (CSE)

CSE is a technique in code Optimization, where we try to eliminate redundant expression in our code by simply calculating and storing in a temporary variable so that the expression does not need to evaluated again and again in the code/loop.

Explanation:

In the code given statement that are repeating in every iteration of loop are x+3 and y->f2; after performing common subexpression elimination we get 

temp1 = x + 3

temp2 =  y -> f1

temp3 = y -> f2

z = temp1 + temp2 + temp3;

for (i = 0; i < 200; i = i + 2){

if (z > i) {

P = p + temp1;

q = q + temp3;

} else {

p = p + temp3;

q = q +temp1;

}

}

now we get 1 addition + 2 addition + 100 addition (i=i+2) + 2*100(if/else) = 303 additions and 2 deference operations.

41

The relation scheme given below is used to store information about the employees of a company, where empId is the key and deptId indicates the department to which the employee is assigned. Each employee is assigned to exactly one department.

emp(empId, name, gender, salary, deptId)

Consider the following SQL query:

select deptId, count(⋆)

from emp

where gender = "female" and salary > (select avg(salary) from emp)

group by deptId;

The above query gives, for each department in the company, the number of female employees whose salary is greater than the average salary of

  1. ((a))

    female employees in the department.

  2. ((b))

    employees in the department.

  3. ((c))

    employees in the company.

  4. ((d))

    female employees in the company.

Show Answer
Answer: ((c))

employees in the company.

Answer: Option 3

Explanation:

 (select avg(salary) from emp)

This part of the Query will get evaluated first and gives " Average Salary of all employees in the company."

select deptId, count(⋆)

from emp

where gender = "female" and salary > (select avg(salary) from emp)

group by deptId;

this will count for each department no of employees who are female and whose salary is greater than the average salary.

Lets take an example 

EmpidNameGenderSalarydeptid
1AMale2000CSE
2BFemale3000CSE
3CMale4000CSE
4DFemale5000CSE
5EMale3000ME
6FFemale4000ME
7GMale4000ME
8HFemale2000ME
9IMale1000CE
10JFemale2000CE
11KMale4000CE
12LFemale5000CE
13MMale3000EC
14NFemale4000EC
15OFemale5000EC

 

(select avg(salary) from emp) this will return 3400 as the average salary.

and final Query result will be

Deptidcount
CSE1
ME1
CE1
EC2
42

Let S be the following schedule of operations of three transactions T1, T2 and T3 in a relational database system:

R2(Y), R1(X), R3(Z), R1(Y), W1(X), R2(Z), W2(Y), R3(X), W3(Z)

Consider the statements P and Q below:

P: S is conflict-serializable.

Q: If T3 commits before T1 finishes, then S is recoverable.

Which one of the following choices is correct?

  1. ((a))

    P is true and Q is false.

  2. ((b))

    Both P and Q are true.

  3. ((c))

    P is false and Q is true.

  4. ((d))

    Both P and Q are false.

Show Answer
Answer: ((a))

P is true and Q is false.

Answer: Option 1

Concept:

Conflict Serializable Schedule: For A Schedule to be Conflict Serializable Schedule It’s Precedence graph should not contain any cycle.

Recoverable Schedule: If A schedule Contain Dirty Read (W-R dependency) then transaction which contain the Read operation must commit after the Transaction which contains Write operation.

And If schedule does not contain Dirty Read It is trivially Recoverable. 

Explanation :  

Statement 1: S is Conflict Serializable.

It is correct. As Precedence graph does not contain cycle, i.e.  Precedence graph is Acyclic.

T1T2T3
R2(y)
R1(x)
R3(z)
R1(y) W1(x)
R2(z) W2(y)
R3(x) W3(z)

 

Statement 2: If T3 commits before T1 finishes , then S is recoverable. 

Consider the below Diagram Schedule

at the point “×\times ”, Crash\rollback happens then we cannot Rollback\undo transaction T3 because it is already committed. So In this case S is not Recoverable. Hence given Statement is false.

43

A bag has r red balls and b black balls. All balls are identical except for their colours. In a trial, a ball is randomly drawn from the bag, its colour is noted and the ball is placed back into the bag along with another ball of the same colour. Note that the number of balls in the bag will increase by one, after the trial. A sequence of four such trials is conducted. Which one of the following choices gives the probability of drawing a red ball in the fourth trial ? 

  1. ((a))

    rr+b\frac{r}{r+b}

  2. ((b))

    (rr+b)(r+1r+b+1)(r+2r+b+2)(r+3r+b+3)\left(\frac{r}{r+b}\right)\left(\frac{r+1}{r+b+1}\right)\left(\frac{r+2}{r+b+2}\right)\left(\frac{r+3}{r+b+3}\right)

  3. ((c))

    (r+3r+b+3)\left(\frac{r+3}{r+b+3}\right)

  4. ((d))

    (rr+b+3)\left(\frac{r}{r+b+3}\right)

Show Answer
Answer: ((a))

rr+b\frac{r}{r+b}

Answer: Option 1

Explanation:

No of trials = 4 

colors combination possible for drawing the red ball in the fourth trial: { RRRR, RRBR, RBRR, RBBR, BRRR, BRBR, BBRR, BBBR }

P(Red ball in 4th Trial) =(  RR+B\frac{R}{{R + B}}× R+1R+B+1\frac{{R + 1}}{{R + B + 1}}×R+2R+B+2\frac{{R + 2}}{{R + B + 2}}× R+3R+B+3\frac{{R + 3}}{{R + B + 3}} )+ ( RR+B\frac{R}{{R + B}}× R+1R+B+1\frac{{R + 1}}{{R + B + 1}}× BR+B+2\frac{B}{{R + B + 2}}× R+2R+B+3\frac{{R + 2}}{{R + B + 3}})+ (RR+B\frac{R}{{R + B}}× BR+B+1\frac{B}{{R + B + 1}}× R+1R+B+2\frac{{R + 1}}{{R + B + 2}}× R+2R+B+3\frac{{R + 2}}{{R + B +3}}) +( RR+B\frac{{R }}{{R + B }}× BR+B+1\frac{{B }}{{R + B + 1}}× B+1R+B+2\frac{{B+1 }}{{R + B+2 }}×  R+1R+B+3\frac{{R+1 }}{{R + B+3 }})  +( BR+B\frac{{B}}{{R + B }}× RR+B+1\frac{{R }}{{R + B+1 }}× R+1R+B+2\frac{{R+1 }}{{R + B+2 }}× R+2R+B+3\frac{{R + 2 }}{{R + B+3 }} )+( BR+B\frac{B}{{R + B}}× RR+B+1\frac{R}{{R + B+1}}× B+1R+B+2\frac{B+1}{{R + B+2}}× R+1R+B+3\frac{R+1}{{R + B+3}})+( BR+B×B+1R+B+1×RR+B+2×R+1R+B+3\frac{B}{{R + B}}\times \frac{B+1}{{R + B+1}}\times \frac{R}{{R + B+2}}\times \frac{R+1}{{R + B+3}} )+( BR+B×B+1R+B+1×B+2R+B+2×RR+B+3\frac{B}{{R + B}}\times \frac{B+1}{{R + B+1}}\times \frac{B+2}{{R + B+2}}\times \frac{R}{{R + B+3}})

 

= (R)(R+1)(R+2)(R+3)+(R)(R+1)(B)(R+2)+(R)(B)(R+1)(R+2)+(R)(B)(B+1)(R+1)+(B)(R)(R+1)(R+2)+(B)(R)(R+1)(B+1)+(B)(B+1)(R)(R+1)+(B)(B+1)(B+2)(R)(R+B)(R+B+1)(R+B+2)(R+B+3)\frac{({R})({R+1})({R+2})({R+3})+({R})({R+1})({B})({R+2})+({R})({B})({R+1})({R+2})+({R})({B})({B+1})({R+1})+({B})({R})({R+1})({R+2})+({B})({R})({R+1})({B+1})+({B})({B+1})({R})({R+1})+({B})({B+1})({B+2})({R})}{{(R + B )(R+B+1)(R+B+2)(R+B+3)}}

after solving the above expression 

= RR+B\frac{R}{{R + B}}

44

Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial X3 + X + 1. Suppose the message m4m3m2m1m0 = 11000 is to be transmitted. Check bits c2c1c0 are appended at the end of the message by the transmitter using the above CRC scheme. The transmitted bit string is denoted by m4m3m2m1m0c2c1c0. The value of the check bit sequence c2c1c0 is

  1. ((a))

    101

  2. ((b))

    100

  3. ((c))

    111

  4. ((d))

    110

Show Answer
Answer: ((b))

100

Answer: Option 2

Concept:

If the polynomial is of order n then the number bits generated by CRC generator is n + 1.

Data:

Message = m4m3m2m1m0 = 11000

CRC polynomial =X3+X+1 

Explanation:

CRC polynomial = 1.X3+ 0.X2 + 1.X+ 1.X0 ≡ 1011

Message bits will be 11000 000

Calculation:

  

Hence 100 will be appended to message bits (m4m3m2m1m0 = 11000).

45

Consider the following ANSI C program:

#include <stdio.h>

#include <stdlib.h>

struct Node{

int value;

struct Node ⋆next;};

int main(){

struct Node ⋆boxE, ⋆head, ⋆boxN; int index = 0;

boxE = head = (struct Node ⋆) malloc (sizeof(struct Node));

head -> value = index;

for (index = 1; index <=3; index++){

boxN = (struct Node ⋆) malloc(sizeof(struct Node));

boxE -> next = boxN;

boxN -> value = index;

boxE = boxN; }

for (index = 0; index <= 3; index++) {

printf("value at index %d is %d\m", index, head -> value);

head = head -> next;

printf("value at index %d is %d\n", index + 1, head -> value);}}

Which one of the statement below is correct about the program ?

  1. ((a))

    It has a missing return which will be reported as an error by the compiler.

  2. ((b))

    It dereferences an uninitialized pointer that may result in a run-time error.

  3. ((c))

    Upon execution, the program goes into an infinite loop.

  4. ((d))

    Upon execution, the program creates a linked-list of five nodes.

Show Answer
Answer: ((b))

It dereferences an uninitialized pointer that may result in a run-time error.

Answer: Option 2

Explanation: 

Assume size int data type is of 2 bytes And size of Pointer is 4 bytes. Memory is byte addressable and all dynamic memory requests are successfully assigned. "" is garbage value.

  • boxE=head= (struct Node *) malloc(sizeof(struct Node));

After this statement a new Block will be created dynamically and its address will be assigned to head and boxE. 

  • head → value = index;

after this statement we following situation in memory.( 2000 is the address of memory block assigned)

  • Now for loop starts

for (index =1; index<=3; index++){

boxN = (struct Node *) malloc (sizeof(struct Node));

boxE → next = boxN;

boxN → value = index;

boxE = boxN;

}

  • After loop we have

Now in 2nd for loop 

  • At index = 0; output:

Value at index 0 is 0

Value at index 1 is 1

  • At index = 1; output:

Value at index 1 is 1

Value at index 2 is 2

  • At index = 2; output:

Value at index 2 is 2

Value at index 3 is 3

  • At index = 3; output:

Value at index 3 is 3

Here it will give Dereferencing Error.

option 2 is correct .

46

Consider the following two statements about regular languages:

S1: Every infinite regular language contains an undecidable language as a subset.

S2: Every finite language is regular.

Which one of the following choices is correct?

  1. ((a))

    Only S2 is true.

  2. ((b))

    Neither S1 nor S2 is true.

  3. ((c))

    Only S1 is true.

  4. ((d))

    Both S1 and S2 are true.

Show Answer
Answer: ((d))

Both S1 and S2 are true.

Key Points

Note that the following statements are true

  1. Every infinite regular language L has a subset S which is undecidable.
  2. Every infinite regular language L has a subset S which is unrecognizable.
  3. Every infinite language L has a subset S which is undecidable.
  4. Every infinite language L has a subset S which is unrecognizable.

So, S1 and S2 both are correct.  

the correct answer is option 4

Explanation: for statements S2 consider the following explanation

every infinite language (regular or not) has an undecidable subset.

With the particular focus on regular languages, the intended solution might have been something like using the pumping lemma to find x,y,z such that xynz is in your language for every n,  then consider the subset A = {xynz | n ∈ N}, where A is your favorite undecidable set of natural numbers.

it proves s1 is correct.

47

For two n-dimensional real vectors P and Q, the operation s(P, Q) is defined as follows:

\(s\left( {P,;Q} \right) = \mathop \sum \limits_{i = 1}^n \left( {p\left[ i \right].Q\left[ i \right]} \right)\)

Let L be a set of 10-dimensional non-zero vectors such that for every pair of distinct vectors P, Q ∈ L, s(P, Q) = 0. What is the maximum cardinality possible for the set L ?

  1. ((a))

    100

  2. ((b))

    10

  3. ((c))

    9

  4. ((d))

    11

Show Answer
Answer: ((b))

10

Answer: Option 2

Concept:

Dot product of two vectors:

lets take following example

example : \(\left[ {\begin{array}{{20}{c}} a\ b\ c \end{array}} \right].\left[ {\begin{array}{{20}{c}} l\ m\ n \end{array}} \right]\) = \({\left[ {abc} \right]^T} \times \left[ {\begin{array}{*{20}{c}} l\ m\ n \end{array}} \right]\) = al + bm + cn 

Explanation:

\(s\left( {P,;Q} \right) = \mathop \sum \limits_{i = 1}^n \left( {p\left[ i \right].Q\left[ i \right]} \right)\)

This is nothing but a dot product of two vectors P and Q.

Let's solve for 3 - 3-dimensional non-zero vectors. we need to find pair of Non zero vectors such that their dot product is zero.

consider 3 vectors as

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

you consider any pair from those 3 vectors the dot product will always be zero.

An interesting point is that now if you try to add any vector in the set it will result in a non-zero dot product with at least one of the vectors.

 So with 3 Dimensions, Max cardinality possible is 3.

Similarly, with 10 dimensions, the Max cardinality possible is 10.

\(\left[ {\begin{array}{{20}{c}} 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0 \end{array}} \right]\), \(\left[ {\begin{array}{{20}{c}} 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0 \end{array}} \right]\), \(\left[ {\begin{array}{{20}{c}} 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0 \end{array}} \right]\),\(\left[ {\begin{array}{{20}{c}} 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0 \end{array}} \right]\),\(\left[ {\begin{array}{{20}{c}} 0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0 \end{array}} \right]\),\(\left[ {\begin{array}{{20}{c}} 0\ 0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0 \end{array}} \right]\),\(\left[ {\begin{array}{{20}{c}} 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 0\ 0 \end{array}} \right]\),\(\left[ {\begin{array}{{20}{c}} 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 0 \end{array}} \right]\),\(\left[ {\begin{array}{{20}{c}} 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1\ 0 \end{array}} \right]\),\(\left[ {\begin{array}{{20}{c}} 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 1 \end{array}} \right]\)

48

For a statement S in a program, in the context of liveness analysis, the following sets are defined:

USE(S): the set of variables used in S

IN(S): the set of variables that are live at the entry of S

OUT(S): the set of variables that are live at the exit of S

Consider a basic block that consists of two statements, S1 followed by S2.

Which one of the following statements is correct?

  1. ((a))

    OUT(S1) = USE(S1) ∪ IN(S2)

  2. ((b))

    OUT(S1) = IN(S2)

  3. ((c))

    OUT(S1) = IN(S1) ∪ USE(S1)

  4. ((d))

    OUT(S1) = IN(S2) ∪ USE(S2)

Show Answer
Answer: ((b))

OUT(S1) = IN(S2)

Answer: Option 2

Concept:

Live variables: A variable said to be live at some point/instance if from that point/instance to the exit of a program that variable is used ( only R-value Occurrence ) without being redefined( no L-value Occurrence ). 

Explanation:

Option 1:OUT(S1) = USE(S1) ∪ IN(S2)

If a variable being redefined and used at the same statement S1 then it will not be live at OUT(S1). But USE(S1) will add those variables to the set OUT(S1) as well.

So this is incorrect.

Option 2: OUT(S1) = IN(S2)

This is Correct. Every variable which is live at IN(S2) is Live at OUT(S1). Because it is given that statement S1 followed by S2..

Option 3: OUT(S1) = IN(S1) ∪ USE(S1)

Consider a variable which was live before S1 but not after S1 then IN(S1) will add those variable to OUT(S1). It is wrong.

So this is incorrect.

Option 4:OUT(S1) = IN(S2) ∪ USE(S2)

Consider a variable which is being redefined and used at the same statement S2 then USE(S2) will be added to OUT(S1) , which is wrong.

So this is Incorrect.

49

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:

T(n)=a.T(nb)+f(n)T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)

Which one of the following options is correct about the recurrence T(n)?

  1. ((a))

    If f(n) is nlog⁡2(n)\frac{n}{{{{\log }_2}(n)}}, then T(n) is θ(log2(n)).

  2. ((b))

    If f(n) is n log2(n), then T(n) is θ(n log2(n)).

  3. ((c))

    If f(n) is O(nlogb(a) - ϵ) for some ϵ > 0, then T(n) is θ(nlogb(a)).

  4. ((d))

    If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))

Show Answer
Answer: ((c))

If f(n) is O(nlogb(a) - ϵ) for some ϵ > 0, then T(n) is θ(nlogb(a)).

Key Points

The recurrence T(n) = aT(n/b) + f(n), where a, b are constants. Then

(A) If f(n) = O(nlogb(a) - ϵ) for some constant ε > 0, then T(n) = θ(nlogb(a))..

(B) If f(n) = θ(nlogb(a))., then T(n) =θ(nlogbalogn)\theta (n^{log_b a} logn)

(C) If f(n) = Ω (nlogb(a) + ϵ) for some constant ε > 0, and if f satisfies the smoothness condition a × f(n/b) ≤ c × f(n) for some constant c < 1, then T(n) = Θ(f(n)).

The above statements illustrate the master's theorem.

option 3 is the correct answer

50

Suppose the following functional dependencies hold on a relation U with attributes P, Q, R, S, and T:

P → QR

RS → T

Which of the following functional dependencies can be inferred from the above functional dependencies?

  1. ((a))

    P → R

  2. ((b))

    PS → T

  3. ((c))

    R → T

  4. ((d))

    PS → Q

Show Answer
Answer: ((a))

P → R

Functional Dependencies are P → QR and RS → T

Option 1: Inferred

{P}+ = {PQR} 

P → R is inferred from the given functional dependencies.

Option 2 and option 4: Inferred

{PS}+ = {PSQRT}

PS → T is inferred from the given functional dependencies.

PS → Q is inferred from the given functional dependencies.

Option 3:  Cannot be Inferred

{R}+ = {R} 

R → T is not inferred from the given functional dependencies.

Therefore option 1, 2 and 4 are correct

51

For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR = 10110.

Which of the following languages is/are context-free?

  1. ((a))

    {wxxRwR | w, x ∈ {0, 1}*}

  2. ((b))

    {wxwR | w, x ∈ {0, 1}*}

  3. ((c))

    {wxwRxR | w, x ∈ {0, 1}*}

  4. ((d))

    {wwRxxR | w, x ∈ {0, 1}*}

Show Answer
Answer: ((a))

{wxxRwR | w, x ∈ {0, 1}*}

option 1 is correct

{wxxRwR | w, x ∈ {0, 1}*} is context-free language as it can be done using a stack. here is the way

  • push all letters of w in the stack
  • push all letters of x in the stack
  • if a new letter matches with the top of the stack, pop it

at the end stack will be empty so, it is context free language

option 2 is correct

{wxwR | w, x ∈ {0, 1}*} is context-free.

push all the letters before w in the stack, skip x, now pop an element from the stack for each new letter,(top of the stack will match with each new letter due to WR ). So, it is context-free

option 3 is incorrect 

{wxwRxR | w, x ∈ {0, 1}*} is Not context-free, we have to match w with wRwR but the top of the stack contains x, so not possible.

option 4 is correct

{wwRxxR | w, x ∈ {0, 1}*} is Context-free language ,

first match w with wR then match x with xR using a stack.

option 1,2,4 are correct.

52

Consider the following multi-threaded code segment (in a mix of C and pseudocode), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2:

int x = 0; // global

Lock L1; // global

main() {

create a thread to execute foo(); // Thread T1

create a thread to execute foo(); // Thread T2

wait for the two threads to finish execution;

print (x);}

foo() {

int y = 0;

Acquire L1;

x = x + 1;

y = y + 1;

Release L1;

print (y); }

Which of the following statement(s) is/are correct ?

  1. ((a))

    Both T1 and T2, in both the processes, will print the value of y as 1.

  2. ((b))

    At least one of P1 and P2 will print the value of x as 4

  3. ((c))

    Both P1 and P2 will print the value of x as 2.

  4. ((d))

    At least one of the threads will print the value of y as 2.

Show Answer
Answer: ((a))

Both T1 and T2, in both the processes, will print the value of y as 1.

Answer: Option 1 and Option 3.

Explanation:

Option 1:  Both T1 and T2, in both the processes, will print the value of y as 1.

This Option is Correct. Since Every thread makes a new temporary variable (y) and then it increments y in mutually exclusive fashion.

Option 2: At least one of P1 and P2 will print the value of x as 4.

This Option is not correct. x=4 is not possible.

Option 3:Both P1 and P2 will print the value of x as 2.

This Option is correct. 

each process, two threads are created and they increment variable x after acquiring the lock L1.So no interleaving execution of increment statement possible.

Print(x) will be performed when both threads complete execution. Hence both the process will print x as 2 only.

Option 4:At least one of the threads will print the value of y as 2.

This Option is not correct. because both threads have a different copy of y variable in their memory even one thread increment variable it will reflect in its own memory, not in the other thread's memory. so y = 2 not possible.

53

Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock (L). The following scheme is used to own a resource instance:

function OWNRESOURCES(Resource R)

Acquire lock L / / a global lock

if R is available then

Acquire R

Release lock L

else

if R is owned by another process P then

Terminate P, after releasing all resources owned by P

Acquire R

Restart P

Release lock L

end if

end if

end function

Which of the following choice(s) about the above scheme is/are correct?

  1. ((a))

    The scheme may lead to starvation.

  2. ((b))

    The scheme may lead to live-lock.

  3. ((c))

    The scheme ensures that deadlocks will not occur.

  4. ((d))

    The scheme violates the mutual exclusion property.

Show Answer
Answer: ((a))

The scheme may lead to starvation.

Answer: Option 1, Option 2, Option 3

Concept:

Livelock:  A situation in which two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work.

Consider the following example 

Process 0Process 1
flag[0] = true;
while(flag[1]){
flag[0]=false;
/delay/
flag[0]=true;
}
/* CRITICAL SECTION */
flag[0]=false;		flag[1] = true;
while (flag[0]) {
flag[1] = false;
/delay /;
flag[1] = true;
}
/ CRITICAL SECTION/;
flag[1] = false;

In this example, if you see both the processes just changing states of their flag variable and none of them can enter into the critical section provided mutual exclusion is satisfied. 

Note:

*Assume that preemption does not occur in executing the statement of inside while loops in the above example.

Explanation:

  • OWNRESOURCES(R) function does the following tasks

acquire lock L

  • If R is available

acquire resource R 

release lock L

  • If R is not available , it is already acquired by a process P

Terminate P and release all resources owned by P.

acquire R.

Restart P

Release L

Option 1: The scheme may lead to starvation.

this is correct.

Let's take an example consider 2 processes (P, Q1)  initially no other process currently in the System. First Q1 executes OWNRESOURCES(R) 

  • Q1 acquires L
  • Q1 acquires R
  • Q1 Release L

Now as soon as Q1 finishes Q2 arrives and executes the same 3 tasks and completes then as soon as Q2 finishes Q3 arrives and so on process Q's keep arriving in the system and the process P never gets to execute.

so Starvation possible.

Option 2: The scheme may lead to live-lock.

Let's take an example consider 2 processes (P, Q)  initially no other process currently in the System. First P executes OWNRESOURCES(R)

  • P acquires L
  • P acquires R
  • Release L

immediately after Releasing L, P gets preempted Q starts OWNRESOURCES(R) 

  • Q acquires L
  • Terminate P and release all resources owned by P.
  • acquire R.
  • Restart P
  • Release L

immediately after Releasing L, Q gets preempted P starts OWNRESOURCES(R) 

  • P acquires L
  • Terminate Q and release all resources owned by Q.
  • acquire R.
  • Restart Q
  • Release L

and so on the same thing will repeat itself.

This is not Deadlock right. This is Livelock.

Option 3: The scheme ensures that deadlocks will not occur.

This statement is correct as Deadlock not possible. because even if there circular waiting exists one process simply terminates the other processes which hold the resources.

so no hold and wait, so Deadlock will not occur.

Option 4: The scheme violates the mutual exclusion property.

This statement is not correct because every process has to go through the function OWNRESOURCES(R) to own resource and even if a Resource is owned by another process then it will get terminated and restarted; at a time no 2 processes can own a single resource. So Mutual exclusion property is satisfied.

54

If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(s) the unsigned integer on a little endian computer?

  1. ((a))

    0x0001

  2. ((b))

    0x6665

  3. ((c))

    0x0100

  4. ((d))

    0x4243

Show Answer
Answer: ((a))

0x0001

2,3 is the correct answer. 

concept:

If you split hex number into bytes,

In hexadecimal representation, each digit corresponds to 4 binary digits.(i.e 2 hex digits = 8 bits= 1 byte). 

If  little-endian representation used then byte arrangement is as follows:

byte_nbyte_n-1…………..…byte_1

if Big endian representation is used then the byte arrangement is as follows:

byte_1byte_2…………..…byte_n

Within the byte no change in the bit sequence.

A) 0x0001 is incorrect.

Little-endian 0x0001  gives you 01 as the first byte and 00 as the second byte, So the corresponding big-endian representation is 0x0100.

Hex (0x0001) is equal to 1 in decimal 

Hex(0x0100) is equal to 256 in decimal. 

Their difference is -255.

B) 0x6665 is correct

Little-endian 0x6665  gives you 65 as the first byte and 66 as the second byte, So the corresponding big-endian representation is 0x6566.

Hex (0x6665) is equal to 26213 in decimal 

Hex(0x6566) is equal to 25958 in decimal. 

Their difference is 255.

C) 0x0100 is correct

Little-endian 0x0100  gives you 00 as the first byte and 01 as the second byte, So the corresponding big-endian representation is 0x0100

Hex(0x0100) is equal to 256 in decimal.,

Hex (0x0001) is equal to 1 in decimal 

Their difference is 255.

D)0x4243 is incorrect

Little-endian 0x4243  gives you 43 as first byte and 42 as the second byte, So the corresponding big-endian representation is 0x4342

Hex(0x4243) is equal to 16963  in decimal.

Hex (0x4342) is equal to  17218 in decimal. 

Their difference is -255.

So 2,3 is the answer

55

Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below.

The objective is to find the shortest-cost path from the router R to routers P and Q. Assume that R does not initially know the shortest routes to P and Q. Assume that R has three neighbouring routers denoted as X, Y, and Z. During one iteration, R measures its distance to its neighbours X, Y, and Z as 3, 2, and 5, respectively. Router R gets routing vectors from its neighbours that indicate that the distance to router P from routers X, Y, and Z are 7, 6, and 5, respectively. The routing vector also indicates that the distance to router Q from routers X, Y, and Z are 4, 6, and 8, respectively. Which of the following statement(s) is/are correct with respect to the new routing table of R, after updation during this iteration ?

  1. ((a))

    The next hop router for a packet from R to P is Y.

  2. ((b))

    The distance from R to Q will be stored as 7

  3. ((c))

    The next hop router for a packet from R to Q is Z.

  4. ((d))

    The distance from R to P will be stored as 10.

Show Answer
Answer: ((a))

The next hop router for a packet from R to P is Y.

Answer: Option 1 and Option 2

Explanation:

given data 

R → X3
R → Y2
R → Z5

To Router P

CostFrom
7X
6Y
5Z

To Router Q

CostFrom
4X
6Y
8Z

 

Cost of R → P = Min (R → X + X → P, R → Y + Y → P, R → Z + Z → P)

Cost of R → P = Min (3 + 7, 2 + 6, 5 + 5)

Cost of R → P = Min (10, 8, 10) = 8

Cost of R → P = 8 and next hop is Y.

Cost of R → Q = Min (R → X + X → Q, R → Y + Y → Q, R → Z + Z → Q)

Cost of R → Q = Min (3 + 4, 2 + 6, 5 + 8)

Cost of R → Q = Min (7, 8, 13)

Cost of R → Q = 7 and next hop is X.

56

Consider the following directed graph: 

Which of the following is/are correct about the graph?

  1. ((a))

    The graph does not have a strongly connected component.

  2. ((b))

    For each pair of vertices u and v, there is a directed path from u to v.

  3. ((c))

    ​The graph does not have a topological order.

  4. ((d))

    A depth-first traversal starting at vertex S classifies three directed edges as back edges.

Show Answer
Answer: ((a))

The graph does not have a strongly connected component.

Answer: Option 3 and Option 4 

Concept:

Strongly Connected Graph:

The directed graph in which every vertex can be reached from any other vertex.

Strongly Connected Component:

A strongly connected component of a directed graph is a maximal strongly connected subgraph.

Topological Order:

Graph must not contain any cycle for topological ordering to exist in a graph.

Explanation:

Option 1:The graph does not have a strongly connected component.

This statement is false as There exists ASBC, this rectangle is a strongly connected component as we can reach all the vertices in the component from any vertex in the component.

Option 2: For each pair of vertices u and v, there is a directed path from u to v.

This statement is also false as from vertex O we can not reach any other vertex in the graph.

Option 3:​ The graph does not have a topological order.

As you can observe there exists cycles in the graph so topological ordering not possible.

This Statement is correct.

Option 4: A depth-first traversal starting at vertex S classifies three directed edges as back edges.

This Statement is correct.

In DFS tree back edges indicates cycle in the graph. but that does not mean no of back edges == no of cycles.

57

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∈ divisible by three.

  1. ((a))

    (0 + 1(01*0)1)

  2. ((b))

    (0*(1(010)1))

  3. ((c))

    (0 + 11 + 10(1 + 00)01)

  4. ((d))

    ( 0+ 11 + 11(1 + 00)00)

Show Answer
Answer: ((a))

(0 + 1(01*0)1)

Answer: Option 1, Option 2 and Option 3

Concept :

A DFA is a finite Automata which is Deterministic in Nature i.e. On every State transition on each input symbol must be defined.

DFA is represented by 5 tuples (Q, ∑, δ, q0, F)

Q – finite set of states.

∑ - Set of input symbols.

δ – Transition Functions

q0 – Initial State

F – Set of Final State

Explanation :

DFA of the given language given below

Where , Q = { Q0, Q1, Q2 }

 ∑ = { 0, 1}

q0 =  Q0  //Initial State

F = { Q0 } // Set of Final States

Now options can be constructed by concatenating the Transitions.

Option 1:

After

Now for this RE will be (0+10101)<sup></sup>.

Option 2:

This just a Variation of option 1.

  ∵\because (R1 + R2)* ≡\equiv  (R1</sup>R2<sup>)*.

 ∴\therefore (0+10101)≡\equiv  (0<sup></sup>(10101)<sup></sup>).

Option 3:

(0+11+10(1+00)**</sup>**01)<sup>

This option also generate all the Strings that are divisible by 3.

Option 4:

( 0 + 11 + 11(1+00)<sup></sup>00) Generate “11100” which is clearly not divisible by 3. Hence Here Option 4 is incorrect.

So Options 1 , 2 and 3 are only correct.

58

Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below.

The page size is 4 KB (1 KB = 210 bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2 GB (1 GB = 230 bytes) virtual memory which is mapped to 2 GB of physical memory. The minimum amount of memory required for the page table of P across all levels is _______ KB.

59

Consider the following ANSI C program

#include <stdio.h>

int foo(int x, int y, int q)

{

if ((x <= 0 && (y <= 0))

return q;

if (x <= 0)

return foo(x, y - q, q);

if (y <= 0)

return foo(x - q, y, q);

return foo (x, y - q, q) + foo(x - q, y, q);

}

int main()

(

int r = foo(15, 15, 10);

printf("%d", r);

return 0;

}

The output of the program upon execution is ________

60

Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is _______

61

Consider the following augmented grammar with {#, @, <, >, a, b, c} as the set of terminals.S' → S

S → S # cS

S → SS

S → S @

S → < S >

S → a

S → b

S → c

Let I0 = CLOSURE({S' → ∙ S}). The number of items in the set GOTO(GOTO(I0, <), <) is _______

62

Consider a Boolean function f(w, x, y, z) such that 

f(w, 0, 0, z) = 1

f(1, x, 1, z) = x + z

f(w, 1, y, z) = wz + y

The number of literals in the minimal sum-of-products expression of f is ______

63

Consider a pipelined processor with 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Each stage of the pipeline, except the EX stage, takes one cycle. Assume that the ID stage merely decodes the instruction and the register read is performed in the EX stage. The EX stage takes one cycle for ADD instruction and two cycles for MUL instruction. Ignore pipeline register latencies.

Consider the following sequence of 8 instructions:

ADD, MUL, ADD, MUL, ADD, MUL, ADD, MUL

Assume that every MUL instruction is data-dependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data-dependent on the MUL instruction just before it. The speedup is defined as follows:

Speedup=Execution:time:without:operand:forwardingExecution:time:with:operand:forwardingSpeedup = \frac{{Execution{:}time{:}without{:}operand{:}forwarding}}{{Execution{:}time{:}with{:}operand{:}forwarding}}

The Speedup achieved in executing the given instruction sequence on the pipelined processor (rounded to 2 decimal places) is _______

64

Consider a network using the pure ALOHA medium access control protocol, where each frame is of length 1,000 bits. The channel transmission rate is 1 Mbps (= 106 bits per second). The aggregate number of transmissions across all the nodes (in-cluding new frame transmissions and retransmitted frames due to collisions) is modelled as a Poisson process with a rate of 1,000 frames per second. Throughput is defined as the average number of frames successfully transmitted per second. The throughput of the network (rounded to the nearest integer) is

65

In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all the vertices in the graph shown above is ______

Attempt this paper under real exam conditions

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

Start Timed Attempt