Let A and B be sets and let A^c and B^c denote the complements of the sets A and B. The set (A – B) ∪ (B - A) ∪ (A∩B) is equal to

Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x divides y. Number of edge as in the Hasse diagram of (X,≤) is

Suppose X and Y are sets and X Y and are their respective cardinalities. It is given that there are exactly 97 functions from X to Y. from this one can conclude that

Which of the following statements is false?

Two dice are thrown simultaneously. The probability that at least one of them will have 6 facing up is

The formula used to compute an approximation for the second derivative of a function f at a point X₀ is

Let Ax = b be a system of linear equations where A is an m × n matrix and b is a m × 1 column vector and X is a n × 1 column vector of unknowns. Which of the following is false?

Which two of the following four regular expressions are equivalent? (ε is the empty string).

(i) (00)*(ε+0)
(ii) (00)*
(iii) 0*
(iv) 0(00)*

Which of the following statements is false?

Let L ⊆ Σ* where Σ = {a, b}. Which of the following is true?

Which of the following is false?

Consider the following statements:

(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

An advantage of chained hash table (external hashing) over the open addressing scheme is

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?

Which of the following sequences denotes the post order traversal sequence of the tree of question 14?

Relative mode of addressing is most relevant to writing

The pass number for each of the following activities

1. Object code generation
2. Literals added to literal table
3. Listing printed
4. Address resolution of local symbols

That occur in a two pass assembler respectively are

The process state transition diagram in below figure is representative of

A critical section is a program segment

Which of the following is an example of spooled device?

A ROM is sued to store the table for multiplication of two 8-bit unsigned integers. The size of ROM required is

Number of machine cycles required for RET instruction in 8085 microprocessor is

Both’s algorithm for integer multiplication gives worst performance when the multiplier pattern is

For the daisy chain scheme of connecting I/O devices, which of the following statements is true?

Consider the following floating point number representation

The exponent is in 2's complement representation and mantissa is in the sign magnitude representation. The range of the magnitude of the normalized numbers in this representation is

Let R denotes the set of real numbers. Let f: R×R → R×R be a bijective function defined by f(x,y) = (x+y,x-y), The inverse function of f is given by

Let R be a non-empty relation on a collection of sets defined by A R B if and only if A ∩ B = ф. Then, (pick the true statement)

Which of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one way implication and ↔ as two way implication.

Which one of the following is false?

Newton-Raphson iteration formula for finding 3√c, where c > 0 is,

The matrices and commute under multiplication

The probability that top and bottom cards of a randomly shuffled deck are both aces in

If L₁ and L₂ are context free languages and R a regular set, one of the languages below is not necessarily a context free language. Which one?

Define for a context free language L ⊆ {0,1}*, init(L) = {u ∣ uv ∈ L for some v in {0,1}∗} (in other words, init(L) is the set of prefixes of L)
Let L = {w ∣ w is nonempty and has an equal number of 0’s and 1’s}
Then init(L) is

The grammar whose productions are

  → if id then 
  → if id then   else 
  → id := id 

is ambiguous because

The minimum number of interchanges needed to convert the array

 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70  

into a heap with the maximum element at the root is

The recurrence relation

 T(1) = 2
 T(n) = 3T(n/4)+n 

has the solution, T(n) equals to

The average number of key comparisons done on a successful sequential search in list of length n is

A binary search tree is generated by inserting in order the following integers:

 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24  

The number of nodes in the left subtree and right subtree of the root respectively is

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,

(i) 1,2,3,...,n
(ii) n,n-1,n-2,...,2,1 

Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

Which of the following macros can put a micro assembler into an infinite loop?

(i)  .MACRO M1 X
     .IF EQ, X      ;if X=0 then
      M1 X + 1
     .ENDC
     .IF NE X       ;IF X≠0 then
     .WORD X        ;address (X) is stored here
     .ENDC
     .ENDM
(ii) .MACRO M2 X
     .IF EQ X
      M2 X
     .ENDC
     .IF NE, X
     .WORD X+1
     .ENDC
     .ENDM 

The correct matching for the following pairs is

         A. Activation record	   1. Linking loader
         B. Location counter	   2. Garbage collection
         C. Reference counts	   3. Subroutine call
         D. Address relocation	   4. Assembler 

A 1000 Kbyte memory is managed using variable partitions but to compaction. It currently has two partitions of sizes 200 Kbytes and 260 Kbytes respectively. The smallest allocation request in Kbytes that could be denied is for

A solution to the Dining Philosophers Problem which avoids deadlock is

Four jobs to be executed on a single processor system arrive at time 0⁺ in the order A, B, C, D. their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is

Consider the circuit given below which has a four bit binary number b₃b₂b₁b₀ as input and a five bit binary number d₄d₃d₂d₁d₀ as output. The circuit implements:

Consider the circuit in below figure. f implements

Consider the given figure of state table for a sequential machine. The number of states in the minimized machine will be

What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given below.

A micro program control unit is required to generate a total of 25 control signals. Assume that during any microinstruction, at most two control signals are active. Minimum number of bits required in the control word to generate the required control signals will be

Let f be a function defined by

Find the values for the constants a, b, c and d so that f is continuous and differentiable every where on the real line.

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.

A logic network has two data inputs A and B, and two control inputs C₀ and C₁. It implements the function F according to the following table.

Implement the circuit using one 4 to 1 Multiplexer, one 2-input Exclusive OR gate, one 2-input AND gate, one 2-input OR gate and one Inverter.

An 8052 based system has an output port with address 00H. Consider the following assembly language program.

     ORG    0100H
     MVI    A, 00H
     LXI    H, 0105H
     OUT    00H
     INR    A
     PCHL
     HLT   

(a) What does the program do with respect to the output port 00H?
(b) Show the wave forms at the three least significant bits of the port 00H.

A demand paged virtual memory system uses 16 bit virtual address, page size of 256 bytes, and has 1 Kbyte of main memory. LRU page replacement is implemented using a list whose current status (page number in decimal) is

For each hexadecimal address in the address sequence given below

 00FF, 010D, 10FF, 11B0

indicate
(i) the new status of the list
(ii) page faults, if any, and
(iii) page replacements, if any

Let F be the collection of all functions f: {1,2,3} → {1,2,3}. If f and g ∈ F, define an equivalence relation ~ by f ~ g if and only if f(3) = g(3).
a) Find the number of equivalence classes defined by ~.
b) Find the number of elements in each equivalence class.

The Fibonacci sequence {f₁,f₂,f₃,...,f_n} is defined by the following recurrence:

   fn+2 = fn+1 + fn, n ≥ 1; f2=1 : f1=1 

Prove by induction that every third element of the sequence is even.

Let and be two matrices such that AB = I. Let and CD = 1. Express the elements of D in terms of the elements of B.

Let G be a context-free grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.

   S → ABAC
   A → aA ∣ ε
   B → bB ∣ ε
   C → d  

(ε denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)

Given below are the transition diagrams for two finite state machine M₁ and M₂ recognizing languages L₁ and L₂ respectively.
(a) Display the transition diagram for a machine that recognizes L₁.L₂, obtained from transition diagrams for M₁ and M₂ by adding only ε transitions and no new states.
(b) Modify the transition diagram obtained in part(a) obtain a transition diagram for a machine that recognizes (L₁.L₂)∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).

Let Q = ({q₁,q₂}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.

(1) δ(q1,a,Z) = {(q1,Za)}
(2) δ(q1,b,Z) = {(q1,Zb)}
(3) δ(q1,a,a) = {(.....,.....)}
(4) δ(q1,b,b) = {(.....,.....)}
(5) δ(q2,a,a) = {(q2,ϵ)}
(6) δ(q2,b,b) = {(q2,ϵ)}
(7) δ(q2,ϵ,Z) = {(q2,ϵ)} 

A two dimensional array A[1...n][1...n] of integers is partially sorted if

    ∀i, j ∈ [1...n−1],   A[i][j] < A[i][j+1] and 
                           A[i][j] < A[i+1][j] 

Fill in the blanks:
(a) The smallest item in the array is at A[i][j] where i=............and j=..............
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x (which is guaranteed to be smaller than any item in the last row or column) still keeping A partially sorted.

procedure  insert (x: integer);
var        i,j: integer;
begin
(1) i:=1; j:=1, A[i][j]:=x;
(2) while (x > ...... or x > ......) do
(3) if A[i+1][j] < A[i][j] ......... then begin
(4) A[i][j]:=A[i+1][j]; i:=i+1;
(5) end
(6) else begin
(7) ............
(8) end
(9) A[i][j]:= .............
    end  

Insert the characters of the string K R P C S N Y T J M into a hash table of size 10.
Use the hash function

 h(x) = (ord(x) – ord("a") + 1) mod10 

and linear probing to resolve collisions.
(a) Which insertions cause collisions?
(b) Display the final hash table.

A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v

Let G be the directed, weighted graph shown in below figure.

We are interested in the shortest paths from A.
(a) Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node A.
(b) Write down sequence of vertices in the shortest path from A to E.
(c) What is the cost of the shortest path from A to E?

Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

      var          i,j,k: integer; x: integer;
                   a:= array; [1...N] of integer;
      begin	   i:= 1; j:= N;
      repeat	   k:(i+j) div 2;
                   if a[k] < x then i:= k 
                   else j:= k 
      until (a[k] = x) or (i >= j);
      if (a[k] = x) then
      writeln ('x is in the array')
      else
      writeln ('x is not in the array')
      end; 

Consider the following program in pseudo-pascal syntax. What is printed by the program if parameter a in procedure test 1 is passed as
(i) call-by-reference parameter
(ii) call-by-value-result parameter

     program Example (input, output)
     var b: integer;
     procedure test2:
     begin b:=10; end
    procedure test1 (a:integer):
     begin 	a:=5;
                writeln ('point 1: ', a, b);
                test2;
                writeln ('point 2: ', a, b);
     end
     begin(*Example*)
     b:=3; test1(b);
     writeln('point3:', b);
     end 

Consider the syntax-directed translation schema (SDTS) shown below:

    E → E + E  {print “+”}
    E → E ∗ E  {print “.”}
    E → id     {print id.name}
    E → (E) 

An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.

(a+b)∗(c+d), using the SDTS given above. 

The concurrent programming constructs fork and join are as below:
fork which creates a new process executing from the specified label
join which decrements the specified synchronization variable (by 1) and terminates the process if the new value is not 0.
Show the precedence graph for S1, S2, S3, S4, and S5 of the concurrent program below.

   N = 2
   M = 2
   fork L3
   fork L4
   S1
L1:join N
   S3
L2:join M
   S5
L3:S2
   goto L1
L4:S4
   goto L2
next: 

A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the table below, where P0, P1, P2 are processes, and R0, R1, R2 are resources types.

(a) Show that the system can be in this state.
(b) What will the system do on a request by process P0 for one unit of resource type R1?

A file system with a one-level directory structure is implemented on a disk with disk block size of 4K bytes. The disk is used as follows:

 Disk-block 0: File Allocation Table, consisting of one 8-bit entry per date block, 
               representing the data block address of the next date block in the file
 Disk block 1: Directory, with one 32 bit entry per file:
 Disk block 2: Data block 1;
 Disk block 3: Data block 2; etc. 

(a) What is the maximum possible number of files?
(b) What is the maximum possible file size in blocks?

Consider the synchronous sequential circuit in the below figure.

(a) Draw a state diagram, which is implemented by the circuit. Use the following names for the states corresponding to the values of flip-flops as given below.

(b) Given that the initial state of the circuit is S₄, identify the set of states, which are not reachable.

A hard disk is connected to a 50 MHz processor through a DMA controller. Assume that the initial set-up of a DMA transfer takes 1000 clock cycles for the processor, and assume that the handling of the interrupt at DMA completion requires 500 clock cycles for the processor. The hard disk has a transfer rate of 2000 Kbytes/sec and average block transferred is 4 K bytes. What fraction of the processor time is consumed by the disk, if the disk is actively transferring 100% of the time?

A computer system has a three level memory hierarchy, with access time and hit ratios as shown below:

(a) What should be the minimum sizes of level 1 and 2 memories to achieve an average access time of less than 100 nsec?
(b) What is the average access time achieved using the chosen sizes of level 1 and level 2 memories?

A library relational database system uses the following schema

USERS (User#, UserName, HomeTown)
BOOKS (Book#, BookTitle, AuthorName)
ISSUED (Book#, User#, Date) 

Explain in one English sentence, what each of the following relational algebra queries is designed to determine

(a) σ User #=6 (11 User #, Book Title ((USERS ISSUED) BOOKS))
(b) σ Author Name (BOOKS (σ Home Town) = Delhi (USERS ISSUED)))