For the digital in figure, the expression for the output f is ________

In interleaved memory organization, consecutive words are stored in consecutive memory modules in ________ interleaving, whereas consecutive words are stored within the module in ________ interleaving.

Consider the number given by the decimal expression:

  163 * 9 + 162 * 7 + 16 * 5 + 3

The number of 1’s in the unsigned binary representation of the number is ________.

Using the 8087 arithmetic coprocessor with the 8087 CPU requires that the 8087 CPU is operated ________.

When two 4-bit binary number A = a₃a₂a₁a₀ and B = b₃b₂b₁b₀ are multiplied, the digit c₁ of the product C is given by _________

Consider the following PASCAL program segment:

 if i mode 2 = 0 then
           while i > = 0 do
             begin
              i:=i div 2;
              if i mod 2 < > 0 do then i:=i – 1
                   else i:=i – 2
 end

An appropriate loop-invariant for the while-loop is ______

The minimum number of comparisons required to sort 5 elements is _____

The weighted external path length of the binary tree in figure is _____

If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______

Consider the following recursive definition of fib:

 fib (n) : = if n = 0 then 1
             else if n = 1 than 1
             else fib (n – 1) + fib (n – 2)

The number of times fib is called (including the first call) for an evaluation of fib (7) is ___________

The arithmetic expression : (a + b) * c - d / e * * f is to be evaluated on a two-address machine, where each operands, the number of registers required to evaluate this expression is ______. The number of memory access of operand is __________.

A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is ________

The number of integer-triples (i.j.k) with 1 ≤ i.j.k ≤ 300 such that i + j + k is divisible by 3 is ________

If the longest chain in a partial order is of length n then the partial order can be written as a ______ of n antichains.

The maximum number of possible edges in an undirected graph with a vertices and k components is ________.

Match the pairs in the following questions by writing the corresponding letters only.

(A) IEEE 488    (P) specifies the interface for connecting a single device
(B) IEEE 796    (Q) specifies the bus standard for connecting a computer to 
                    other devices including CPU’s
(C) IEEE 696    (R) specifies the standard for an instrumentation bus
(D) RS232-C     (S) specifies the bus standard for the “backplane” bus called  
                    multibus. 

Match the pairs in the following questions by writing the corresponding letters only. For the 8086 microprocessor:

(A) RQ/GT   (P) Used by processor for holding the bus for consecutive instruction
                cycles.
(B) LOCK    (Q) Used for extending the memory or I/O cycle times
(C) HOLD    (R) Used for getting hold of processor bus in minimum bus mode
(D) READY   (S) Used for requesting processor bus in minimum bus mode.

Match the pairs in the following questions by writing the corresponding letters only.

(A) Buddy system     (P) Run-time type specification
(B) Interpretation   (Q) Segmentation
(C) Pointer type     (R) Memory allocation
(D) Virtual memory   (S) Garbage collection

Match the pairs in the following questions by writing the corresponding letters only.

(A) The number distinct binary trees with n nodes       (P) n!/2        
(B) The number of binary strings of length of 2n        (Q) (3n/n)
    with an equal number of 0’s and 1’s                                     
(C) The number of even permutations of n objects        (R) (2n/n) 
(D) The number of binary strings of length 6m which     (S) 1/n+1(2n/n) 
    are palindromes with 2n 0’s.

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: The advantages of CMOS technology over a MOS is:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Advantage of synchronous sequential circuits over asynchronous ones is:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: The total size of address space is a virtual memory systems is limited by

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: The TRAP interrupt mechanism of the 8085 microprocessor:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: The ALE line of an 8085 microprocessor is used to:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with vertices and m edges has the time complexity of:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: The following sequence of operations is performed on a stack:

 PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POP

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Consider the following Pascal function:

 function X (M:integer) : integer;
 var i:integer;
 begin
   i = 0;
   while i*i < M do i; =i+1
   X;=i
 end

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: A “link editor” is a program that:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Indicate all the true statements from the following:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Indicate all the false statements from the statements given below:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If F₁, F₂ and F₃ are propositional formulae such that F₁ ∧ F₂ → F₃ and F₁ ∧ F₁ → ~F₂ are both tautologies, then which of the following is true:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Let r = 1(1+0)*, s = 11*0 and t = 1*0 be three regular expressions. Which one of the following is true?

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Which one of the following is the strongest correct statement about a finite language over some finite alphabet ∑?

Give short answers to the following questions:
(i) Convert the following Pascal statement to a single assignment statement:

       if x > 5 they y:=true
             else y:=false; 

(a) Analyse the circuit in figure and complete the following table:

(b) Find the minimum sum of products form of the logic function.

 f(A,B,C,D) = ∑m(0,2,8,10,15) + ∑d(3,11,12,14)

(c) Find the maximum clock frequency at which the counter in figure, can be operated. Assume that the propagation delay through each flip-flop and AND gate is 10 ns. Also assume that the setup time for the JK inputs of the flipflops is negligible.

(a) Using D flip-flop and gates, design a parallel-in/serial-out shift register that shifts data from left to right with the following input lines:

(i) Clock CLK
(ii) Three parallel data inputs A, B, C
(iii) Serial input S
(iv) Control input .

(b) Design a 1024 bit serial-in/serial-out unidirectional shift register using a 1K × 1 bit RAM with data input D_in, data output D_out and control input . You may assume that availability of standard SSI and MSI components such as gates, registers and counters.

It is required to design a hardwired controller to handle the fetch cycle of a single address of an indexed instruction should be derived in the fetch cycle itself. Assume that the lower order 8 bits of an instruction constitute the operand field.
(a) Give the register transfer sequence for realizing the above instruction fetch cycle.
(b) Draw the logic schematic of the hardwired controller including the date path.

(a) Consider an 8085 based system operating with the following specification:

Crystal frequency : 6 MHz
ROM map : 0000 through 07FF
RAM map : 1000 through 17 FF:
ROM requires one wait state.
RAM requires no wait state. 

Determine the instruction cycle time for each of the following instructions:

(i) ORI A, 22 
(ii) DCR M 

Assume the following initial conditions of the CPU registers (in hex) for each of the instructions:

 A = 55, B = AA, C = F7, D = 10, H = 10, L = FF, PC = 0200, SP = 17FO. 

(b) Developing an output port interface (draw a block schematic) for an 8085 based system with a demultiplexed address bus which incorporates a handshake protocol as per the timing diagram given in figure. The interface should include a status input port at I/O address 40H which reads the INTERRUPT and BUFFFULL signals through the most significant bit and the least significant bit, respectively. The output data port is at the same I/O address 40H and is activated by a write operation. Assume the availability of SSI and MSI level components only.
Write a short program segment which performs a 200 H byte programmed I/O data transfer to the device from memory address 3400 H,

(a) Consider the following pseudo-code
(all data items are of type integer):

   Procedure P (a, b, c);
                 a:=2;
                 c:=a+b;
   end {P}
   begin
                 x:=1
                 y:=5;
                 z:=100;
                 P(x,x*y,z);
                 Write (‘x=’,x,z=’,z)
   end: 

(b) For the following pseudo-code, indicate the output, if
(i) static scope rules and (ii) dynamic scope rules are used

      Var, a, b : integer;
      Procedure P;
         a:=5; b:=10
      end {P};
      procedure Q;
      var a, b : integer;
      P;
      end {Q};
      begin
      a:=1; b:=2;
      Q;
      Write (‘a =’, a, ‘b=’,b)
      end. 

Consider the following grammar for arithmetic expression using binary operators – and/which are not associative:

   E → E−T|T
   T → T/F|F
   F → (E)id 

(a) Is this grammar unambiguous? If so, what is the relative precedence between – and/if not, give an unambiguous grammar that gives/precedence over -
(b) Does the grammar allow expressions with redundant parentheses as in (id/id) or in id-(id/id)? If so, convert the grammar into one which does not generate expressions with redundant parentheses. Do this with minimum number of changes to the given production rules and adding at most one more production rule.

Consider the following scheme for implementing a critical section in a situation with three processes and P_j and P_k.

     Pi;
     repeat
            flag [i]:=true;
     while flag [j] or flag [k] do
            case turn of
            j : if flag [j] then
            begin
            flag [i]:=false;
            while turn ≠ i do skip;
            flag [i] : true
            end;
     k : if flag [k] then
            begin
            flag [i]:=false,
            while turn ≠ i do skip;
            flag [i]:=true
            end
     end
     critical section
     if turn = i then turn:=j;
     flag [i]:=false
     non-critical section
     until false; 

(a) Does the scheme ensure mutual exclusion in the critical section? Briefly explain.
(b) Is there a situation in which a waiting process can never enter the critical section? If so, explain and suggest modifications to the code to solve this problem.

Suppose, a database consists of the following relations:

     SUPPLIER (SCODE, SNAME, CITY)
     PART (PCODE, PNAME, PDESC, CITY)
     PROJECTS (PRCODE, PRNAME, CITY)
     SPRR (SCODE, PCODE, PRCODE, QJY)  

(a) Write SQL programs corresponding to the following queries:
(i) Print PCODE value for parts supplied to any project in DELHI by a supplier in DELHI.
(ii) Print all triples (CITY, PCODE, CITY), such that a supplier in the first city supplies the specified part to a project in the second city, but do not print triples in which the two CITY values are the same.

(b) Write algebraic solutions to the following:
(i) Get SCODE values for suppliers who supply to both projects PR1 and PR2.
(ii) Get PRCODE values for projects supplied by at least one supplier not in the same city.

Consider the binary tree in Figure:

(a) What structure is represented by the binary tree?
(b) Give the different steps for deleting the node with key 5 so that the structure is preserved.
(c) Outline a procedure in pseudo-code to delete an arbitrary node from such a binary tree with n nodes that preserves the structure. What is the worst-case time-complexity of your procedure?

(a) Show that the product of the least common multiple and the greatest common divisor of two positive integers a and b is a*b.
(b) Consider the following first order formula:

(Ax)(Ey)R(x,y)∧(Ax)(Ay)(R(x,y) → ~R(y,x))
        ∧(Ax)(Ay)(Az)(R(x,y)∧R(y,z) → R(x,z))
        ∧(Ax) ~R(x,x) 

(a) Find the number of binary strings w of length 2n with an equal number os 1’s and 0’s, and the property that every prefix and w has atleast as many 0’s as 1’s.
(b) Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.

(a) Show that Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class or regular languages.
(b) Let L be the language of all binary strings in which the third symbol from the right is a₁. Give a non-deterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?