Give the correct matching for the following pairs:

Group - 1

(A) $${\rm O}(\log n)$$
(B) $${\rm O}(n)$$
(C) $${\rm O}(n\log n)$$
(D) $${\rm O}({n^2})$$

Group - 2

(P) Selection
(Q) Insertion sort
(R) Binary search
(S) Merge sort

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

Type checking is normally done during

Which of the following statements is true?

Which of the following device should get higher priority on assigning interrupts?

Which of the following is true?

Let A be a two dimensional array declared as follows:
A : array [ 1... 10] [1... 15] of integer;
Assuming that each integer takes one memory locations the array is stored in row-major order and the first element of the array is stored at location 100, what is the address of the element A[i] [j]?

Compute the post fix equivalent of the following expression. 3 * log(x+1) - a/2

What value would the following function return for the input x = 95?

 function fun (x:integer):integer; 
   Begin 
      If x > 100 then fun : x – 10 
      Else fun : fun(fun (x + 11)) 
   End; 

Which of the following statements is false?

A complete n-ary tree is one in which every node has O or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

Which normal form is considered adequate for normal relational database design?

Consider the following database relations containing the attributes
Book–id
Subject–Category–of–book
Name–of–Author
Nationality–of–Author
With book–id as the primary key.
(a) What is the highest normal form satisfied by this relation?

(b) Suppose the attributes Book–title and Author–address are added to the relation, and the primary key is changed to {Name–of–Author, Book–title}, what will be the highest normal form satisfied by the relation?

Consider the following database relations containing the attributes
Book–id
Subject–Category–of–book
Name–of–Author
Nationality–of–Author
With book–id as the primary key.
(a) What is the highest normal form satisfied by this relation?

(b) Suppose the attributes Book–title and Author–address are added to the relation, and the primary key is changed to {Name–of–Author, Book–title}, what will be the highest normal form satisfied by the relation?

Suppose we have a database consisting of the following three relations.

FREQUENTS (student, parlor) giving the parlors each student visits.

SERVES (parlor, ice-cream) indicating what kind of ice-creams each parlor serves.

LIKES (student, ice-cream) indicating what ice-creams each student likes.

(Assume that each student likes at least one ice-cream and frequents at least one parlor)

Express the following in SQL:
Print the students that frequent at least one parlor that serves some ice-cream that they like.

Which of the following query transformations (i.e. replacing the l.h.s. expression by the r.h.s. expression) is incorrect? R₁ and R₂ are relations, C₁, C₂ are selection conditions and A₁, A₂ are attributes of R₁?

There are five records in a database.

Name	Age	Occupation	Category
Rama	27	CON	A
Abdul	22	ENG	A
Jennifer	28	DOC	B
Maya	32	SER	D
Dev	24	MUS	C

There is an index file associated with this and it contains the values 1, 3, 2, 5 and 4. Which one of the fields is the index built from?

Consider the following determinant $$$\Delta = \left| {\matrix{ 1 & a & {bc} \cr 1 & a & {ca} \cr 1 & a & {ab} \cr } } \right|$$$

Which of the following is a factor of $$\Delta $$ ?

A die is rolled three times. The probability that exactly one odd number turns up among the three outcomes is

The binary relation R = {(1, 1)}, (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4) } on the set A = { 1, 2, 3, 4} is

Let (A, *) be a semigroup. Furthermore, for every a and b in A, if $$a\, \ne \,b$$, then $$a\,*\,b \ne \,\,b\,*\,a$$.

(a) Show that for every a in A
a * a = a
(b) Show that for every a, b in A
a * b * a = a
(c) Show that for every a, b, c in A
a * b * c = a * c

Suppose A = {a, b, c, d} and $${\Pi _1}$$ is the following partition of A

$${\Pi _1}\, = \,\{ \{ a,\,\,b,\,\,c\,\} \,,\,\{ d\} \,\} $$
(a) List the ordered pairs of the equivalence relations induced by $${\Pi _1}$$
(b) Draw the graph of the above equivalence relation.

Let $${R_1}$$ and $${R_2}$$ be two equivalence relations on a set. Consider the following assertions:

(i)$$\,\,\,\,{R_1} \cup {R_2}$$ is an euivalence relation
(ii)$$\,\,\,\,{R_1} \cap {R_2}$$ is an equivalence relation

Which of the following is correct?

Suppose $$A$$ is a finite set with $$n$$ elements. The number of elements in the Largest equivalence relation of $$A$$ is

The number of functions from an $$m$$ element set to an $$n$$ element set is

Consider the following set a equations
x + 2y = 5
4x + 8y = 12
3x + 6y + 3z = 15 This set

In a room containing 28 people, there are 18 people who speak English, 15 people who speak Hindi and 22 people who speak Kannada, 9 persons speak both English and Hindi, 11 persons speak both Hindi and Kannada where as 13 persons speak both Kannada and English. How many people speak all three languages?

Solve the following recurrence relation

$$\,\,\,\,\,\,\,{x_n} = 2{x_{n - 1}} - 1\,\,n > 1$$
$$\,\,\,\,\,\,\,{x_1} = 2$$

The rank of the matrix given below is: $$$\left[ {\matrix{ 1 & 4 & 8 & 7 \cr 0 & 0 & 3 & 0 \cr 4 & 2 & 3 & 1 \cr 3 & {12} & {24} & {2} \cr } } \right]$$$

Consider the function $$y = \left| x \right|$$ in the interval $$\left[ { - 1,1} \right]$$. In this interval, the function is

(a) Find the points of local maxima and minima, if any, of the following function defined $$0 \le x \le 6.\,\,\,{x^3} - 6{x^2} + 9x + 15$$

(b) Integrate $$\,\,\,\int\limits_{ - \pi }^\pi {x\,\cos \,x\,dx} $$

What is the converse of the following assertion?
I stay only if you go

Find the points of local maxima and minima if any of the following function defined in $$0 \le x \le 6,$$ $$\,\,\,\,f\left( x \right) = {x^3} - 6{x^2} + 9x + 15.$$

If an instruction takes $${\rm I}$$ microseconds and a page fault takes an additional $$j$$ microseconds, the effective instruction time if on the average a page fault occurs every $$k$$ instruction is:

A computer has six tape drives, with n processes competing for them. Each process may need two drives. What is the maximum value of n for the system to be deadlock free?

In a resident $$–OS$$ computer, which of the following systems must reside in the main memory under all situations?

The overlay tree for a program is as shown below:

What will be the size of the partition (in physical memory) required to load (and run) this program?

A counting semaphore was initialized to 10. Then 6 P (wait) operations and 4 V (signal) operations were completed on this semaphore. The resulting value of the semaphore

In a computer system where the ‘best-fit’ algorithm is used for allocating ‘jobs’ to ‘memory partitions’, the following situation was encountered:

When will the $$20$$ $$K$$ job complete?

Which of the following devices should get higher priority in assigning interrupts?

Which of the following is true?

Formatting of floppy disk refers to

Which of the following is an example of spooled device?

Consider $$n$$ processes sharing the $$CPU$$ in a round-robin fashion. Assuming that each process switch takes $$s$$ seconds, what must be the quantum size $$q$$ such that the overhead resulting from process switching is minimized but, at the same time each process is guaranteed to get its turn at the $$CPU$$ at least every $$t$$ seconds?

Four jobs are waiting to be run. Their expected run times are $$6, 3, 5$$ and $$x$$. $${\rm I}$$n what order should they be run to minimize the average response time?

When the result of a computation depends on the speed of the processes involved there is said to be

What is the result of the following program?

program side-effect (input, output);
var x, result: integer:
fucntion f (var x:integer):integer;
begin
    x:x+1;f:=x;
end
begin
    x:=5
    result:=f(x)*f(x)
    writeln(result)
end

What value would the following function return for the input x = 95?

Function fun (x:integer):integer;
Begin
     If x > 100 then fun : x – 10
     Else fun : fun(fun (x + 11))
End;

Faster access to non-local variables is achieved using an array of pointers to activation records called a

Regarding the power of recognition of languages, which of the following statement is false?

If the regular set $$A$$ is represented by $$A = {\left( {01 + 1} \right)^ * }$$ and the regular set $$'B'$$ is represented by $$B = \left( {{{\left( {01} \right)}^ * }{1^ * }} \right),$$ which of the following is true?

The string $$1101$$ does not belong to the set represented by

Which of the following sets can be recognized by a Deterministic Finite-state Automation?

How many substrings of different lengths (non-zero) can be formed from a character string of length $$n$$ ?

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state automaton accepting $$L$$ is

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state automation accepting $$L$$ is

Which of the following statements is false?