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

Consider the following set of equations

                x + 2y = 5
               4x + 8y = 12
          3x + 6y + 3z = 15 

This set

Which of the following statements applies to the bisection method used for finding roots of functions:

Consider the function y = |x| in the interval [-1,1]. In this interval, the function is

What is the converse of the following assertion?

  I stay only if you go. 

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

Let R₁ and R₂ be two equivalence relations on a set. Consider the following assertions:

(i) R₁ ∪ R₂ is an equivalence relation
(ii) R₁ ∩ R₂ is an equivalence relation

Which of the following is correct?

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

If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?

Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.

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

The string 1101 does not belong to the set represented by

What happens when a bit-string is XORed with itself n-times as shown:

  [B⊕(B⊕(B⊕(B........ n times)]  

A multiplexor with a 4 bit data select input is a

The threshold level for logic 1 in the TTL family is

In serial communication employing 8 data bits, a parity bit and 2 stop bits, the minimum band rate required to sustain a transfer rate of 300 characters per second is

The octal representation of an integer is (342)₈. If this were to be treated as an eight-bit integer is an 8085 based computer, its decimal equivalent is

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

Which of the following addressing modes permits relocation without any change whatsoever in the code?

Which of the following is true?

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

Give the correct matching for the following pairs:

            A. O(log n)     1. Selection sort
            B. O(n)         2. Insertion sort
            C. O(nlog n)    3. Binary search
            D. O(n2)        4. Merge sort   

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

Which of the following statements is false?

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

Which of the following statements is true?

Type checking is normally done during

A linker reads four modules whose lengths are 200, 800, 600 and 500 words, respectively. If they are loaded in that order, what are the relocation constants?

Which of the following is an example of a spooled device?

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

A counting semaphore was initialized to 10. Then 6P (wait) operations and 4V (signal) operations were completed on this semaphore. The resulting value of the semaphore 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?

Given two union compatible relations R₁(A,B) and R₂(C,D), what is the result of the operation R₁A = CAB = DR₂?

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

There are 5 records in a database.

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

The rank of the matrix given below is:

        1   4   8   7
        0   0   3   0
        4   2   3   1
        3   12  24  2  

Consider the following determinant 

Which of the following is a factor of Δ?

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

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 whereas 13 persons speak both Kannada and English. How many people speak all three languages?

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 0 state automaton accepting L is

Which of the following statements is false?

The function represented by the Karnaugh map given below is:

Which of the following operations is commutative but not associative?

Formatting for a floppy disk refers to

The address space of 8086 CPU is

A complete n-ary tree is one in which every node has 0 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

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;  

What is the result of the following program?

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

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 location, 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]?

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

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?

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?

If an instruction takes 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:

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₁?

Suppose the domain set of an attribute consists of signed four digit numbers. What is the percentage of reduction in storage space of this attribute if  it is stored as an integer rather than in character form?

(a) Two friends agree to meet at a park with the following conditions. Each will reach the park between 4:00 p.m. and 5:00 p.m. and will see if the other has already arrived. If not, they will wait for 10 minutes or the end of the hour whichever is earlier and leave. What is the probability that the two will not meet?

(b) Given a regular expression for the set of binary strings where every 0 is immediately followed by exactly k 1's and preceded by atleast k 1's (k is a fixed integer).

Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}* | w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}

(a) The implication gate shown below, has two inputs (x and y), the output is 1 except when x=1 and y=0. Realize f = x'y + xy' using only four implication gates.

(b) Show that the implication gate is functionally complete.

(a) Solve the following recurrence relation:

  xn = 2xn-1 - 1, n>1
  x1 = 2 

(b) Consider the grammar

  S →  Aa | b
  A → Ac | Sd | ε 

Construct an equivalent grammar with no left recursion and with minimum number of production rules.

(a) 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 parlor serves.
(Assuming 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.

(b) 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 20K job complete? Note - This question was subjective type.

(a) Find the points of local maxima and minima, if any, of the following function defined in 0 ≤ x ≤ 6.

  x3 - 6x + 9x - 15 

(b) Integrate

Derive the expression for the number of expressions required to solve a system of linear equations in n unknowns using the Gaussian Elimination Method. Assume that one operation refers to a multiplication followed by an addition.

(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n-3)/2.

(b) Let R be a binary relation on A = {a, b, c, d, e, f, g, h} represented by following two component digraph. Find the smallest integers m and n such that mm = Rⁿ.

Suppose A = {a,b,c,d} and Π₁ is the following partition of A
Π₁ = {{a,b,c}{d}}

(a) List the ordered pairs of the equivalence relations induced by Π₁.

(b) Draw the graph of the above equivalence relation.

(c) Let Π₂ = {{a},{b},{C},{d}}
Π₃ = {{a,b,c,d}}
and Π₄ = {{a,b},{c,d}}

Draw a Poset diagram of the poset,
({Π₁,Π₂,Π₃,Π₄}, refines⟩

Let (A, *) be a semi group. Furthermore, for every a and b in A, if a ≠ b, then a*b ≠ 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 

Let M = ({q₀, q₁}, {0, 1}, {z₀, x}, δ, q₀, z₀, ∅) be a pushdown automaton where δ is given by

δ(q₀, 1, z₀) = {(q₀, xz₀)}
δ(q₀, ε, z₀) = {(q₀, ε)}
δ(q₀, 1, X) = {(q₀, XX)}
δ(q₁, 1, X) = {(q₁, ε)}
δ(q₀, 0, X) = {(q₁, X)}
δ(q₀, 0, z₀) = {(q₀, z₀)}

(a) What is the language accepted by this PDA by empty stack?

(b) Describe informally the working of the PDA.

(a) Let G₁ = (N, T, P, S₁) be a CFG where,
N = {S₁, A, B}, T = {a,b} and
P is given by

         S1 → aS1b             S1 → aBb
         S1 → aAb              B → Bb
         A → aA                B → b
         A → a 

What is L(G1)?

(b) Use the grammar in part(a) to give a CFG
for L₂ = {aⁱ b^j a^k b^l | i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.

(c) Is L₂ inherently ambiguous?

(a) Draw the schematic of an 8085 based system that can be used to measure the width of a pulse. Assume that the pulse is given as a TTL compatible signal by the source which generates it.

(b) Write the 8085 Assembly Language program to measure the width of the pulse. State all your assumption clearly.

Design a synchronous counter to go through the following states:

  1, 4, 2, 3, 1, 4, 2, 3, 1, 4,........... 

Calculate the total time required to read 35 sectors on a 2-sided floppy disk. Assume that each track has 8 sectors and the track-to-track step time is 8 milliseconds. The first sector to be read is sector 3 on track 10. Assume that the diskette is soft stored and the controller has a 1-sector buffer. The diskette spins at 300 RPM and initially, the head is on track 10.

For a set-associative Cache Organization, the parameters are as follows:

t_c -- Cache access tine
t_m -- Main memory access time
l -- number of sets
b -- block size
k*b -- set size

Calculate the hit ratio for a loop executed 100 times where the size of the loop is n * b and n= k * m is a non-zero integer and 1 < m ≤ l.
Given the value of the hit ratio for l = 1.

Let p be a pointer as shown in the figure in a single linked list.

What do the following assignment statements achieve?

q: = p → next
p → next:= q → next
q → next:=(q → next) → next
(p → next) → next:= q

(b) Compute the postfix equivalent of the following Infix expression

  3 * log(x+1) - a/2  

Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:

 Inorder       a f b c d g e
 Postorder     a f c g e d b 

(a) Derive a recurrence relation of the size of the smallest AVL tree with height h.

(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.

(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions

Program → begin d semi X end
X → d semi X | sY
Y → semi s Y | ε 

Let the attribute 'val' give the value of a binary number generated by S in the following grammar:

S → L.L | L 
L→ LB | B 
B → 0 | 1 

For example, an input 101.101 gives S.val = 5.625

Construct a syntax directed translation scheme using only synthesized attributes, to determine S.val.

(a) Four jobs are waiting to be run. Their expected run times are 6, 3, 5 and x. In what order should they be run to minimize the average response time?

(b) Write a concurrent program using par begin - par end to represent the precedence graph shown below.

(a) Free disk space can be kept track of using a free list or a bit map. Disk addresses require d bits. For a disk with 13 blocks, F of which is free, state the condition under which the free list uses less space than the bit map.

(b) Consider a disk with C cylinders, t tracks per cylinder, s sectors per track and a sector length sl. A logical file dl with fixed record length rl is stored continuously on this disk starting at location (c_L,t_L,s_L), where c_L, t_L and S_L are the cylinder, track and sector numbers, respectively. Derive the formula to calculate the disk address (i.e. cylinder, track and sector) of a logical record n assuming that rl=sl.

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 relational database schemes:

  COURSES(Cno, name)
  PRE-REQ(Cno, pre_Cno)
  COMPLETED(student_no, Cno) 

COURSES give the number and the name of all the available courses.
PRE-REQ gives the information about which course are pre-requisites for a given course.
COMPLETED indicates what courses have been completed by students.

Express the following using relational algebra:
List all the courses for which a student with student_no 2310 has completed all the pre-requisites.