The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used?

The correct matching for the following pairs is

A. All pairs shortest path	1. Greedy
B. Quick Sort	2. Depth-First Search
C. Minimum weight spanning tree	3. Dynamic Programming
D. Connected Components	4. Divide and Conquer

Let T(n) be the function defined by $$T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$$
Which of the following statements is true?

In the following grammar:

$$\eqalign{ & X:: = X \oplus {Y \over Y} \cr & Y:: = Z*{Y \over Z} \cr & Z:: = id \cr} $$

Which of the following is true?

The correct matching for the following pairs is

An $$N$$-bit carry look ahead adder, where $$N$$ is a multiple of $$4,$$ employs $${\rm I}cs$$ $$74181$$ ($$4$$bit $$ALU$$) and $$74182$$ ($$4$$ bit carry look ahead generator). The minimum addition time using the best architecture for this adder is

Which of the following is essential for converting an infix expression to the postfix form efficiently?

A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

Let $$R (a, b, c)$$ and $$S(d, e, f)$$ be two relations in which $$d$$ is the foreign key of $$S$$ that refers to the primary key of $$R.$$ Consider the following four operations $$R$$ and $$S$$
(a) Insert into $$R$$ (b) Insert into $$S$$
(c) Delete from $$R$$ (d) Delete from $$S$

Which of the following statements is true about the referential integrity constraint above?

For a database relation $$R(a,b,c,d),$$ where the domains of $$a, b, c, d$$ include only atomic values, only the following functional dependencies and those that can be inferred from them hold:
$$a \to c\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,b \to d$$
This relation is

Consider the logic circuit shown in Figure below. The functions $${f_1},$$ $${f_2}$$ and $$f$$ (in canonical sum of products form in decimal notation) are:

$${f_1}\left( {w,\,x,\,y,\,z} \right) = \sum {8,9,10} $$
$${f_2}\left( {w,\,x,\,y,\,z} \right) = \sum {7,8,12,13,18,15} $$
$$f\left( {w,\,x,\,y,\,z} \right) = \sum {\left( {8,9} \right)} $$

The function $${f_3}$$ is

Let $$^ * $$ be defined as $${x^ * }y = \overline x + y,$$ Let $$z = {x^ * }y.$$ Value of $${z^ * }x$$ is

Let $$f\left( {x,y,z} \right) = \overline x + \overline y x + xz$$ be a switching function. Which one of the following is valid?

Given $$\sqrt {\left( {224} \right),} = {\left( {13} \right)_r},$$
The value of the radix' $$r$$ is:

The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. That is the probability that it will rain today and tomorrow?

The number of equivalence relations on the set $$\left\{ {1,2,3,4} \right\}$$ is

Let $$A = ({a_{ij}})$$ be and n-rowed square matrix and $${I_{12}}$$ be the matrix obtained by interchanging the first and second rows of the n-rowed Identity matrix. Then$${AI_{12}}$$ is such that its first

What is the maximum value of the function
$$f\left( x \right) = 2{x^2} - 2x + 6$$ in the interval $$\left[ {0,2} \right]$$?

The determination of the matrix $$$\left[ {\matrix{ 6 & { - 8} & 1 & 1 \cr 0 & 2 & 4 & 6 \cr 0 & 0 & 4 & 8 \cr 0 & 0 & 0 & { - 1} \cr } } \right]\,\,is$$$

Thrashing

Dirty bit for a page in a page table

Locality of reference implies that the page reference being made by a process

$$I/O$$ redirection

The correct matching for the following pairs is

(a) Disk scheduling $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$(1) Round robin
(b) Batch processing $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ (2) $$SCAN$$
(c) Time sharing $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ (3) $$LIFO$$
(d) Interrupt processing $$\,\,\,\,\,\,\,\,\,\,\,$$(4) $$FIFO$$

When an interrupt occurs, an Operating System

The correct matching for the following pairs is
$$\,\,\,\,\,$$ List - $${\rm I}$$
(a) $$DMA$$ $$\,\,$$ $${\rm I}/O$$
(b) Cache
(c) Interrupt $${\rm I}/O$$
(d) Condition Code Register

$$\,\,\,\,\,$$ List - $${\rm II}$$
(1) High speed $$RAM$$
(2) Disk
(3) Printer
(4) $$ALU$$

An operating system contains 3 user processes each requiring 2 units of resource R.The minimum number of units of R such that no deadlocks will ever arise is

Each process P_i,i=1.....9 is coded as follows

  Repeat
  P(mutex){
  critical section
  }
  V(mutex)
  Forever

The code for P₁₀ is identical except that it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?

Heap allocation is required for languages.

Given the following Pascal like program segment:

Procedure A;

     x,y:intger;

     Procedure B;

            x,z:real;

            S1

     end B;

     Procedure C;

            i:integer;

            S2;

     end C;

end A;

The variables accessible in S1 and S2 are

Which of the following languages over $$\left\{ {a,b,c} \right\}$$ is accepted by Deterministic push down automata?

$$\sum { = \left\{ {a,b} \right\},\,\,} $$ which one of the following sets is not countable.

Which one of the following regular expressions over $$\left\{ {0,\,\,1} \right\}$$ denotes the set of all strings not containing $$100$$ as substring?

Which one of the following is not decidable?