FORTRAN implementation do not permit recursion because

Let A and B be real symmetric matrices of size n × n. Then which one of the following is true?

Backward Euler method for solving the differential equation dy/dx = f(x,y) is specified by, (choose one of the following).

Let A and B be any two arbitrary events, then, which one of the following is true?

An unrestricted use of the “goto” statement is harmful because

The number of distinct simple graphs with upto three nodes is

The recurrence relation that arises in relation with the complexity of binary search is:

The logic expression for the output of the circuit shown in figure below is:

The tank of matrix is:

Some group (G,o) is known to be abelian. Then, which one of the following is true for G?

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size n × n, non-zero elements (i.e elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the (i, j)^th element of the lower triangular matrix in this new representation is:

Generation of intermediate code based on an abstract machine model is useful in compilers because

A memory page containing a heavily used variable that was initialized very early and is in constant use is removed when

Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?

The number of substrings (of all lengths inclusive) that can be formed from a character string of length n is

Which of the following conversions is not possible (algorithmically)?

Linked lists are not suitable data structures of which one of the following problems?

Which of the following features cannot be captured by context-free grammars?

Which of the following algorithm design techniques is used in the quicksort algorithm?

In which one of the following cases is it possible to obtain different results for call-by reference and call-by-name parameter passing methods?

Which one of the following statements is true?

Which one of the following statements is false?

Consider the following two functions:

Which of the following is true?

Consider the following heap (figure) in which blank regions are not in use and hatched region are in use.

The sequence of requests for blocks of size 300, 25, 125, 50 can be satisfied if we use

The number of flip-flops required to construct a binary modulo N counter is __________.

On the set N of non-negative integers, the binary operation __________ is associative and non-commutative.

Amongst the properties {reflexivity, symmetry, anti-symmetry, transitivity} the relation R = {(x,y) ∈ N² | x ≠ y } satisfies __________.

The number of subsets {1, 2, ... n} with odd cardinality is __________.

The number of edges in a regular graph of degree d and n vertices is _________.

The probability of an event B is P₁. The probability that events A and B occur together is P₂ while the probability that A and occur together is P₃. The probability of the event A in terms of P₁, P₂ and P₃ is __________.

Consider n-bit (including sign bit) 2’s complement representation of integer number. The range of integer values, N, that can be represented is _________ ≤ N ≤ _________

Let A, B and C be independent events which occur with probabilities 0.8, 0.5 and 0.3 respectively. The probability of occurrence of at least one of the event is __________

The Hasse diagrams of all the lattices with up to four elements are __________ (write all the relevant Hasse diagrams).

The regular expression for the language recognized by the finite state automaton of figure is __________

State True or False with one line explanation
Multiplexing of address/data lines in 8085 microprocessor reduces the instruction execution time.

State True or False with one line explanation
Expanding opcode instruction formats are commonly employed in RISC. (Reduced Instruction Set Computers) machines.

State True or False with one line explanation
A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits).

Match the following items

Match the following items

State True or False with reason
There is always a decomposition into Boyce-Codd normal form (BCNF) that is lossless and dependency preserving.

An instance of a relational scheme R(A, B, C) has distinct values for attribute A.
Can you conclude that A is a candidate key for R?

Give a relational algebra expression using only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.

Every subset of a countable set is countable.
State whether the above statement is true or false with reason.

Match the following items

State True or False with reason
Logical data independence is easier to achieve than physical data independence

Find the inverse of the matrix

Let p and q be propositions. Using only the truth table decide whether p ⇔ q does not imply p → q is true or false.

(a) Let * be a Boolean operation defined as
If C = A * B then evaluate and fill in the blanks:
(i) A * A = _______
(ii) C * A = _______
(b) Solve the following boolean equations for the values of A, B and C:

A 3-ary tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a 3-ary tree with n interval nodes is 2(n-1)+3.

What function of x, n is computed by this program?

 Function what (x, n:integer): integer:
 Var
     value : integer;
     begin
     value:=1
     if n>0 then
 begin
     if n mod 2 = 1 then
     value:=value*x;
     value:=value*what(x*x, n div 2);
     end;
     what:value
     end; 

An array A contains n integers in locations A[0],A[1], …………… A[n-1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n-1. An incomplete algorithm for doing this in linear time, without using another is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably declared.

 min:=n;
 i=0;
 while _____do
 begin
     temp:=A[i];
     j:=i;
     while _____do
 begin
     A[j]:=_____;
     j:=(j+K) mod n;
 if j

A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, the nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1.
Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.

Following 7 bit single error correcting Hamming coded message is received. (figure below):

Determine if the message is correct (assuming that at most 1 bit could be corrupted). If the message contains an error find the bit which is erroneous and gives the correct message.

Write a program in 8085 Assembly language to Add two 16-bit unsigned BCD(8-4-2-1 Binary Coded Decimal) number. Assume the two input operands are in BC and DE Register pairs. The result should be placed in the register pair BC. (Higher order register in the register pair contains higher order digits of operand)

Find the contents of the flip-flop Q₂, Q₁ and Q₀ in the circuit of figure, after giving four clock pulses to the clock terminal. Assume Q₂Q₁Q₀ = 000 initially.

(a) Assume that a CPU has only two registers R₁ and R₂ and that only the following instruction is available XOR R_i, R_j; {R_j ← R_i ⊕ R_j, for i,j = 1,2}
Using this XOR instruction, find an instruction sequence in order to exchange the contents of the registers R₁ and R₂.

(b) The line p of the circuit shown in figure has stuck at 1 fault. Determine an input test to detect the fault.

Consider the following relational schema:

 COURSES (cno, cname)
 STUDENTS (rollno, sname, age, year)
 REGISTERED FOR (cno, rollno) 

(a) Write a relational algebra query to
Print the roll number of students who have registered for cno 322.
(b) Write a SQL query to
Print the age and year of the youngest student in each year.

Consider B+ − tree of order d shown in figure? (A) B⁺ − tree of order d contains between d and 2d keys in each node. (a) Draw the resulting B⁺ − tree after inserted in the figure.

(b) For a B⁺ − tree of order d with n leaf nodes, the number of nodes accessed during a search is 0(-).

(a) Use the patterns given to prove that

(b) Use the result obtained in (a) to prove that

Every element a of some ring (R,+,0) satisfies the equation aoa = a.
Decide whether or not the ring is commutative.

State whether the following statements are True or False with reasons for your answer:
(a) Coroutine is just another name for a subroutine.
(b) A two pass assembler uses its machine opcode table in the first pass of assembly.

State whether the following statements are True or False with reasons for your answer
(a) A subroutine cannot always be used to replace a macro in an assembly language program.
(b) A symbol declared as ‘external’ in assembly language is assigned an address outside the program by the assembler itself.

(a) Given a set
S = {x| there is an x-block of 5's in the decimal expansion of π}
(Note: x-block is a maximal block of x successive 5’s)
Which of the following statements is true with respect to S? No reasons need to be given for the answer.

(i) S is regular
(ii) S is recursively enumerable
(iii) S is not recursively enumerable
(iv) S is recursive

(b) Given that a language L₁ is regular and that the language L₁ ∪ L₂ is regular, is the language L₂ always regular? Prove your answer.

A grammar G is in Chomsky-Normal Form (CNF) if all its productions are of the form A → BC or A → a, where A, B and C, are non-terminals and a is a terminal. Suppose G is a CFG in CNF and w is a string in L(G) of length, then how long is a derivation of w in G?

Consider the following recursive function:

 function fib (1:integer);integer;
 begin
 if (n=0) or (n=1) then fib:=1
 else fib:=fib(n-1) + fib(n-2)
 end; 

The above function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter and passed on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack will not overflow. Give reasons for your answer.

Consider the program below:

 Program main;
    var r:integer;
    procedure two;
    begin write (r) end;
    procedure one;
    var r:integer;
    begin r:=5 two; end
    begin r:=2;
    two; one; two;
    end. 

What is printed by the above program if
(i) Static scoping is assumed for all variables;
(ii) Dynamic scoping is assumed for all variables.
Give reasons for your answer.

Suppose we have a computer with a single register and only three instructions given below:

 LOAD addren     ; load register
                 ; from addren
 STORE addren    ; store register
                 ; at addren
 ADD addren      ; add register to
                 ; contents of addren
                 ; and place the result
                 ; in the register 

Consider the following grammar:

   A → id :=E       E → E + T|T        T → (E)|id 

Write a syntax directed translation to generate code using this grammar for the computer described above.

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:

                      V: Set of all vertices in the tree;        I:=φ;
    While             V ≠ φdo
    begin
                      select a vertex u; ∈ V such that
                      V:= V – {u};
                      if u is such that
                      then 1:= I ∪ {u}
                      end;
                      output(I); 

(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.

An array a contains n integers in non-decreasing order, A[1] ≤ A[2] ≤ ... ≤ A[n]. Describe, using Pascal like pseudo code, a linear time algorithm to find i, j, such that A[i] + A[j] = a given integer M, if such i, j exist.

A queue Q containing n items and an empty stack S are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the top of the stack, and the order of all other items is preserved. Show how this can be done in O(n) time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

(a) Draw a precedence graph for the following sequential code. The statements are numbered from S₁ to S₆

 S1       read n
 S2       i:=1
 S3       if i>n goto next
 S4       a(i):=i+1
 S5       i:=i+1
 S6       next : Write a(i) 

(b) Can this graph be converted to a concurrent program using parbegin-parend construct only?

Consider the resource allocation graph given in the figure.

(a) Find if the system is in a deadlock state. (b) Otherwise, find a safe sequence.