GATE CSE topic:computing PYQs & Answers — Page 83

Questions 821–830 of 975. Imported answers require independent review unless marked reviewed.

Assume that multiplying a matrix G_i of dimension p × q with another matrix G_j of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G_1G_2G_3...G_n can be done by parenthesizing in different ways. Define G_iG_ as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain G_1G_2G_3G_4G_5G_6 using parenthesization (G_1(G_2G_3))(G_4(G_5G_6)), G_2G_3 and G_5G_6 are the only explicitly computed pairs. Consider a matrix multiplication chain F_1F_2F_3F_4F_5, where matrices F_1, F_2, F_3, F_4 and F_5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F_1F_2F_3F_4F_5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

Your answerChoose one option.

F_1F_2 and F_3F_4 only

F_2F_3 only

F_3F_4 only

F_1F_2 and F_4F_5 only

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following C code. Assume that unsigned long int type length is 64 bits.

unsigned long int fun(unsigned long int n){

unsigned long int i, j = 0, sum = 0;

for (i = n; i > 1; i = i/2) j++;

for (; j > 1; j = j/2) sum++;

return(sum);

}

The value returned when we call fun with the input

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the unsigned 8-bit fixed point binary number representation below,

where the position of the binary point is between

and

. Assume

is the most significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above representation: (i) 31.500 (ii) 0.875 (iii) 12.100 (iv) 3.001 Which one of the following statements is true?

Your answerChoose one option.

None of (i), (ii), (iii), (iv) can be exactly represented

Only (ii) cannot be exactly represented

Only (iii) and (iv) cannot be exactly represented

Only (i) and (ii) cannot be exactly represented

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

The size of the physical address space of a processor is

bytes. The word length is

bytes. The capacity of cache memory is

bytes. The size of each cache block is

words. For a

-way set-associative cache memory, the length (in number of bits) of the tag field is

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following languages:

II.

III.

IV.

Which of the languages above are context-free?

Your answerChoose one option.

I and IV only

I and II only

II and III only

II and IV only

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following problems.

denotes the language generated by a grammar

denotes the language accepted by a machine

(I) For an unrestricted grammar

and a string

, whether

(II) Given a Turing machine

, whether

is regular (III) Given two grammars

and

, whether

(IV) Given an NFA

, whether there is a deterministic PDA

such that

and

accept the same language.

Which one of the following statements is correct?

Your answerChoose one option.

Only I and II are undecidable

Only III is undecidable

Only II and IV are undecidable

Only I, II and III are undecidable

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

A lexical analyzer uses the following patterns to recognize three tokens

, and

over the alphabet

Note that ‘

’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.

If the string

is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following parse tree for the expression

, involving two binary operators

and

Diagram for Computer Science and Information Technology question 38

Which one of the following is correct for the given parse tree?

Your answerChoose one option.

has higher precedence and is left associative;

is right associative

has higher precedence and is left associative;

is right associative

has higher precedence and is left associative;

is left associative

has higher precedence and is right associative;

is left associative

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

In a system, there are three types of resources: E, F and G. Four processes P₀, P₁, P₂ and P₃ execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P₂,F] is the maximum number of instances of F that P₂ would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation.

Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available.

Allocation: P₀ (E=1, F=0, G=1); P₁ (E=1, F=1, G=2); P₂ (E=1, F=0, G=3); P₃ (E=2, F=0, G=0).

Max: P₀ (E=4, F=3, G=1); P₁ (E=2, F=1, G=4); P₂ (E=1, F=3, G=3); P₃ (E=5, F=4, G=1).

From the perspective of deadlock avoidance, which one of the following is true?

Your answerChoose one option.

The system is in safe state.

The system is not in safe state, but would be safe if one more instance of E were available

The system is not in safe state, but would be safe if one more instance of F were available

The system is not in safe state, but would be safe if one more instance of G were available

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is

. Three semaphores empty, full and mutex are defined with respective initial values of 0,

and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal().

Producer:	Consumer:
do {<br> wait(P);<br> wait(mutex);<br> //Add item to buffer<br> signal(mutex);<br> signal(Q);<br>} while(1);	do {<br> wait(R);<br> wait(mutex);<br> //Consume item from buffer<br> signal(mutex);<br> signal(S);<br>} while(1);

Which one of the following assignments to P, Q, R and S will yield the correct solution?

Your answerChoose one option.

P: full, Q: full, R: empty, S: empty

P: empty, Q: empty, R: full, S: full

P: full, Q: empty, R: empty, S: full

P: empty, Q: full, R: full, S: empty

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE topic:computing PYQs

Question 31

Question 32

Question 33

Question 34

Question 35

Question 36

Question 37

Question 38

Question 39

Question 40