GATE CSE 2003
View Questions

GATE CSE

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total
View Question
Consider the following three claims I. (n + k)m = $$\Theta \,({n^m})$$ where k and m are constants II. 2n+1 = O(2n) II
View Question
In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time
View Question
The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity
View Question
The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the positi
View Question
Let G=(V,E) be an undirected graph with a subgraph G1=(V1,E1). Weights are assigned to edges of G as follows. $$$w(e) =
View Question
Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ……., vj
View Question
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction fro
View Question
What is the weight of a minimum spanning tree of the following graph?
View Question
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
View Question
In a bottom-up evaluation of a syntax directed definition, inherited attributes can
View Question
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship betwe
View Question
Consider the grammar shown below $$\eqalign{ & S \to iEtSS'\,|\,\,a \cr & S' \to eS\,|\,\,\varepsilon \c
View Question
Consider the translation scheme shown below $$\eqalign{ & S \to TR \cr & R \to + T\left\{ {pr{\mathop{\rm
View Question
Consider the grammar shown below. $$\eqalign{ & S \to CC \cr & C \to cC\,|\,d \cr} $$ This grammar is
View Question
Which of the following statements is FALSE?
View Question
Consider the syntax directed definition shown below. Here, gen is a function that generates the output code, and newtem
View Question
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically
View Question
A 2 km long broadcast LAN has 107 bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2 × 108 m/s. What
View Question
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
View Question
Which of the following assertions is FALSE about the Internet Protocol (IP)?
View Question
The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to t
View Question
Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?
View Question
The following is a scheme for floating point number representation using $$16$$ bits. Let $$s, e,$$ and $$m$$ be the n
View Question
For a pipelined $$CPU$$ with a single $$ALU$$, consider the following situations $$1.\,\,\,\,\,$$ The $$j+1$$ instructio
View Question
Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequen
View Question
Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct ite
View Question
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
View Question
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.
View Question
Consider the following functional dependencies in a database. $$\eqalign{ & \,\,\,\,Date\,\,of\,\,Birth\,\, \to \,
View Question
Consider the set of relations shown below and the SQL query that follows. Students: (Roll_number, Name, Date_of_birth) C
View Question
Consider the following SQL query: Select distinct a1, a2, ..., an From r1, r2, ..., rm Where P; For an arbitrary p
View Question
Which of the following scenarios may lead to an irrecoverable error in a database system?
View Question
Consider three data items D1, D2, and D3, and the following execution schedule of transactions T1, T2, and T3. In the di
View Question
Assuming all numbers are in $$2's$$ complement representation, which of the following numbers is divisible by $$11111011
View Question
The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For
View Question
Consider the following circuit composed of $$XOR$$ gates are non-inverting buffers. The non-inverting buffers have del
View Question
A 1- input, 2- output synchronous sequential circuit behaves as follows. Let $${z_k},\,{n_k}$$ denote the number of $$0’
View Question
Consider the $$ALU$$ shown below If the operands are in $$2's$$ complement representation, which of the following oper
View Question
The following resolution rule is used in logic programming. Derive clause $$\left( {P \vee Q} \right)$$ from clauses $$\
View Question
Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = $${\raise0.5ex\hbox{$\scriptstyle 1$} \kern-0.1em
View Question
Let $$A$$ be a sequence of $$8$$ distinct integers sorted in ascending order. How many distinct pairs of sequence, $$B$$
View Question
$$n$$ couples are invited to a party with the condition that every husband should be accompanied by his wife. However,
View Question
$$m$$ identical balls are to be placed in $$n$$ distinct bags. You are given that $$m \ge kn$$, where $$k$$ is a natural
View Question
Let $$G$$ be an arbitrary graph with $$n$$ nodes and $$k$$ components. If a vertex is removed from $$G$$, the number of
View Question
Consider the following system of linear equations $$$\left[ {\matrix{ 2 & 1 & { - 4} \cr 4 & 3 &amp
View Question
$$A$$ graph $$G$$ $$=$$ $$(V, E)$$ satisfies $$\left| E \right| \le \,3\left| V \right| - 6.$$ The min-degree of $$G$$
View Question
How many perfect matchings are there in a complete graph of 6 vertices?
View Question
$$A$$ system of equations represented by $$AX=0$$ where $$X$$ is a column vector of unknown and $$A$$ is a square matrix
View Question
$$\mathop {Lim}\limits_{x \to 0} \,{{Si{n^2}x} \over x} = \_\_\_\_.$$
View Question
A uni-processor computer system only has two processes, both of which alternate $$10$$ $$ms$$ $$CPU$$ bursts with $$90$$
View Question
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the proces
View Question
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S and T. The code for the proces
View Question
In a system with $$32$$ bit virtual addresses and $$1$$ $$KB$$ page size, use of one-level page tables for virtual to ph
View Question
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically
View Question
A processor uses $$2$$-level page tables for virtual to physical address translation. Page tables for both levels are st
View Question
A processor uses $$2$$-level page tables for virtual to physical address translation. Page tables for both levels are st
View Question
Using a larger block size in a fixed block size file system leads to
View Question
Which of the following statements is FALSE?
View Question
The following program fragment is written in a programming language that allows global variables and does not allow nest
View Question
The following program fragment is written in a programming language that allows global variables and does not allow nest
View Question
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++
View Question
Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses d
View Question
Assume the following C variable declaration int * A[10], B[10][10]; Of the following expressions I. A[2] II. A[2] [3] II
View Question
Consider the C program shown below. #include < stdio.h > #define print(x) printf("%d ", x) int x; void Q(int z) {
View Question
The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ * $$denotes the same set as
View Question
Consider the set $$\sum {^ * } $$ of all strings over the alphabet $$\,\sum { = \,\,\,\left\{ {0,\,\,\,1} \right\}.\sum
View Question
Consider the $$NFA$$ $$M$$ shown below. Let the language accepted by $$M$$ be $$L.$$ Let $${L_1}$$ be the language acc
View Question
Consider the following deterministic finite state automation $$M.$$ Let $$S$$ denote the set of seven bit binary stri
View Question
Nobody knows yet if $$P=NP$$. Consider the language $$L$$ defined as follows $$L = \left\{ {\matrix{ {{{\left( {0 + 1
View Question
If the strings of a language $$L$$ can be effectively enumerated in lexicographic (i.e., alphabetic$$(c)$$ order, which
View Question
A single tape Turing Machine $$M$$ has two states $${q_0}$$ and $${q_1}$$, of which $${q_0}$$ is the starting state. The
View Question
Define Languages $${L_0}$$ and $${L_1}$$ as follows $${L_0} = \left\{ { < M,\,w,\,0 > \left| {M\,\,} \right.} \rig
View Question
EXAM MAP
Joint Entrance Examination
JEE MainJEE AdvancedWB JEEBITSAT
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN