GATE CSE 2003 PYQ

In a permutation of n distinct integers, an inversion is a pair such that and . What would be the worst case time complexity of the insertion Sort algorithm, if the inputs are restricted to permutatio

Let G = (V,E) be an undirected graph with a sub-graph G1 = (V1,E1), Weight are assigned to edges of G as follows A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with

The cube root of a natural number n is defined as the largest natural number m such that . The complexity of computing the cube root of n(n is represented in binary notation) is

Consider the following three claims 1. , where k and m are constants 2. 3. Which of these claims are correct?

Consider the following graph Among the following sequences (I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b e Which are depth first traversals of the above graph?

The usual implementation of Insertion Sort to sort ab array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we us

What is the weight of a minimum spanning tree of the following graph?

Consider the following recurrence relation T(1)=1 T(n+1)=T(n)+ for all n 1 The value of T( ) for m 1 is

Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?

Consider the syntax directed definition shown below Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. A

Consider the translation scheme shown below S TR R + T {print ('+');}R | T num {print (num.val);} Here num is a token that represents an integer and num. val represents the corresponding integer value

Consider the grammar shown below In the predictive parse table. M, of this grammar, the entries M[S',e] and M[S',$] respectively are

Which of the following statements is FALSE?

Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

A 2 km long brodcast LAN has bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2* m/s. What is the minimum packet size that can be used on this network ?

Which of the following functionalities must be implemented by a transport protocol over and above the network protocol ?

The subnet mask for a particular network is 255.255.31.0 Which of the following pairs of IP addresses could belong to this network ?

Which of the following assertions is false about the internet Protocol (IP) ?

Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only

For a pipelined CPU with a single ALU, consider the following situations 1. The (j + 1)-th instruction uses the result of j-th instruction as an operand 2. The execution of a conditional jump instruct

Using a larger block size in a fixed block size file system leads to

Consider the following assembly language program for a hypothetical processor. A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments. Which of the following instr

Consider the following assembly language program for a hypothetical processor. A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments. If the initial value of regi

Consider the following functional dependencise in a database: The relation (Roll_number,Name,Date_of_brith,Age) is

Consider the following SQL query select distinct al, a2,........., an from r1, r2,........, rm where P For an arbitrary predicate P,this query is equivalent to which of the following relational algebr

Consider three data items D1,D2 and D3 and the following execution schedule of transactions T1,T2 and T3. In the diagram, R(D) and W(D) denote the actions reading and writing the data item D respectiv

Consider the set of relations shown below and the SQL query that follow: Students:(Roll_number,Name,Date_of_birth) Courses:(Course_number,Course_name,Instructor) Grades:(Roll_number,Course_number,Grad

Consider the set {a, b, c} with binary operators + and x defined as follows : For example, a + c = c, c + a = a, c x b = c and b x c = a. Given the following set of equations : (a x x) + (a x y) = c (

Assuming all numbers are in 2's complement representation, which of the following number is divisible by 11111011?

Consider the ALU shown below If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C0 only (+ and - denot

A 1-input, 2-output synchronous sequential circuit behaves as follows. Let denote the number of 0's and 1's respectively in initial k bits of the input ( ). The circuit outputs 00 until one of the fol

The following is a scheme for floating point Number System using 16 bits. Let s,c and m be the number represented in binary in the sign, exponent, and mantissa fields respectively. Then the flouting p

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

The literal count of a Boolean Algebra is the sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz) is 4. What are the minimum possible literal

Consider the following circuit composed of XOR gates and non-inverting buffers The non-inverting buffers have delays = 2ns and = 4ns as shown in the figure. Both XOR gates and al wires have zero delay

Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = 1/2, the values of P(A|B) and P(B|A) respectively are

A program consists of two modules executed sequentially. Let f1(t) and f2(t) respectively denote the probability density functions of time taken to execute the two modules. The probability density fun

Consider the set of all strings over the alphabet ={0,1}. with the concatenation operator for strings

Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3

A piecewise linear function f (x) is plotted using thick solid lines in the figure below (the plot is drawn to scale). If we use the Newton-Raphson method to find the roots of f(x) = 0 using x0, x1 an

m identical balls are to be placed in n distinct bags. You are given that m kn, where k is a natural number 1. In how many ways can the balls be placed in the bags if each bag must contain at least k

Let G = (V,E) be a direction graph with n vertices. A path from to in G is sequence of vertices ( , ,....., ) such that ( , ) E for all k in i through j - 1. A simple path is a path in which no vertex

Let : A B be injective (one-to-one) function. Define as: g(C) = {f (x)| x C), for all subsets C of A. Define as : h(D) = {x | x A, f (x) D}, for all subsets D of B. Which of the following statements i

Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between.

Consider the following logic program P Which of the following first order sentences is equivalent to P?

Let (S, ) be a partial order with two minimal elements a and b, and a maximum element c. Let P:S {True, False} be a predicate defined on S . Suppose that P(a) = True, P(b) =False and P(x) p(y) for all

Which of the following is a valid first order formula? (Here and are first order formulae with x as their only free variable)

Consider the following system of linear equations Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of , does this system of equations

n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings pos

Consider the following formula and its two interpretations I1: Domain : the set of natural numbers is a prime number divides x I2; same as I1 except that is a composite number. Which of the following

A graph G = (V, E) satisfies |E| 3|V|-6. The min-degree of G is defined as . Therefore, min-degree of G cannot be

Let = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows : g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11. Let denote the i-th prime number ( =2). For a non-empty string , wher

the following resolution rule is used in logic programming: Derive clause(P Q) from clauses (P R),(Q JR) Which of the following statements related to this rule is FASLE?

In a permutation of n distinct integers, an inversion is a pair such that and . If all permutation are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1..

How many perfect matching are there in a complete graph of 6 vertices?

Consider the following graph Among the following sequences (I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b e Which are depth first traversals of the above graph?

The following are the starting and ending times of activities A,B,C,D,E,F,G and H respectively in chronological order: . Here, denotes the starting time and denotes the ending time of activity X. W ne

In a system with 32 bit virtual addresses and 1 KB page size, use of one-level page tables for virtual to physical address translation is not practical because of

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The m

A processor uses 2-level page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide. The m

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below. Process P: while (1) { W: print '0'; print '0'; X: }

Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the processes P and Q is shown below. Process P: while (1) { W: print '0'; print '0'; X: }

A uni-processor computer system only has two processes, both of which alternate 10 ms CPU bursts with 90 ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both process

Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL) || ((P->data next->data) && f(p->next))); } For a

Let S be a stack of size n 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X secon

The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions. global int i = 100, j = 5; void P(x) { int i = 10; print(

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the i

In a heap with n elements with the smallest element at the root, the smallest element ban be found in time

Consider the C program shown below. #include #define print(x) printf("%d ", x) int x; void Q(int z) { z += x; print(z); } void P(int *y) { int x = *y + 2; Q(x); *y = x - 1; print(x); } main(void) { x

Let T(n) be the number of different binary search trees on n distinct elements. Then , where is

Consider the following C function. float f(float x, int y) { float p, s; int i; for (s=1, p=1, i=1; i < y; i ++) { p*= x/i; s+=p; } return s; } For large values of y, the return value of the function

In the following C program fragment, j, k, n and TwoLog_n are integer variables, and A is an array of integers. The variable n is initialized to an integer 3, and TwoLog_n is initialized to the value

The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions. global int i = 100, j = 5; void P(x) { int i = 10; print(

Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree What is t

A data structure is required for storing a set of integers such that each of the following operations can be done in O(logn) time, where n is the number of elements in the set. 1. Delection of the sma

Assume the following C variable declaration int *A [10], B[10][10]; Of the following expressions I A[2] II A[2][3] III B[1] IV B[2][3] which will not give compile-time errors if used as left hand side

Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changi

The regular expression 0*(10*)* denotes the same set as

A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is Which of the following statements is true?

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

Consider the following deterministic finite state automaton M. Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that

Define languages L0 and L1 as follows : L0 = { | M halts on w} L1 = { | M does not halts on w} Here is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a

Consider two languages L1 and L2 each on the alphabet . Let be a polynomial time computable bijection such that . Further, let be also polynomial time computable. Which of the following CANNOT be true

Consider the grammar shown below. S C C C cC | d The grammar is

If the strings of a language L can be effectively enumerated in lexicographic (i.e. alphabetic) order, which of the following statements is true?

Nobody knows yet if P = NP. Consider the language L defined as follows : Which of the following statements is true ?