GATE CSE 2019 PYQ

Let G be any connection, weighted, undirected graph: I. G has a unique minimum spanning tree if no two edges of G have the same weight. II. G has a unique minimum spanning tree if, for every cut of G,

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible

There are n unsorted arrays: . Assume that n is odd. Each of contains n distinct elements. There are no common elements between any two arrays. The worst-case Asymptotic Notation of computing the medi

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The sequence sum . Determine the maximum of S(i,j), where . (Divide and conquer approach may be used). Ans

Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let be the placeholders for the non-terminals D, T, L or in the following table: Which one

Consider the augmented grammar given below: Let . The number of items in the set is __________.

Consider the following given grammar: S -> Aa A -> BD B -> b| ε D -> d| ε Let a, b, d and }, then the answer should be 3210). Answer:_____

Which one of the following kinds of derivation is used by LR parsers?

Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?

In an RSA cryptosystem, the value of the public modulus parameter n is 3007. If it is also is known that , where denotes Euler's Totient Function, then the prime factors of n which is greater than 50

Suppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?

Consider three machines M, N and P with IP addresses 100.10.5.2, 100.10.5.5 and 100.10.5.6 respectively. The subnet mask is set to 255.255.255.252 for all the three machines. Which one of the followin

Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate up link ports. The minimum number of switches needed is ____

A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60-MHz clock. To service a cache-miss, the memory controller fi

The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has 16 address lines denoted by . What is the range of address (in hexadecimal) of

A certain processor uses a fully associative cache of size 16 kB, The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are require

Consider the following relation P(X, Y, Z), Q(X, Y, T) and R(Y, V): How many tuples will be returned by the following relational algebra query? Answer:______

A relational database contains two tables Student and Performance as shown below: The primary key of the Student table is Roll_no. For the Performance table, the columns Roll_no. and Subject_code toge

Let the set of functional dependencies hold on a relation schema X = (PQRS). X is not in BCNF. Suppose X is decomposed into two schemas Y and Z where Y = (PR) and Z = (QRS). Consider the two statement

Which one of the following statements is NOT correct about the tree data structure used for creating an index of a relational database table?

Consider the following two statements about database transaction schedules: I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable. II. Timestamp-orde

Consider three 4-variable functions , which are expressed in sum-of-minterms For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as:

In 16-bit 2's complement representation, the decimal number -28 is:

What is the minimum number of 2-input NOR gates required to implement 4-variable function expressed in sum-of-minterms from as ? Assume that all the inputs and their complements are available. Answer

Which one of the following is NOT a valid identity?

Consider Z = X - Y where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:

Compute lim_(x→3) (x^4 − 81)/(2x^2 − 5x − 3)

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

Consider the first order predicate formula: Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets: S1: {1, 2, 3, ..., 100} S2: Set of all positive integers S3:

Let G be an arbitrary group. Consider the following relations on G: R1: if and only if such that R2: if and only if Which of the above is/are equivalence relation/relations?

Let G be an undirected complete graph on n vertices, where n 2. Then, the number of different Hamiltonian cycles in G is equal to

Let . Let . Consider the following two statements on |A|. I. II. Which of the above statements is/are TRUE?

Suppose Y is distributed uniformly in the open interval (1,6). The probability that the polynomial has only real roots is (rounded off to 1 decimal place) _________.

Compute

Let G be an arbitrary group. Consider the following relations on G: R1: ∀a,b ∈ G, a R1 b if and only if ∃g ∈ G such that a = g^−1 b g R2: ∀a,b ∈ G, a R2 b if and only if a = b^−1 Which of the above is

Let X be a square matrix. Consider the following two statements on X. I. X is invertible II. Determinant of X is non-zero Which one of the following is TRUE?

Let X be a square matrix. Consider the following two statements on X. I. X is invertible. II. Determinant of X is non-zero. Which one of the following is TRUE?

Consider the following matrix: The absolute value of the product of Eigenvalues of R is _________ .

Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the

Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the

The value of 3^51 mod 5 is ________.

Consider the following snapshot of a system running n concurrent processes. Process is holding instances of a resource R, . Assume that all instances of R are currently in use. Further, for all , proc

Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8kB and the word size is 4 bytes

The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointer The disk block size is 4 kB and the disk block addresses 32-bits long. The maximum

The following C program is executed on a Unix / Linux system: #include int main() { int i; for (i = 0; i < 10; i++) if (i % 2 == 0) fork(); return 0; } The total number of child process created is ___

Consider the following four processes with arrival times (in milliseconds) and their length of CPU burst (in milliseconds) as shown below: These processes are run on a single processor using preemptiv

Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100. The process are executed on a uniprocessor system running a time-sh

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distan

Consider the following C program: void convert(int n) { if (n<0) printf("%d",n); else { convert(n/2); printf("%d",n%2); } } Which one of the following will happen when the function convert is called w

Consider the following C program: #include int r(){ int static num=7; return num--; } int main() { for(r();r();r()) { printf("%d ",r()); }; return 0; } Which one of the following values will be displa

Consider the following statements: I. The smallest element in a max-heap is always at a leaf node. II. The second largest element in a max-heap is always a child of the root node. III. A max-heap can

Consider the following C program: #include int main() { float sum = 0.0, j = 1.0, i = 2.0; while (i / j > 0.0625) { j = j + j; sum = sum + i/j; printf("%f ", sum); } return 0; } The number of times va

Consider the following C program: #include int jumble(int x, int y) { x = 2 * x + y; return x; } int main() { int x = 2, y = 5; y = jumble(y, x); x = jumble(y, x); printf("%dn", x); return 0; } The va

Consider the following C program: #include int main(){ int arr[] = {1,2,3,4,5,6,7,8,9,0,1,2,5}, *ip = arr + 4; printf("%dn", ip[1]); return 0; } The number that will be displayed on execution of the p

Consider the following C program: #include int main() { int a[] = {2, 4, 6, 8, 10}; int i, sum = 0, *b = a + 4; for (i = 0; i < 5; i++ ) sum = sum + (*b - i) - *(b - i); printf("%dn", sum); return 0;

Which one of the following languages over is NOT context-free?

If L is a regular language over , which one of the following languages is NOT regular ?

For , let us consider the regular language . Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

Let be the set of all bijections from {1,...,5} to {1,...,5}, where denotes the identity function, i.e. . Let denote composition on functions. For a string , let . Consider the language . The minimum

Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet {0, 1}. S2: Set of all syntactically valid C programs. S3: Set of all languages over the alphabet {0, 1}.