Computer Science Test - 5

Table representation of the processes burst time, CPU and I/O time is shown as :

The correct answer is 3

To determine the maximum number of errors that can be detected for the given code, we need to find the minimum Hamming distance between any pair of the valid codewords. The Hamming distance between two codewords is the number of positions at which the corresponding bits are different.

Let's calculate the Hamming distance between each pair of codewords:

• 11001100 and 00110011: The Hamming distance is 8 (since all bits are different).
• 11001100 and 11111111: The Hamming distance is 4 (first, second, seventh, and eighth bits differ).
• 11001100 and 00000000: The Hamming distance is 4 (third, fourth, fifth, and sixth bits differ).
• 00110011 and 11111111: The Hamming distance is 4 (first, second, seventh, and eighth bits differ).
• 00110011 and 00000000: The Hamming distance is 4 (third, fourth, fifth, and sixth bits differ).
• 11111111 and 00000000: The Hamming distance is 8 (since all bits are different).

The minimum Hamming distance among the codewords is 4.

To determine the maximum number of errors that can be detected, we can use the property that a code with a minimum Hamming distance (d) can detect up to (d-1) errors.

Since the minimum Hamming distance (d) is 4, the maximum number of errors that can be detected is: [d - 1 = 4 - 1 = 3]

Thus, the maximum number of errors that can be detected for this code is: [ 3 ]

Take: k = 9

while(1 < 9 )

i= 1 * 3 = 3  (1^st time)

while(3 < 9 )

i= 3 * 3 = 9  (2^nd time)

while(3 < 9 )  // while will not be executed

For k = 9 while loop runs 2 times

Take: k = 10

while(1 < 10 )

i = 1 * 3 = 3  (1^st time)

while(3 < 10 )

i = 3 * 3 = 9  (2^nd time)

while(9 < 10 )

i = 9 * 3 = 27  (3^rd time)

while(27 < 10 )  // while will not be executed

For k = 10 while loop runs 3 times

Option 2:

For k = 9, ⌈log₃k⌉ = 2

For k = 10, ⌈log₃k⌉ = 3

 Hence option 2 is correct

Important Points:

To verify the answer, execute the code:

#include<stdio.h>

int main()

{

int c = 0;

int k=9, i = 1; // also put k = 10 to verify the options

while(i < k)

{

c++;

i = i * 3;

}

printf("%d",c);

}

LRU:

In this event of page fault, replace the page which is Least recently used

No. of page faults using LRU = 12

MRU:

In this event of page fault, replace the page which is Most recently used

No. of page faults using LRU = 16

Difference between the page faults using LRU and MRU is 16 – 12 = 4

Concept:

A decoder with k input lines has 2^k output lines.

Calculation:

The memory is byte addressable. So 4 KB = 2¹² B.

12 × 2¹⁰ decoder.

So, the number of input lines (m) = 12

Number of output lines (n) = 2^m = 2¹² = 4096

Hence, (m + n) = 12 + 4096 = 4108

The correct answer is option 4.

Key Points

1. Cannot be merged since lookaheads are different.

False, We can find the LALR stage by merging LR(1) states that have the same set of the first component. We can take the union of lookahead symbol of the respective item. The given LR (1) items can be merged as, 

X → c.X, c/d/$

X → .cX, c/d/$  

X → .x, c/d/$   

2. Can be merged but will result in S-R conflict.

3. Can be merged but will result in R-R conflict.

The given items have no reduced entry(means dot at end of the production) then there is no S-R conflict and R-R conflict in the given grammar. So clearly it says both option 2 and 3 are false. 

4. Cannot be merged since goto on c will lead to two different sets. 

False, Because goto is carried on Non-terminals symbols, not on terminal symbols, and c is a terminal symbol.

Hence the correct answer is 1, 2, 3 and 4.

Additional Information

Checking LALR conflicts:

Shortcut:

Let's consider the production A → αaβ and B→α and a,b are lookaheads of the grammar. Then S-R conflicts will occur when one production with reducing production and another one is a shift production. This will make the conflict when shifting terminal and lookahead are same then parsing table has multiple entries. And R-R conflicts have two productions with the same lookaheads.

• If there is no S-R conflict in LR(1) state it never be reflected in the LALR(1) parser.
• If there is no R-R conflict in LR(1) state it may be R-R conflict in LALR(1) parser.
• The parse generates tool 'YAAC' uses LALR(1) parsing algorithm.

Concepts:

V(S): signal operation will increment the semaphore variable, that is, S++.

P(S): wait operation will decrement the semaphore variable., that is, S--. 

Calculation:

Initial counting semaphore (I) = x

Signal operation = 14 V

Wait operation = 23 P

Final counting semaphore (F) = -3

F = x + 14V + 23P

-3 = x + 14(+1) + 23(-1)

∴ x = 6

Concepts:

A substring is a contiguous sequence of characters within a string.

Example:

String: “GATE”

Substring: G, A, T, E, GA, AT, TE, GAT, ATE, GATE and Λ (empty string or null string)

Therefore, number of substrings = 11

Formula:

If character is not repeated, then

POST-order traversal: 117, 126, 108, 131, 157, 182, 163, 148, 195 and 129

In a binary search tree, in-order traversal is sorted

In-order traversal: 108, 117, 126, 129, 131, 148, 157, 163, 182 and 195

Required Binary Search Tree:

PRE-order traversal: 129, 108, 126, 117, 195, 148, 131, 163, 157, 182