BARC Minimock Quiz-10 (App update required to attempt this test) for GATE & PSU CS Exams

Question 1

Which of the following is decidable. Assume given a turing machine M a state q, a symbol ‘x’ and a string ‘w’.

Question 2

A language is defined over ∑(a,b) To draw NFA that accept strings of length equal to n, no. of state is m. Which is true ?
The minimum no. of state in –

Question 3

Match the following groups
List-I
A) Synchronization
B) Mutual Exclusion
C) Critical Section
List-II
1) Piece of code that only one thread can execute at once.
2) Ensuring that only one thread does a particular thing at a time.
3) Using atomic operations to ensure cooperation between threads.

Question 4

In a 8 bit SISO register, if 16-bit data 1011 0101 0010 1010 is applied at the input. The minimum number of clock pulses required to transfer 16 bit data at the output is

Question 5

Consider the three half adders are connected in cascade whose sum and carry are ‘S’ & ‘C’ as shown in figure. Then what is the value of S and C ?

Question 6

Decompose the following table into BCNF:
R(ABCD)
A->C
C->A
AB->D

Question 7

Assume

and

relations have the following instances

Find number of tuples returned by the following query (ρ is used to rename the attribute)

Question 8

Find the number of min heap trees are possible with 7 elements such that every leaf node must be greater than all non-leaf nodes of the tree.

Question 9

Consider an undirected Graph A having b number of vertices and c number of edges. This graph is represented by adjacency list. In terms of Big-Oh what will be the time complexity of printing all the elements which are connected in this graph?

Question 10

Assume that multiplying a matrix

of dimension

with another matrix

of dimension

requires scalar multiplications. Computing the product of

matrices

can be done by parenthesizing in different ways. Define

as an explicitly computed pair for a given parathesization if they are directly multiplied. For example, in the matrix multiplication chain

using parenthesization

and

are the only explicitly computed pairs.
Consider a matrix multiplication chain

where matrices

and

are of dimensions

and

respectively. In the parenthesization of

that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

Question 11

Consider an initially empty symbol table implemented using a hash table of size ‘B’ with hash function h(C) = C mod B. In worst case for any possible sequence of inputs where N > B, what is the order of growth of inserting N (key, value) pairs with distinct key into table, if separate chaining is used to resolve collisions?

Question 12

Consider the following LL(1) parsing table

Which of the following string generates syntax error by the LL(1) parser with start symbol ‘E’?

Question 13

Which of the following protocol allows non-ASCII data to be sent through e-mail?

Question 14

Which of the following are the memory performance parameters?
(i) Access time and latency
(ii) Block size and block access time
(iii) Cycle time and bandwidth

Question 15

Suppose a system has physical memory which can accommodate ‘f’ frames. A process has to access f frames initially, all empty. If the total no of memory references to access the p distinct pages are m, what is the minimum and maximum no of page fault that will occur?