Consider the following C-program fragment in which i, j and n are integer variables. for (i = n, j = 0; i > 0; i /= 2

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorit

Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM3 be th

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible

Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a min

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure

Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick

Consider the following recurrence: $$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) +

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be repres

Given two arrays of numbers a1,......,an and b1,......, bn where each number is 0 or 1, the fastest algorithm to find th

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be repres

Which one of the following in place sorting algorithms needs the minimum number of swaps?

In a binary max heap containing n numbers, the smallest element can be found in time

Which one of the following grammars generates the following language? $$L = \left( {{a^i}{b^j}|i \ne j} \right)$$

Consider the following grammar. $$\eqalign{ & S \to S*E \cr & S \to E \cr & E \to F + E \cr &a

In the correct grammar of the previous question, what is the length of the derivation (number of steps starring from S)

Consider the following C code segment. for (i = 0; i < n; i++) { for (j=0; j < n; j++) {

Consider the following translation scheme. $$\eqalign{ & S \to ER \cr & R \to *E\left\{ {pr{\mathop{\rm in

Consider the following grammar: $$\eqalign{ & S \to FR \cr & R \to *S\,|\,\varepsilon \cr & F \to

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packet

Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP a

For which one of the following reasons does Internet Protocol (IP) use the time-to-live (TTL) field in the IP datagram h

Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and go-bac

Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay b

Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packet

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content

Consider the following program segment. Here R1, R2 and R3 are the general purpose registers. Assume that the content

A $$CPU$$ has $$24$$-bit instructions. A program starts at address $$300$$ (in decimal). Which one of the following is a

A CPU has five stages pipeline and runs at $$1$$ $$GHz$$ frequency. Instruction fetch happens in the first stage of the

Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set associate with $$32$$-byte block size. The

Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set associate with $$32$$-byte block size. The

A $$CPU$$ has a cache with block size $$64$$ bytes. The main memory has $$k$$ banks, each bank being $$c$$ bytes wide. C

Given two three bit number $${a_2}{a_1}{a_0}$$ and $${b_2}{b_1}{b_0}$$ and $$c,$$ the carry in the function that repres

Let T be a depth first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent th

Let T be a depth-first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array

Which of the following sequences of array elements forms a heap?

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of th

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is store

The following function computes the value of mCn correctly for all legal values m and n (m≥1,n≥0 and m>n) int func(

An implementation of a queue Q, using two stacks S1 and S2, is given below: void insert(Q, X){ push(S1, X); } void de

Which of the following relational query languages have the same expressive power? I) Relational algebra II) Tuple relati

Consider the relations r1(P, Q, R) and r2(R, S, T) with primary keys P and R respectively. The relation r1 contains 2000

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are Di

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are Di

Consider the relation "enrolled (student, course)" in which (student, course) is the primary key, and the relation "paid

Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would

The following functional dependencies are given : $$\eqalign{ & AB \to CD,\,AF \to D,\,\,DE \to F, \cr & C

Consider the relation enrolled (student, course) in which (student, course ) is the primary key, and the relation Paid (

Consider the circuit in the diagram. The $$ \oplus $$ operator represents $$EX$$-$$OR.$$ The $$D$$ flip-flops are initia

You are given a free running clock with a duty cycle of $$50$$% and a digital waveform $$f$$ which changes only at the n

Consider the circuit above. Which one of the following options correctly represents $$f(x,y,z)?$$

Consider a Boolean function $$f(w, x, y, z).$$ Suppose that exactly one of its inputs is allowed to change at a time. If

Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \subseteq \,N\,$$ and $$B\, \subseteq \,N\,

What are the eigen values of the matrix $$P$$ given below? $$$P = \left( {\matrix{ a & 1 & 0 \cr 1 &

$$F$$ is an $$n$$ $$x$$ $$n$$ real matrix. $$b$$ is an $$n$$ $$x$$ $$1$$ real vector. Suppose there are two $$n$$ $$x$$

Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have a

The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices

The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices

What is the cardinality of the set of integers $$X$$ defined below? $$X = $$ {$$n\left| {1 \le n \le 123,\,\,\,\,\,n} \r

For each elements in a set of size $$2n$$, an unbiased coin in tossed. The $$2n$$ coin tosses are independent. An elemen

Consider the polynomial $$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3}{x^3},$$ where $${a_i} \ne 0,\forall i

Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ suc

If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices an

Consider the set S = {a, b, c, d}. Consider the following 4 partitions $$\,{\pi _1},\,{\pi _2},\,{\pi _3},\,{\pi _4}$$ o

Let S = {1, 2, 3,....., m} , m > 3. Let $${X_1},\,....,\,{X_n}$$ be subsets of S each of size 3. Define a function f

For the set $$N$$ of natural numbers and a binary operation $$f:N \times N \to N$$, an element $$z \in N$$ is called an

The set $$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$ under multiplication modulo 10 is not a group. Give

Let $$X,. Y, Z$$ be sets of sizes $$x, y$$ and $$z$$ respectively. Let $$W = X x Y$$ and $$E$$ be the set of all

A relation $$R$$ is defined on ordered pairs of integers as follows: $$\left( {x,y} \right)R\left( {u,v} \right)\,if\,x

Let E, F and G be finite sets. Let $$X = \,\left( {E\, \cap \,F\,} \right)\, - \,\left( {F\, \cap \,G\,} \right)$$ and

Let $$P, Q$$, and $$R$$ be sets. Let $$\Delta $$ denote the symmetric difference operator defined as $$P\Delta Q = \left

Consider the following first order logic formula in which $$R$$ is a binary relation symbol. $$\forall x\forall y\left(

When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N be the random variable denoting th

A logical binary relation $$ \odot $$, is defined as follows: Let ~ be the unary negation (NOT) operator, with higher

In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data

Consider the following propositional statements: $${\rm P}1:\,\,\left( {\left( {A \wedge B} \right) \to C} \right) \equ

Which one of the first order predicate calculus statements given below correctly expresses the following English stateme

A Computer system supports $$32$$-bit virtual addresses as well as $$32$$-bit physical addresses. Since the virtual addr

Consider the following snapshot of a system running n processes. Process i is holding xi instances of a resource R, for

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arriv

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arriv

The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x

Consider three processes, all arriving at time zero, with total execution time of $$10,20,$$ and $$30$$ units, respectiv

Consider three processes (process id $$0,1,2,$$ respectively) with compute time bursts $$2, 4,$$ and $$8$$ time units. A

Consider three $$CPU$$-intensive process, which require $$10,20$$ and $$30$$ time units and arrive at times $$0,2$$ and

Consider this C code to swap two integers and these five statements: void swap(int *px, int *py) { *px = *px - *py

If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$

Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enum

For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$ Let $$L = \lef

Consider the following statements about the context-free grammar $$G = \left\{ {S \to SS,\,S \to ab,\,S \to ba,\,S \to \

Let $${L_1} = \left\{ {{0^{n + m}}{1^n}{0^m}\left| {n,m \ge 0} \right.} \right\},$$ $$\,\,\,{L_2} = \left\{ {{0^{n + m}

Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ ac