GATE 1994

Question 1

FORTRAN implementation do not permit recursion because

A
they use static allocation for variables
B
they use dynamic allocation for variables
C
stacks are not available on all machines
D
it is not possible to implement recursion on all machines
       Algorithms       Recursions
Question 1 Explanation: 
FORTRAN implementation do not permit recursion because they use the static allocation for variables.
→ Recursion requires dynamic allocation of data.
Question 2

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

A
AA′ = 1
B
A = A-1
C
AB = BA
D
(AB)' = BA
       Engineering-Mathematics       Linear-Algebra
Question 2 Explanation: 
Question 3

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

A
yn+1 = yn + hf(xn, yn)
B
yn+1 = yn + hf(xn+1, yn+1)
C
yn+1 = yn-1 + 2hf(xn, yn)
D
yn+1 = (1 + h) f(xn+1, yn+1)
       Engineering-Mathematics       Calculus
Question 3 Explanation: 
dy/dx = f(x,y)
With initial value y(x0) = y0. Here the function f and the initial data x0 and y0 are known. The function y depends on the real variable x and is unknown. A numerical method produces a sequence y0, y1, y2, ....... such that yn approximates y(x0 + nh) where h is called the step size.
→ The backward Euler method is helpful to compute the approximations i.e.,
yn+1 = yn + hf(x n+1, yn+1)
Question 4

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

A
P(A∩B) = P(A)P(B)
B
P(A∪B) = P(A) + P(B)
C
P(A|B) = P(A∩B)P(B)
D
P(A∪B) ≤ P(A) + P(B)
       Engineering-Mathematics       Probability
Question 4 Explanation: 
(A) Happens when A and B are independent.
(B) Happens when A and B are mutually exclusive.
(C) Not happens.
(D) P(A∪B) ≤ P(A) + P(B) is true because P(A∪B) = P(A) + P(B) - P(A∩B).
Question 5

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

A
it makes it more difficult to verify programs
B
it increases the running time of the programs
C
it increases the memory required for the programs
D
it results in the compiler generating longer machine code
       Data-Structures       Programming
Question 5 Explanation: 
If we use "goto" statements then it leads to structural decomposition of code then it is difficult to verify the programs.
Question 6

The number of distinct simple graphs with upto three nodes is

A
15
B
10
C
7
D
9
       Engineering-Mathematics       Graph-Theory
Question 6 Explanation: 
Question 7

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

A
T(n) = T(n/2) + k, k a constant
B
T(n) = 2T(n/2) + k, k a constant
C
T(n) = T(n/2) + log n
D
T(n) = T(n/2) + n
       Algorithms       Time-Complexity
Question 7 Explanation: 
In binary search, search for the half of the list and constant time for comparing. So,
∴ T(n) = 2T(n/2) + k, k a constant
Question 8

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

A
B
C
D
E
None of the above.
       Digital-Logic-Design       Logic-Gates
Question 8 Explanation: 
Question 9

The tank of matrix is:

A
0
B
1
C
2
D
3
       Engineering-Mathematics       Linear-Algebra
Question 9 Explanation: 
Question 10

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

A
g = g-1 for every g ∈ G
B
g = g2 for every g ∈ G
C
(goh)2 = g2oh2 for every g,h ∈ G
D
G is of finite order
       Engineering-Mathematics       Groups
Question 10 Explanation: 
Associate property of a group (aob)oc = ao(boc)
For Abelian group, commutative also holds
i.e., (aob) = (boa)
Consider option (C):
(goh)2 = (goh)o(gog)
= (hog)o(goh)
= (ho(gog)oh)
= ((hog2)oh)
= (g2oh)oh
= g2o(hoh)
= g2oh2 [True]
Question 11

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:

A
i + j
B
i + j - 1
C
j + i(i-1)/2
D
i + j(j-1)/2
       Engineering-Mathematics       Linear-Algebra
Question 11 Explanation: 
Though not mentioned in question, from options it is clear that array index starts from 1 and not 0.
If we assume array index starting from 1 then, ith row contains i number of non-zero elements. Before ith row there are (i-1) rows, (1 to i-1) and in total these rows has 1+2+3......+(i-1) = i(i-1)/2 elements.
Now at ith row, the jth element will be at j position.
So the index of (i, j)th element of lower triangular matrix in this new representation is
j = i(i-1)/2
Question 12

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

A
it makes implementation of lexical analysis and syntax analysis easier
B
syntax-directed translations can be written for intermediate code generation
C
it enhances the portability of the front end of the compiler
D
it is not possible to generate code for real machines directly from high level language programs
       Compiler-Design       Compilers
Question 12 Explanation: 
In Intermediate code optimizations can also enhances the probability of optimizer.
Question 13

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

A
LRU page replacement algorithm is used
B
FIFO page replacement algorithm is used
C
LFU page replacement algorithm is used
D
None of the above
       Operating-Systems       Page-Replacement-Algorithm
Question 13 Explanation: 
In FIFO, whichever comes first that can be removed first. If the variable was initialized very early, it is in set of first pages. So it was removed.
In LRU which can eliminate (or) removed which is least recently used.
In LFU the frequency of the page is more. So it is in constant use so cannot be replaced.
Question 14

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?

A
3, 4, 5, 1, 2
B
3, 4, 5, 2, 1
C
1, 5, 2, 3, 4
D
5, 4, 3, 1, 2
       Data-Structures       Stacks
Question 14 Explanation: 
Push 1 Push 2 Push 3 Pop 3 Push 4 Pop 4 Push 5 Pop 5 Pop 2 Pop 1.
→ Remaining options are not possible.
Question 15

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

A
n
B
n2
C
n(n-1)/2
D
n(n+1)/2
       Engineering-Mathematics       Permutation-and-Combination
Question 15 Explanation: 
No. of substrings of length
n = 1
(n-1) = 2
(n-2) = 3
So, Total = n(n+1)/2
Question 16

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

A
Regular grammar to context free grammar
B
Non-deterministic FSA to deterministic FSA
C
Non-deterministic PDA to deterministic PDA
D
Non-deterministic Turing machine to deterministic Turing machine
       Theory-of-Computation       Grammar
Question 16 Explanation: 
NPDA to DPDA conversion is not possible. They have different powers.
Question 17

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

A
Insertion sort
B
Binary search
C
Radix sort
D
Polynomial manipulation
       Data-Structures       Linked-List
Question 17 Explanation: 
In linked list finding an element take O(n) which is not suitable for the binary search. And time complexity of binary search is O(log n).
Question 18

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

A
Syntax of if-then-else statements
B
Syntax of recursive procedures
C
Whether a variable has been declared before its use
D
Variable names of arbitrary length
       Theory-of-Computation       CFG
Question 18 Explanation: 
Context free grammars are used to represent syntactic rules while designing a compiler.
Syntactic rules not checking the meaningful things such as if a variable is declared before it use (or) not.
Like this, things are handled by semantic analysis phase.
Question 19

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

A
Dynamic programming
B
Backtracking
C
Divide and conquer
D
Greedy method
       Algorithms       Quick-Sort
Question 19 Explanation: 
In quick sort, we use divide and conquer technique.
Question 20

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?

A
Passing a constant value as a parameter
B
Passing the address of an array as a parameter
C
Passing an array element as a parameter
D
Passing an array following statements is true
       Algorithms       Call-by-reference-and-Call-by-value
Question 20 Explanation: 
Passing an array element as a parameter then it gives different output values for the call-by-reference and call-by-name parameters.
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Call-by-reference = 8
Call-by-value = 1
Question 21

Which one of the following statements is true?

A
Macro definitions cannot appear within other macro definitions in assembly language programs
B
Overlaying is used to run a program which is longer than the address space of computer
C
Virtual memory can be used to accommodate a program which is longer than the address space of a computer
D
It is not possible to write interrupt service routines in a high level language
       Computer-Organization       General
Question 21 Explanation: 
A macro body can also have further macro definitions. However, these nested macro definitions aren't valid until the enclosing macro has been expanded. That means enclosing macro must have been called before the macros can be called.
Question 22

Which one of the following statements is false?

A
Optimal binary search tree construction can be performed efficiently using dynamic programming.
B
Breadth-first search cannot be used to find connected components of a graph.
C
Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D
Depth-first search can be used to find connected components of a graph.
       Algorithms       Searching
Question 22 Explanation: 
In BFS algorithm, we can randomly select a source vertex and then run, after that whether we need to check distance to each and every vertex from source is still infinite (or) not. If we find any vertex having infinite distance then the graph is not connected.
Question 23

Consider the following two functions:

Which of the following is true?

A
g1(n) is O(g2(n))
B
g1 (n) is O(3)
C
g2 (n) is O(g1 (n))
D
g2 (n) is O(n)
E
Both A and B
       Algorithms       Asymptotic-Notations
Question 23 Explanation: 
In asymptotic complexity, we assume sufficiently large n. So, g1(n) = n2 and g2(n) = n3.
Growth rate of g1 is less than that of g2 i.e., g1(n) = O(g2(n)) = O(n).
Question 24

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

A
either first fit or best fit policy (any one)
B
first fit but not best fit policy
C
best fit but first fit policy
D
None of the above
       Operating-Systems       Page-Replacement-Algorithm
Question 24 Explanation: 
In first fit, block request will be satisfied from the first free block that fits it.
So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 125 size block, reducing it to 125.
Request for 125 satisfied by the 125 size block.
And request for 50 satisfied by 50 size block.
So, all requests can be satisfied.
In best fit strategy, a block request is satisfied by the smallest block in which can fit it. So, request for 300 will be satisfied by 350 size block reducing the free size to 50.
Request for 25, satisfied by 50 size block as its the smallest size that fits 25, reducing it to 25.
Request for 125, satisfied by 150 size block, reducing it to 25.
Now, request for 50 cannot be satisfied as the two 25 size blocks are not contiguous.
Question 25

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

A
⌈log2 N⌉
       Digital-Logic-Design       Flip-Flops
Question 25 Explanation: 
For mod-N counter we need ⌈log2 N⌉ flip flops.
Question 26

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

A
fog
       Engineering-Mathematics       Functions
Question 26 Explanation: 
The most important associative operation that is not commutative is function composition. If you have two functions f and g, their composition, usually denoted fog, is defined by
(fog)(x) = f(g(x))
It is associative, (fog)oh = fo(goh), but its usually not commutative. fog is usually not equal to gof.
Note that if fog exists then gof might not even exists.
Question 27

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

A
symmetry
       Engineering-Mathematics       Relations
Question 27 Explanation: 
It is not reflexive as xRx is not possible.
It is symmetric as if xRy then yRx.
It is not antisymmetric as xRy and yRx are possible and we can have x≠y.
It is not transitive as if xRy and yRz then xRz need not be true. This is violated when x=x.
So, symmetry is the answer.
Question 28

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

A
2n-1
       Engineering-Mathematics       Set-Theory
Question 28 Explanation: 
Total no. of subsets with n elements is 2n.
And so, no. of subsets with odd cardinality is half of total no. of subsets = 2n /n = 2n-1
Question 29

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

A
d*n/2
       Engineering-Mathematics       Graph-Theory
Question 29 Explanation: 
Sum of degree of vertices = 2 × no. of edges
d * n = 2 * |E|
∴ |E| = d*n/2
Question 30

The probability of an event B is P1. The probability that events A and B occur together is P2 while the probability that A and occur together is P3. The probability of the event A in terms of P1, P2 and P3 is __________.

A
P2 + P3
       Engineering-Mathematics       Probability
Question 30 Explanation: 
P(A∩B') = P(A) - P(A∩B)
P3 = P(A) - P2
P(A) = P2 + P3
Question 31

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 ≤ _________

A
-2n-1 to 2n-1 - 1
       Digital-Logic-Design       Number-Systems
Question 32

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 __________

A
0.93
       Engineering-Mathematics       Probability
Question 32 Explanation: 
P(A∪B∪C) = P(A) + P(B) + P(C) - P(A∩B) - P(B∩C) - P(A∩C) + P(A∩B∩C)
Since all the events are independent, so we can write
P(A∪B∪C) = P(A) + P(B) + P(C) - P(A)P(B) - P(B)P(C) - P(A)P(C) + P(A)P(B) P(C)
= 0.8 + 0.5 + 0.3 - 0.4 - 0.5 - 0.24 + 0.12
= 0.93
Question 33

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

A
       Engineering-Mathematics       Lattices
Question 33 Explanation: 
For 1 element:
We can't draw lattice with 1 element.
For 2 element:

For 3 element:

For 4 element:
Question 34

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

A
L = 0*1*
       Theory-of-Computation       Finite-Automata
Question 34 Explanation: 
L = 0*1*
L contains all binary strings where a 1 is not followed by a 0.
Question 35

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

A
True
B
False
       Computer-Organization       Microprocessor
Question 35 Explanation: 
Note: Out of syllabus.
The major reason of multiplexing address and data bus is to reduce the number of pins for address and data and dedicate those pins for other several functions of micro-processor.
Question 36

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

A
True
B
False
       Computer-Organization       RISC
Question 36 Explanation: 
RISC systems use fixed length instruction to simplify pipeline.
Now the challenge is: How to fit multiple sets of instructions types into limited or fixed size instruction format.
Here comes expanding opcode into the picture, So RISC system uses expanding opcode technique to have fixed size instructions.
Question 37

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).

A
True
B
False
       Computer-Organization       Finite-State-Machine
Question 37 Explanation: 
FA or Finite state machine to add two integers can be constructed using two states:
→ q0: Start state to represent carry bit is 0.
→ q1: State to represent carry bit is 1.
The inputs to the FA will be pairs of bits, i.e., 00, 01, 10, 11.

The FA starts in state 1 (since carry is 0) and inputs a pair of bits. If the pair is 11, the FA outputs a '0' and switches to state 2 (since the carry is 1), where the next pair of bits is input and is added to a carry bit of 1.
Question 38

Match the following items

A
(i) - (b), (ii) - (c), (iii) - (d), (iv) - (a)
       Engineering-Mathematics       General
Question 38 Explanation: 
Note: Out of syllabus.
Question 39

Match the following items

A
(i) - (d), (ii) - (a), (iii) - (b), (iv) - (c)
       Compiler-Design       General
Question 39 Explanation: 
Backus Normal Form (BNF) is a notation technique for context free grammars, often used to describe the syntax of languages used in computing.
Yacc (Yet Another Compiler- Compiler) is a computer program for the UNIX operating system. It is a LALR parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specially a LALR parser, based on an analytic grammar. Yacc is written in portable C.
Question 40

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

A
True
B
False
       Database-Management-System       Normalizations
Question 40 Explanation: 
BCNF decomposition can always be lossless, but it may not be always possible to get a dependency preserving BCNF decomposition.
Question 41

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?

A
Yes
B
No
       Database-Management-System       Normal-Forms
Question 41 Explanation: 
Because FD's are defined on the schema itself, not the instance. So, based on the state of the instance we cannot say what holds for schema (there can be many instances for R).
Question 42

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

A
Out of syllabus (For explanation see below)
       Database-Management-System       Relational-Algebra
Question 42 Explanation: 
R - (R - S)
→ No need of using Union operation here. → In question they gave (∪, −) but we don't use both.
→ And also they are saying that only the minimum number of operators from (∪, −) which is equivalent to R ∩ S.
So, the expression is minimal.
Question 43

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

A
True
B
False
       Theory-of-Computation       Undecidability
Question 43 Explanation: 
Because if a set itself is countable then the subset of set is definitely countable.
Question 44

Match the following items

 
A
(i) - (a), (ii) - (b), (iii) - (d), (iv) - (c)
       Computer-Organization       General
Question 44 Explanation: 
Note: Out of syllabus.
Question 45

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

A
True
B
False
       Database-Management-System       General
Question 45 Explanation: 
Logical data independence is more difficult to achieve than physical data independence, since application programs are heavily dependent on the logical structure of the data that they access.
Question 46

Find the inverse of the matrix

A
B
C
D
       Engineering-Mathematics       Linear-Algebra
Question 46 Explanation: 
Using eigen values, the characteristic equation we get is,
3 + 2λ2 - 2 = 0
Using Cayley-Hamiltonian theorem
-A3 + 2A2 - 2I = 0
So, A-1 = 1/2 (2A - A2)
Solving we get,
Question 47

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
True
B
False
       Engineering-Mathematics       Prepositional-Logic
Question 47 Explanation: 

So, "imply" is False making "does not imply" True.
Question 48

(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
Theory Explanation.
Question 49

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.

A
Theory Explanation.
Question 50

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; 
A
Theory Explanation.
Question 51

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
Theory Explanation.
Question 52

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.

A
Theory Explanation.
Question 53

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.

A
Theory Explanation.
Question 54

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)

A
Theory Explanation.
Question 55

Find the contents of the flip-flop Q2, Q1 and Q0 in the circuit of figure, after giving four clock pulses to the clock terminal. Assume Q2Q1Q0 = 000 initially.

A
Theory Explanation.
Question 56

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

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

A
Theory Explanation.
Question 57

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.

A
Theory Explanation.
Question 58

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
Theory Explanation.
Question 59

(a) Use the patterns given to prove that


(You are not permitted to employ induction)

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

A
Theory Explanation.
Question 60

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

A
Theory Explanation.
Question 61

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.

A
Theory Explanation.
Question 62

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
Theory Explanation.
Question 63

(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 L1 is regular and that the language L1 ∪ L2 is regular, is the language L2 always regular? Prove your answer.

A
Theory Explanation.
Question 64

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?

A
Theory Explanation.
Question 65

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.

A
Theory Explanation.
Question 66

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.

A
Theory Explanation.
Question 67

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.

A
Theory Explanation.
Question 68

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.

A
Theory Explanation.
Question 69

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
Theory Explanation.
Question 70

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
Theory Explanation.
Question 71

(a) Draw a precedence graph for the following sequential code. The statements are numbered from S1 to S6

 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?

A
Theory Explanation.
Question 72

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.

A
Theory Explanation.
There are 72 questions to complete.