The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?

Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be impl

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements

Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is gi

Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i

Consider the grammar $$E \to E + n\,|\,E \times n\,|\,n$$ For a sentence n + n × n, the handles in the right-sentential

Consider the grammar $$S \to \left( S \right)\,|\,a$$ Let the number of states in SLR(1), LR(1) and LALR(1) parsers for

The grammar $$A \to AA\,|\,\left( A \right)\,|\,\varepsilon $$ is not suitable for predictive-parsing because the gramm

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each gramma

Consider line number 3 of the following C - program. int main ( ) { /* Line 1 */ int I, N;

Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each gramma

Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum fra

Suppose that two parties A and B wish to setup a common secret key (D - H key) between themselves using the Diffie-Hellm

Packets of the same session may be routed through different paths in

The address resolution protocol (ARP) is used for

An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be

In a packet switching network, packets are routed from source to destination along a single path having two intermediate

The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:

In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since

Consider a three word machine instruction $$ADD$$ $$A$$ $$\left[ {{R_0}} \right],\,@\,B$$ The first operand (destination

A $$5$$ stage pipelined $$CPU$$ has the following sequence of stages $$IF$$-Instruction fetch from instruction memory, $

Consider a direct mapped cache of size $$32$$ $$KB$$ with block size $$32$$ bytes. The $$CPU$$ generates $$32$$ bit addr

Increasing the $$RAM$$ of a computer typically improves performance because

Consider the following data path of a $$CPU$$ The, $$ALU$$, the bus and all the registers in the data path are of ide

Consider the following data path of a $$CPU$$ The, $$ALU$$, the bus and all the registers in the data path are of ide

Consider the disk drive with the following specifications $$16$$ surfaces, $$512$$ tracks/surface, $$512$$ sectors/track

A device with data transfer rate $$10$$ $$KB/sec$$ is connected to a $$CPU.$$ Data is transferred byte-wise. Let the int

Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${\rm I}/O$$ instructions in them. For $$C

The data given below. Solve the problems and choose the correct answer. The normalized representation for the above f

The data given below. Solve the problems and choose the correct answer. Mantissa is a pure fraction in sign - magnitu

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is gi

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values

How many distinct binary search trees can be created out of 4 distinct keys?

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2.

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n interna

Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15,

The numbers 1, 2, ........, n are inserted in a binary search tree in some order. In the resulting tree, the right subtr

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list.

A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S)

A program P reads in 500 integers in the range [0, 100] representing the cores of 500 students. It then print the freque

In an inventory management system implemented at a trading corporation, there are several tables designed to hold all th

A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted i

Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database b

A table ‘student’ with schema (roll, name, hostel, marks), and another table ‘hobby’ with schema (roll, hobbyname) conta

Let r be a relation instance with schema R = (A, B, C, D). We define $${r_1} = {\pi _{A,B,C}}\left( r \right)$$ and $${r

The relation book (title, price) contains the titles and prices of different books. Assuming that no two books have the

A company maintains records of sales made by its salespersons and pays them commission based on each individual’s total

A table has fields, $$F1, F2, F3, F4, F5,$$ with the following functional dependencies: $$F1 \to F3.\,F2 \to F4.\,\,\,\

Consider a relation scheme $$R = \left( {A,\,B,\,C,\,D,\,E,\,H} \right)$$ on which the following functional dependencies

In a schema with attributes $$A, B, C, D,$$ and $$E,$$ following set of functional dependencies are given $$\eqalign{

Which one of the following statements about normal forms is FALSE?

Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below If we wish

The following table has two attributes $$A$$ and $$C$$ where $$A$$ is the primary key and $$C$$ is the foreign key refer

Let $${E_1}$$ and $${E_2}$$ be two entities in an E-R diagram with simple single-valued attributes, $${E_1}$$ and $${E_2

The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is a group under multiplication modulo $$1

Consider the following system of equations in three real variables $$x1, x2$$ and $$x3$$ : $$2x1 - x2 + 3x3 = 1$$ $$3x1

What are the eigen values of the following $$2x2$$ matrix? $$$\left[ {\matrix{ 2 & { - 1} \cr { - 4} & 5

Consider the set $$H$$ of all $$3$$ $$X$$ $$3$$ matrices of the type $$$\left[ {\matrix{ a & f & e \cr 0

Let $$n = {p^2}q,$$ where $$p$$ and $$q$$ are distinct prime numbers. How many numbers $$m$$ satisfy $$1 \le m \le n$$ a

Let $$G\left( x \right) = 1/\left( {1 - x} \right)2 = \sum\limits_{i = 0}^\infty {g\left( i \right)\,{x^1}} \,\,\,,$$

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two p

What is the value of $$\int\limits_0^{2\pi } {{{\left( {x - \pi } \right)}^3}\left( {\sin x} \right)dx} $$

Let $$G$$ be the simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of $$G$$ is 8. Then,

Let $$G$$ be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embe

The determination of the matrix given below is $$$\left[ {\matrix{ 0 & 1 & 0 & 2 \cr { - 1} & 1

The following is the Hasse diagram of the poset $$\left[ {\left\{ {a,b,c,d,e} \right\}, \prec } \right]$$ The poset is:

Let $$f$$ be a function from a set $$A$$ to a set $$B$$, $$g$$ a function from $$B$$ to $$C$$, and $$h$$ a function from

Which one of the following graphs is NOT planar?

Let $$A$$, $$B$$ and $$C$$ be non-empty sets and let $$X = (A - B) - C$$ and $$Y = (A - C) - (B - C)$$ Which one of the

Let R and S be any two equivalence relations on a non-emply set A. Which one of the following statements is TRUE?

Let f: $$\,B \to \,C$$ and g: $$\,A \to \,B$$ be two functions and let h = fog. Given that h is an onto function which o

Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets $${S_1}$$ a

A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on o

An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the tails ar

Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows: (i) sel

Let $$f(x)$$ be the continuous probability density function of a random variable X. The probability that $$a\, < \,X\

A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded

Let $$P(x)$$ and $$Q(x)$$ be arbitrary predicates. Which of the following statement is always TRUE?

Let $$P, Q$$ and $$R$$ be three atomic prepositional assertions. Let $$X$$ denotes $$\left( {P \vee Q} \right) \to R$$ a

What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some studen

What is the swap space in the disk used for?

Suppose n processes, P1,......., Pn share m identical resource units, which can be reserved and released one at a time.

Consider a disk drive with the following specifications: $$16$$ surfaces, $$512$$ tracks/surface, $$512$$ sectors/track,

Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${\rm I}/O$$ instructions in the for $$CPU

Consider the following code fragment: if (fork() == 0) { a = a + 5; printf("%d, %d \n", a, &a); } else { a

What does the following C statement declare? int (*f)(int *);

Consider the following C program: double foo(double); /* Line 1 */ int main () { double da, db; //input da db = fo

Consider the following C program: void foo (int n, int sum) { int k = 0, j = 0; if(n==0) return; k=n%10; j = n /10

Which one of the following are essential features of an object-oriented programming language? i) Abstraction and encapsu

An Abstract Data Type (ADT) is

A common property of logic programming languages and functional languages is:

Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}

Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which

Consider the language : $${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$

Consider the language : $${L_1} = \left\{ {{a^n}{b^n}{c^m}\left| {n,m > 0} \right.} \right\}$$ and $${L_2} = \left\{

Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-determ

Consider the machine $$M:$$ The language recognized by $$M$$ is: