GATE 1997
Question 1 
The probability that it will rain today is 0.5. The probability that it will rain tomorrow is 0.6. The probability that it will rain either today or tomorrow is 0.7. What is the probability that it will rain today and tomorrow?
0.3  
0.25  
0.35  
0.4 
P(Tomorrow) = 0.6
P(T∪To) = 0.7
P(T∩To) = P(T) + P(To)  P(T∪To)
= 0.5 + 0.6  0.07
= 1.1  0.7
= 0.4
Question 2 
The NewtonRaphson method is used to find the root of the equation x^{2}  2 = 0. If the iterations are started from 1, the iterations will
converge to 1  
converge to √2  
converge to  √2  
not converge 
Question 3 
The determinant of the matrix is is:
11  
48  
0  
24 
Question 4 
The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?
Singly linked list  
Doubly linked list  
Circular doubly linked list  
Array implementation of list 
Question 5 
The correct matching for the following pairs is
(A) All pairs shortest path (1) Greedy (B) Quick Sort (2) DepthFirst search (C) Minimum weight spanning tree (3) Dynamic Programming (D) Connected Components (4) Divide and and Conquer
A – 2 B – 4 C – 1 D – 3  
A – 3 B – 4 C – 1 D – 2  
A – 3 B – 4 C – 2 D – 1  
A – 4 B – 1 C – 2 D – 3 
Quick sort  Divide and Conquer
Minimum weight Spanning tree  Greedy
Connected components  DepthFirst search
Question 6 
In the following grammar
X ::= X ⊕ Y/Y Y ::= Z * Y/Z Z ::= id
Which of the following is true?
‘⊕’ is left associative while ‘*’ is right associative  
Both ‘⊕’ and ‘*’ is left associative  
‘⊕’ is right associative while ‘*’ is left associative  
None of the above 
⊕ is left associative.
* is right associative.
Question 7 
Which of the following is essential for converting an infix expression to the postfix from efficiently?
An operator stack  
An operand stack  
An operand stack and an operator stack  
A parse tree 
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
Question 8 
A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which of the following is true?
A compiler using static memory allocation can be written for L  
A compiler cannot be written for L; an interpreter must be used  
A compiler using dynamic memory allocation can be written for L  
None of the above 
Question 9 
The conditional expansion facility of macro processor is provided to
test a condition during the execution of the expanded program  
to expand certain model statements depending upon the value of a condition during the execution of the expanded program  
to implement recursion  
to expand certain model statements depending upon the value of a condition during the process of macro expansion 
Question 10 
Heap allocation is required for languages
that support recursion  
that support dynamic data structures  
that use dynamic scope rules  
None of the above 
Question 11 
Let * be defined as x * y = x' + y. Let z = x * y. Value of z * x is
x'+y  
x  
0  
1 
Question 12 
RST 7.5 interrupt in 8085 microprocessor executes the interrupt service routine from interrupt vector location
0000H  
0075H  
003CH  
0034H 
→ 60 in hexa decimal is 003CH.
Question 13 
Purpose of a start bit in RS 232 serial communication protocol is
to synchronize receiver for receiving every byte  
to synchronize receiver for receiving a sequence of bytes  
a parity bit  
to synchronize receiver for receiving the last byte 
Question 14 
The correct matching for the following pairs is
(A) DMA I/O (1) High speed RAM (B) Cache (2) Disk (C) Interrupt I/O (3) Printer (D) Condition Code Register (4) ALU
A – 4 B – 3 C – 1 D – 2  
A – 2 B – 1 C – 3 D – 4
 
A – 4 B – 3 C – 2 D – 1  
A – 2 B – 3 C – 4 D – 1 
Cache → High speed RAM
Interrupt I/O → Printer
Condition code register → ALU
Question 15 
An Nbit carry look ahead adder, where N is a multiple of 4, employs ICs 74181 (4 bit ALU) and 74182 (4 bit carry look ahead generator).
The minimum addition time using the best architecture for this adder is
proportional to N  
proportional to log N  
a constant  
None of the above 
Question 16 
Let (Z,*) be an algebraic structure, where Z is the set of integers and the operation * is defined by n*m = maximum (n,m). which of the following statements is true for (Z,*)?
(Z,*) is a monoid  
(Z,*) is an Abelian group  
(Z,*) is a group  
None of the above 
Monoid  Closed, Associative and has an identity
Group  Monoid with inverse
Abelian group  Group with commutative property
Go through with given:
Closure: Yes.
(m*n = max(m,n)) output is either m or n whichever is maximum since m,n belongs z. The result of the binary operation also belongs to z. So given is satisfying closure property.
Associative: Yes.
The output is max among the elements and it is associative.
Identity: No.
We don't have single unique element for all the elements which is less than all the elements.
Given one is semigroup only.
Question 17 
Which of the following propositions is a tautology?
(p ∨ q) → p  
p ∨ (q → p)  
p ∨ (p → q)  
p → (p → q) 
Question 18 
In a lattice defined by the Hasse diagram given in following figure, how many complements does the element 'e' have?
2  
3  
0  
1 
No. of complements = 3
e∨g = a and e∧g = f
e∨c = a and e∧c = f
e∨d = a and e∧d = f
Question 19 
Given Σ = {a,b}, which one of the following sets is not countable?
Set of all strings over Σ  
Set of all languages over Σ  
Set of all regular languages over Σ  
Set of all languages over Σ accepted by Turing machines 
Question 20 
Locality of reference implies that the page reference being made by a process
will always be to the page used in the previous page reference  
is likely to be to one of the pages used in the last few page references  
will always be to one of the pages existing in memory  
will always lead to a page fault 
(1) Temporal locality
(2) Spatial locality
(3) Sequential locality
→ In programs related data are stored in consecutive locations and loops in same locations are used repeatedly.
Question 21 
The correct matching for the following pairs is
(A) Disk Scheduling (1) Round robin (B) Batch Processing (2) SCAN (C) Time sharing (3) LIFO (D) Interrupt processing (4) FIFO
A – 3 B – 4 C – 2 D – 1  
A – 4 B – 3 C – 2 D – 1  
A – 2 B – 4 C – 1 D – 3  
A – 3 B – 4 C – 3 D – 2 
Batch processing  FIFO
Time sharing  Round Robin
Interrupt processing  LIFO
Question 22 
I/O redirection
implies changing the name of a file  
can be employed to use an existing file as input file for a program  
implies connection 2 programs through a pipe  
None of the above

Question 23 
When an interrupt occurs, an operating system
ignores the interrupt  
always changes state of interrupted process after processing the interrupt  
always resumes execution of interrupted process after processing the interrupt
 
may change state of interrupted process to 'blocked’ and schedule another process

Option B: Not always.
Option C: Not always. If some high priority interrupt comes during execution of current interrupt then it fails.
Option D: It is True always.
Question 24 
Thrashing
reduces page I/O  
decreases the degree of multiprogramming  
implies excessive page I/O  
improve the system performance 
Question 25 
Dirty bit for a page in a page table
helps avoid unnecessary writes on a paging device  
helps maintain LRU information  
allows only read on a page  
None of the above 
Question 26 
What is the maximum value of the function f(x) = 2x^{2}  2x + 6 in the interval [0,2]?
6  
10  
12  
5.5 
f'(x) = 4x  2 = 0
⇒ x = 1/2
So at x = 1/2, f(x) is an extremum (either maximum or minimum).
f(2) = 2(2)^{2}  2(2) + 6 = 10
f(1/2) = 2 × (1/2)^{2}  2 × 1/2 + 6 = 5.5
f(0) = 6
So, the maximum value is at x=2 which is 10 as there are no other extremum for the given function.
Question 27 
Let A = (a_{ij}) be an nrowed square matrix and I_{12} be the matrix obtained by interchanging the first and second rows of the nrowed Identify matrix. Then AI_{12} is such that its first
row is the same as its second row  
row is the same as the second row of A  
column is the same as the second column of A  
row is all zero 
So, we can see that column 1 and 2 got interchanged.
Question 28 
Using a forward Euler method to solve y′′(t) = f(t), y(0), y′′(0) = 0 with a step size of h, we obtain the following values of y in the first four iterations:
0, hf(0), h(f(0) + f(h)) and h(f(0) + f(h) = f(2h))  
0, 0 h^{2}f(0) and 2h^{2}f(0) + f(h)  
0, 0, h^{2}f(0) 3h^{2}f(0)  
0, 0, hf(0) + h^{2}f(0) and hf(0) + h^{2}f(0) + hf(h) 
Question 29 
A polynomial p(x) is such that p(0) = 5, p(1) = 4, p(2) = 9 and p(3) = 20. The minimum degree it can have is
1  
2  
3  
4 
p(0) = 5 ⇒ b = 5
p(1) = 4 ⇒ a+b = 4 ⇒ a = 1
p(2) = 9 ⇒ 40+b = 9 ⇒ 4+5 = 9, which is false.
So degree 1 is not possible.
Lets take p(x) = ax^{2} + bx +c
p(0) = 5 ⇒ c = 5
p(1) = 4 ⇒ a+b+c = 4 ⇒ a+b = 1 (1)
p(2) = 9 ⇒ 4a+2b+c = 9 ⇒ 2a+b = 2 (2)
(2)  (1)
⇒ a = 3, b = 11 = 4
p(3) = 20 ⇒ 9a+3b+c = 20
⇒ 2712+5 = 20
⇒ 20 = 20, True
Hence, minimum degree it can have.
Question 30 
A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in preorder and the values are printed out. Which of the following sequences is a valid output?
5 3 1 2 4 7 8 6  
5 3 1 2 6 4 8 7  
5 3 2 4 1 6 7 8  
5 3 1 2 4 7 6 8 
Option D:
Let draw binary search tree for the given sequence,
After traversing through this tree we will get same sequence.
Question 31 
Let T(n) be the function defined by T(1)= 1, T(n)= 2T(⌊n/2⌋) + √n for n≥2. Which of the following statement(s) is true?
T(n) = O(√n)  
T(n) = O(n)  
T(n) = O(log n)  
None of the above 
Question 32 
A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in
nonincreasing order  
nondecreasing order  
strictly increasing order  
strictly decreasing order 
Question 33 
Given the following Pascallike program segment
Procedure A; x,y: integer; Procedure B; x,z: real S1 end B; Procedure C; i: integer; S2 end C; end A;
The variables accessible in S1 and S2 are
x or A, y, x of B and z in S1 and x of B, y and i in S2  
x or B, y and z in S1 and x of B, i and z in S2  
x or B, z and y in S1 and x of A, i and y in S2  
None of the above 
Question 34 
The expression (a*b)* c op....
where 'op' is one of '+', '*' and '↑' (exponentiation) can be evaluated on a CPU with a single register without storing the value of (a * b) if
‘op’ is ’+’ or ‘*’  
‘op’ is ’↑’ or ‘*’  
‘op’ is ’↑’ or ‘+’  
not possible to evaluate without storing 
(a*b)*c + d
(a*b)*c * d
(a*b)*c ∧ d
In any case, brackets has the highest priority always. So I have to compute brackets first. Now, for + and *, I can do the rest of the operation and save results in the same register. But for exponentiation, I have to store the result of a*b, then do the computation of c∧d, then multiply these two results.
Hence, (A) is correct.
Question 35 
The trapezoidal method to numerically obtain has an error E bounded by
((ba)/12)h^{2} max f''(x), x∈[a,b]
where h is the width of the trapezoids. The minimum number of trapezoids guaranteed to ensure E ≤ 10^{4} in computing ln 7 using f = 1/x is
60  
100  
600  
10000 
Question 36 
Let f(x, y, z) = x' + y'x + xz be a switching function. Which one of the following is valid?
xz is a minterm of f  
xz is an implicant of f  
y is a prime implicant of f 
Question 37 
Contents of A register after the execution of the following 8085 microprocessor program is
MVI A, 55 H MVI C, 25 H ADD C DAA
7AH  
80H  
50H  
22H 
Question 38 
A micro instruction into be designed to specify
 (a) none or one of the three micro operations of one kind and
(b) none or upto six micro operations of another kind
The minimum number of bits in the microinstruction is
9  
5  
8  
None of the above 
So, no. of bits required
⌈log_{2} (3)⌉ = 2
(b) This is a horizontal microprogramming because at any given time atmost six microoperations will be activated.
So, no. of bits required = 6
So, total minimum no. of bits required = 6+2 = 8
Question 39 
Given √224)_{r} = 13)_{r}.
The value of the radix r is:
10  
8  
5  
6 
Convert r base to decimal.
√2r^{2} + 25 + 4 = r + 3
Take square both sides,
2r^{2} + 2r + 4 = r^{2} + 6r + 9
r^{2}  4r  5 = 0
r^{2}  5r + r  5 = 0
r(r  5) + (r  5) = 0
r = 1, 5
r cannot be 1,
So r = 5 is correct answer.
Question 40 
Consider a logic circuit shown in figure below. The functions f_{1}, f_{2} and f (in canonical sum of products form in decimal notation) are:
f_{1}(w,x,y,z) = ∑8,9,10 f_{2}(w,x,y,z) = ∑7,8,12,13,14,15 f(w,x,y,z) = ∑8,9
The function f_{3} is
Σ9,10  
Σ9  
Σ1,8,9  
Σ8,10,15 
Since, f_{1} and f_{2} are in canonical sum of products form, f_{1}⋅f_{2} will only contain their common terms that is f_{1}⋅f_{2} = Σ8.
Now,
Σ8 + f_{3} = Σ8,9
So, f_{3}= Σ9
Question 41 
A partial order ≤ is defined on the set S= {x, a_{1}, a_{2},.....a_{n}, y} as x < a_{i} for all i and a_{i} ≤ y for all i, where n≥1. The number of total orders on the set S which contain the partial order ≤ is
n!  
n+2  
n  
1 
So for every a_{i}, a_{j} we have to add either (a_{i}, a_{j}) or (a_{j}, a_{i} in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways. So answer is (A).
Question 42 
Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if i  j = 8 or i  j = 12. The number of connected components in G is
8  
4  
12  
25 
1 — 9 — 17 — ......... — 97
2 — 10 — 18 — ......... — 98
3 — 11 — 19 — ......... — 99
4 — 12 — 20 — ......... — 100
5 — 13 — 21 — ......... — 93
6 — 14 — 22 — ......... — 94
7 — 15 — 23 — ......... — 95
8 — 16 — 24 — ......... — 96
We have covered all vertices using 8 vertex sets considering only i  j = 8. Using i  j = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
Question 43 
The number of equivalence relations of the set {1,2,3,4} is
15  
16  
24  
4 
Question 44 
Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?
0*(1+0)*  
0*1010*  
0*1*01  
0(10+1)* 
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 45 
Which one of the following is not decidable?
Given a Turing machine M, a stings s and an integer k, M accepts s within k steps  
Equivalence of two given Turing machines  
Language accepted by a given finite state machine is not empty  
Language generated by a context free grammar is non empty 
In (A) the number of steps is restricted to a finite number 'k' and simulating a TM for 'k' steps is trivially decidable because we just go to step k and output the answer.
(B) Equivalence of two TM's is undecidable.
For options (C) and (D) we do have well defined algorithms making them decidable.
Question 46 
Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?
Note: w^{R} is the string obtained by reversing 'w'.
{w⊂w^{R}w ∈ {a,b}*}  
{ww^{R}w ∈ {a,b,c}*}  
{a^{n}b^{n}c^{n}n ≥ 0}  
{ww is a palindrome over {a,b,c}} 
(B) ww^{R}, is realized by NPDA because we can't find deterministically the center of palindrome string.
(C) {a^{n}b^{n}c^{n}  n ≥ 0} is CSL.
(D) {w  w is palindrome over {a,b,c}},
is realized by NPDA because we can't find deterministically the center of palindrome string.
Question 47 
An operating system contains 3 user processes each requiring 2 units of resource R. The minimum number of units of r such that no deadlocks will ever arise is
3  
5  
4  
6 
Question 48 
Each Process P_{i}, i = 1.......9 is coded as follows
repeat P(mutex) {Critical section} V(mutex) forever
The code for P_{10} is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?
1  
2  
3  
None of the above 
repeat
{
V(mutex)
C.S.
V(mutex)
}
forever
Now, let me say P_{1} is in CS then P_{1} is in CS
then P_{10} comes and executes CS (upon mutex).
Now, P_{2} comes (down on mutex).
Now P_{10} moves out of CS (again binary semaphore will be 1).
Now P_{3} comes (down on mutex).
Now P_{10} comes (upon mutex).
Now P_{4} comes (down mutex).
⁞
So, if we take P_{10} 'in' and 'out' of CS recursively, all 10 processes can be in CS at same time using binary semaphore only.
Question 49 
For a database relation R(a,b,c,d), where the domains a, b, c, d include only atomic values, only the following functional dependencies and those that can be inferred from them hold:
a → c b → d
This relation is
in first normal form but not in second normal form  
in second normal form but not in third normal form  
in third normal form  
None of the above 
Since all a, b, c, d are atomic. So the relation is in 1NF.
Checking the FD's
a → c
b → d
We can see that there is partial dependencies. So it is not 2NF.
So answer is option (A).
Question 50 
Let R(a,b,c) and S(d,e,f) be two relations in which d is the foreign key of S that refers to the primary key of R. Consider the following four operations R and S
(a) Insert into R (b) Insert into S (c) Delete from R (d) Delete from S
Which of the following can cause violation of the referential integrity constraint above?
None of (a), (b), (c) or (d) can cause its violation  
All of (a), (b), (c) and (d) can cause its violation  
Both (a) and (d) can cause its violation  
Both (b) and (c) can cause its violation 
Here 'd' is the foreign key of S and let 'a' is the primary key of R.
(A) Insertion into R: will cause no violation.
(B) Insertion into S: may cause violation because there may not be entry of the tuple in relation R. Example entry of 〈S_{4}, __, __〉 is not allowed.
(C) Delete from R: may cause violation. For example, deletion of tuple 〈S_{2}, __, __〉 will cause violation as there is entry of S_{2} in the foreign key table.
(D) Delete from S: will cause no violation as it does not result inconsistency.
Question 51 
A D flipflop is to be connected to an 8085 microprocessor chip as a 1bit output port with a port address of FF hex. Data bit D3 should be involved in the data transfer from CPU to the flipflop. The flipflop should be cleared on power ON.
(a) Using only one NAND gate (fan in of 10), one NOT gate and one D flipflop. Draw the required interface logic circuit (only the relevant signals should be shown).
(b) Write a program to generate a square wave on the output of the flipflop. ON and OFF periods of the square wave should be 7 bus cycles each.
Theory Explanation. 
Question 52 
Let L = {a_{1}, a_{2}, ......, a_{n}} n ≥ 0 be a list whose Pascal representation is
type list = record next: ↑ list; val: integer end
The following function returns a list in which a_{2i} and a_{2i1}, 1 ≤ i ≤ [n/2] are interchanged. Complete the function by filling the boxes. Write the line number and the content of the box in your answer sheet.
1. function change (p: ↑ list): ↑ list; 2. var q.t: ↑ list; 3. begin 4. if p = nil then change := p 5. else if p ↑ next = nil then change : ▭ 6. else begin 7. q : p ↑ next; 8. ▭ := q; 9. t : q ↑ next; 10. ▭ := p; 11. ▭ := change(t) 12. end 13. end
Theory Explanation. 
Question 53 
Consider a graph whose vertices are points in the plane with integer coordinates (x,y) such that 1≤x≤n and 1≤y≤n, where n≥2 is an integer. Two vertices (x_{1},y_{1}) and (x_{2},y_{2}) are adjacent iff ∣x_{1}−x_{2}∣ ≤ 1 and ∣y_{1}–y_{2}∣ ≤1. The weight of an edge {(x_{1},y_{1}),(x_{2},y_{2})} is √(x_{1}–x_{2})^{2} + (y_{1}–y_{2})^{2}
(a) What is the weight of a minimum weightspanning tree in this graph? Write only the answer without any explanations.
(b) What is the weight of a maximum weightspanning tree in this graph? Write only the answer without any explanations.
Theory Explanation. 
Question 54 
Consider the following program in PseudoPascal syntax.
program what:var z: integer procedure recur(x): begin if x <= 40 then begin x:x+z recur(x); z:=x+10 end end(*recur*) begin(*what*) z=10; recur(z); writeln(z) end
(a) Suppose the parameter to the procedure ‘recur’ is passed by value.
i. What value is printed by program?
ii. How many times is ‘recur’ called?
(b) What value is printed by the program if the parameter is passed by reference?
Theory Explanation. 
Question 55 
Consider the grammar
S → bSe S → PQR P → bPc P → ε Q → cQd Q → ε R → dRe R → ε
where S,P,Q,R are nonterminal symbols with S being the start symbol; b,c,d,e are terminal symbols and ‘ε’ is the empty string. This grammar generates strings of the form b^{i}, c^{j}, d^{k}, e^{m} for some i,j,k,m ≥ 0.
(a) What is the condition on the values of i,j,k,m?
(b) Find the smallest string that has two parse trees.
Theory Explanation. 
Question 56 
Consider a hash table with n buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is 1/n. The hash table is initially empty and K distinct values are inserted in the table.
(a) What is the probability that bucket number 1 is empty after the K^{th} insertion?
(b) What is the probability that no collision has occurred in any of the K insertions?
(c) What is the probability that the first collision occurs at the K^{th} insertions?
Theory Explanation. 
Question 57 
Let F be the set of onetoone functions from the set {1,2,…,n} to the set {1,2,…,m}, where m≥n≥1.
(a) How many functions are members of F?
(b) How many functions f in F satisfy the property f(i) = 1 for some i, 1≤i≤n?
(c) How many functions f in F satisfy the property f(i) < f(j) for all 1≤i≤j≤n?
Theory Explanation. 
Question 58 
Let R be a reflexive and transitive relation on a set A. Define a new relation E on A as
E = {(a,b) ∣ (a,b)∈R and (b,a)∈R}
(a) Prove that E is an equivalence relation on A.
(b) Define a reason ≤ on the equivalence classes of E as E_{1} ≤ E_{2} if ∃a,b such that a∈E_{1}, b∈E_{2} and (a,b)∈R. Prove that ≤ is a partial order.
Theory Explanation. 
Question 59 
Consider the following function.
Function F (n, m: integer): integer; begin If (n <= 0) or (m <= 0) then F:=1 else F:= F(n1, m) + F(n, m1); end;
Use the recurrence relation to answer the following question. Assume that n, m are positive integers. Write only the answers without any explanation.
(a) What is the value of F(n,2)?
(b) What is the value of (n,m)?
(c) How many recursive calls are made to the function F, including the original call, when evaluating F(n,m).
Theory Explanation. 
Question 60 
A sizebalanced binary tree is a binary tree in which for every node, the difference between the number of nodes in the left and right subtree is at most 1. The distance of a node from the root is the length of the path from the root to the node. The height of a binary tree is the maximum distance of a leaf node from the root.
(a) Prove, by using induction on h, that a sizebalance binary tree of height h contains at least 2^{h} nodes.
(b) In a sizebalanced binary tree of height h≤1, how many nodes are at distance h−1 from the root? Write only the answer without any explanations.
Theory Explanation. 
Question 61 
An array A contains n≥1 positive integers in the locations A[1], A[2],... A[n]. The following program fragment prints the length of a shortest sequence of consecutive elements of A, A[i], A[i+1],...A[j] such that the sum of their values is ≥M, a given positive number. It prints ‘n+1’ if no such sequence exists. Complete the program by filling in the boxes. In each case use the simplest possible expression. Write only the line number and the contents of the box.
1. begin 2. i: +1; j:=1; 3. Sum := ▭; 4. min: n; finish:=false; 5. While not finish do 6. If ▭ then 7. if j=n then finish:=true. 8. else 9. begin 10. j:=j+1; 11. sum:=▭ 12. end 13. else 14. begin 15. If(j1) < min then min:=j1; 16. sum:=sum  A[i]; 17. i:=i+1; 18. end 19. writeln (min+1); 20. end.
Theory Explanation. 
Question 62 
Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers.
Node *removeduplicates(Node *head, int *j) { Node *t1, *t2; *j=0; t1 = head; if (t1! = NULL) t2 = t1 →next; else return head; *j = 1; if(t2 == NULL) return head; while t2 != NULL) { if (t1.val != t2.val) → (S1) { (*j)++; t1 → next = t2; t1 = t2: → (S2) } t2 = t2 → next; } t1 → next = NULL; return head; }
Assume the list contains n elements (n≥2) in the following questions.
(a) How many times is the comparison in statement S1 made?
(b) What is the minimum and the maximum number of times statements marked S2 get executed?
(c) What is the significance of the value in the integer pointed to by j when the function completes?
Theory Explanation. 
Question 63 
A B^{+}  tree of order d is a tree in which each internal node has between d and 2d key values. An internal node with M key values has M+1 children. The root (if it is an internal node) has between 1 and 2d key values. The distance of a node from the root is the length of the path from the root to the node. All leaves are at the same distance from the root. The height of the tree is the distance of a leaf from the root.
(a) What is the total number of key values in the internal nodes of a B^{+}  tree with l leaves (l≥2)?
(b) What is the maximum number of internal nodes in a B^{+}  tree of order 4 with 52 leaves?
(c) What is the minimum number of leaves in a B^{+}  tree of order d and height h(h≥1)?
Theory Explanation. 
Question 64 
Construct a finite state machine with minimum number of states, accepting all strings over {a,b} such that the number of a's is divisible by two and the number of b's is divisible by three.
Theory Explanation. 
Question 65 
Given that L is a language accepted by a finite state machine, show that L^{P} and L^{R} are also accepted by some finite state machines, where
L^{P} = {sss' ∈ L, for some string s'}
L^{R} = {ss obtainable by reversing some string in L}
Theory Explanation. 
Question 66 
A language L is a subset of Pascal with the following constructs:
 (a) Expressions involving the operators '+' and '<' only
(b) Assignment statements
(c) 'while' statements and
(d) Compound statements with the syntax 'begin...end'
Give an unambiguous grammar for L.
Theory Explanation. 
Question 67 
The language L, defined by the following grammar allows use of real or integer data in expressions and assignment statements.
(assignstmt):: = (LHS):= (E) (E) :: = (E) + (T)(T) (T) :: = (T) * (V)(V) (V) :: = id((E)) (LHS) :: = id
It is required to convert expression and assignment strings of L into postfix strings that use the typespecific operators (+, i), (+, r), (*, i), (*, r), (:=, i) and (:=,r).
Write a syntax directed translation scheme to convert expression and assignment strings into the postfix form. You may assume that the name and type of a variable can be obtained by making the function calls 'givetype (id)' and 'givename (id)' respectively.
Theory Explanation. 
Question 68 
Consider the following program fragment in Pascal:
Program Main; var X : integer; procedure A: var Y : integer; procedure B: var Z : integer; procedure C: var Z : integer; begin(* Procedure C *) : end(* Procedure C *) begin(*Procedure B*) : C; (* call to C *) A; (* call to A *) : end(*Procedure B*) begin(* Procedure A *) : B; (* call to B *) : end(* Procedure A *) begin (* Main *) : A; (* call to A *) : end(* Main *)
Assume that there are no calls to any procedures other than the ones indicated above. It is known that at some point of time during the execution of this program five activation records exist on the runtime stack. Describe the runtime stack at this point of time by clearly indicating the following: the top of the stack, the contents of the static link and dynamic link, and allocation of the local variables in each record.
Theory Explanation. 
Question 69 
Following is a state table for some finite state machine.
(a) Find the equivalence partition on the states of the machine.
(b) Give the state table for the minimal machine. (Use appropriate names for the equivalent states. For example if states X and Y are equivalent then use XY as the name for the equivalent state in the minimal machine.)
Theory Explanation. 
Question 70 
Let f = (w'+y)(x'+y)(w+x'+z)(w'+z)(x'+z)
(a) Express f as the minimal sum of products. Write only the answer.
(b) If the output line is stuck at 0, for how many input combinations will the value of f be incorrect?
Theory Explanation. 
Question 71 
Following floating point number format is given
f is a fraction represented by a 6bit mantissa (includes sign bit) in sign magnitude form e is a 4bit exponent (includes sign hit) in sign magnitude form n = (f,e) = f, 2^{e} is a floating point number.
Let A = 54.75 in decimal and
B = 9.75 in decimal.
(a) Represent A and B as floating point numbers in the above format.
(b) Show the steps involved in floating point addition of A and B.
(c) What is the percentage error (upto one position beyond decimal point) in the addition operation in (b)?
Theory Explanation. 
Question 72 
A concurrent system consists of 3 processes using a shared resource R in a nonpreemptible and mutually exclusive manner. The processes have unique priorities in the range 1.....3, 3 being the highest priority. It is required to synchronize the processes such that the resource is always allocated to the highest priority requester. The pseudo code for the system is as follows.
Shared Data mutex:semaphore = 1:/* initialized to 1*/ process[3]:semaphore = 0; /*all initialized to 0 */ R_requested [3]:boolean = false; /*all initialized to false */ busy: boolean = false; /*initialized to false */ Code for processes begin process mypriority:integer; mypriority:=____; /*in the range 1...3*/ repeat request_R(mypriority); P (proceed [mypriority]); {use shared resource R} release_R (mypriority); forever end process; Procedures procedure request_R(priority); P(mutex); if busy = true then R_requested [priority]:=true; else begin V(proceed [priority]); busy:=true; end V(mutex);
Give the pseudo code for the procedure release_R.
Theory Explanation. 
Question 73 
A program P reads and processes 1000 consecutive records from a sequential file F stored on device D without using any file system facilities. Given the following
Size of each record = 3200 bytes Access time of D = 10 msecs Data transfer rate of D = 800 × 10^{3} bytes/second CPU time to process each record = 3 msecs
What is the elapsed time of P if
(a) F contains unblocked records and P does not use buffering?
(b) F contains unblocked records and P uses one buffer (i.e., it always reads ahead into the buffer)?
(c) records of F are organized using a blocking factor of 2 (i.e., each block on D contains two records of F) and P uses one buffer?
You may assume that the CPU time needed to transfer a record from a buffer to a local variable of P is negligible.
Theory Explanation. 
Question 74 
An operating system handles requests to resources as follows.
A process (which asks for some resources, uses them for some time and then exits the system) is assigned a unique timestamp are when it starts. The timestamps are monotonically increasing with time. Let us denote the timestamp of a process P by TS(P).
When a process P requests for a resource the OS does the following:
(i) If no other process is currently holding the resource, the OS awards the resource to P.
(ii) If some process Q with TS(Q) < TS(P) is holding the resource, the OS makes P wait for the resources.
(iii) If some process Q with TS(Q) > TS(P) is holding the resource, the OS restarts Q and awards the resources to P.
(Restarting means taking back the resources held by a process, killing it and starting it again with the same timestamp)
When a process releases a resource, the process with the smallest timestamp (if any) amongst those waiting for the resource is awarded the resource.
(a) Can a deadlock ever arise? If yes, show how. If not, prove it.
(b) Can a process P ever starve? If yes, show how. If not, prove it.
Theory Explanation. 
Question 75 
Consider the following relational database schema:
EMP (eno name, age) PROJ (pno name) INVOLVED (eno, pno)
EMP contains information about employees. PROJ about projects and INVOLVED about which employees involved in which projects. The underlined attributes are the primary keys for the respective relations.
(a) What is the relational algebra expression containing one or more of {σ,π,x,u,−} which is equivalent to SQL query.
select eno from EMP, INVOLVED where EMP.eno=INVOLVED.eno and INVOLVED.pno=3
(b) State in English (in not more than 15 words).
What the following relational algebra expressions are designed to determine
(i) π_{eno}(INVOLVED) − π_{eno}((π_{eno}(INVOLVED) X π_{pno}(PROJ))−INVOLVED)
(ii) π_{age}(EMP) − π_{EageE}(EMP) x EMP))
(Note: ρ_{E}(EMP) conceptually makes a copy of EMP and names it K (ρ is called the rename operator))
Theory Explanation. 