Indian Institute of Technology Madras (IIT-M) 2000 A.M.I.E.T.E Computer Science

(iii) At the end of valuation.
8. Consider the line y = -2-x, where n and m are positive integers.
(a) If mq — np < 0, then is the point (p,q) above the line, beneath the line, or on the line?
(b) Complete the subsequent function, that returns actual if the line segment with endpoints (p,q)
and (r,s) intersects the line y = -2-x, by writing the line number and the content of every box
in your ans book.
1: function clash (m, n, p. q, r, 5: integer): Boolean;
2: start
3: clash = false;
4: if(m*q_n*p) lOthenclash : =true;
5: If(m*s — n * r) I IC then clash : = true;
6: if(m*q_n*p) IOand(m*s_n*r)I IOthenclash:=true;
7: if(m*q_n*p) Ioand(m*s_n*r)I Iothenclash:=true;
8: end;
9. Suppose you are provided arrays p[1 N] and q[1 N] both uninitialized that is, every location
may contain an arbitrary value), and a variable count, initialized to 0. Consider the subsequent
procedures set and iset:
set (i) {
count = count + 1;
q [count] = i;
p[i] = count;
}
is_set(i) {
if (p[i] != 0 or p[i] > count)
return false;
if (q[p[i]] i)
return false;
return true;
}
(a) Suppose we make the subsequent sequence of calls:
set (7); set (3); set(9);
After these quence of calls, what is the value of count, and what do q[1], q[2], q[3], p[7],
p[3] and p[9] contain?
(b) Complete the subsequent statement “The 1st count elements of ________ contain values i
such that set ( ____________) has been called”.
(c) Show that if set (i) has not been called for a few i, then regardless of what p[i] contains,
is_set (i) will return false.
10. A recursive program to calculate Fibonacci numbers is shown beneath. presume you are also
provided an array f[O m] with all elements initialized to 0.
fib(n) {
if (n > M) fault 0;
if ( n==0) return 1;
if(n ==1) return 1;
if(I I) (1)
return I I (2)
t = fib(n — 1) + fib (n — 2);
I I (3)
return t;
}
(a) Fill in the boxes with expressions/statements to make fibQ store and reuse calculated
Fibonacci values. Write the box number and the corresponding contents in your ans book.
(b) What is the time complexity of the resulting program when computing fib(n)?
11. An array contains 4 occurrences of 0, 5 occurrences of 1, and 3 occurre3nces of 2
in any order. The array is to be sorted using swap operations (elements that are swapped
need to be adjacent).
(a) What is the minimum number of swaps needed to sort such an array in the worst case?
(b) provide an ordering of elements in the above array so that the minimum number of swaps
needed to sort the array is maximum.
12. Consider the subsequent program is pseudo-Pascal syntax.
program main;
varx: integer;
procedure Q [z:integer);
begin
z: z + x;
writel n (z)
end;
procedure P (y:integer);
varx: integer;
begin
x: y + 2;
writeln(x)
end;
begin
x:=5;
P(x);
writeln(x)
end.
What is the output of the program, when
(a) The parameter passing mechanism is call-by-value and the scope rule is static scooping?
(b) The parameter passing mechanism is call-by-reference and the scope rule is dynamic
scooping?
13. Consider the syntax directed translation scheme (SDTS) provided in the subsequent. presume
attribute valuation with bottom-up parsing, i.e., attributes are evaluated immediately after a
reduction.
E - E1 * T {E.val = E1. val * T. val}
E-T{E.val =T.val}
T - F - T1 {T.val = F. val - T1. val}
T-F{T.val=F.val}
F - two {F. val =2}
F - four {F. val =4}
(a) Using this SDTS, construct a parse tree for the expression
4_2_4*2
and also calculate its E.val.
(b) It is needed to calculate the total number of reductions performed to parse a provided input.
Using synthesized attributes only, replace the SDTS given, without changing the grammar, to
obtain E.red, the number of reductions performed while reducing an input to E.
14. (a) Fill in the boxes beneath to get a solution for the readers-writers problem, using a single
binary semphore, mutex (initialized to 1) and busy waiting. Write the box numbers (1,2 and
3), and their contents in your ans book.
mt R = 0, W = 0;
learner ( ) {
Li: wait (mutex);
If (W ==0) {
R = R +1;
I I (1)
}
else {
I I (2)
goto Li;
}
./* do the learn */
wait (mutex)
R = R -
signal (mutex);
}
author () {
L2: wait(mutex);
If(I I) { (3)
signal (mutex);
goto L2;
}
W=i;
signal (mutex);
/*do the write*/
wa it( m utex)
W = 0;
signal (mutex);
(b) Can the above solution lead to starvation of writers?
15. (a) Suppose you are provided an empty B+-tree where every node (leaf and internal) can
store up to five key values. Suppose values i,2, iO are inserted, in order, into the tree, Show the
tree pictorially
(i) After six insertions, and
(ii) After all iO insertions
Do NOT show intermediate stages.
(b) Suppose instead of splitting a node when it is full, we try to move a value to the left
sibling. If there is no left sibling, or the left sibling is full, we split the node. Show the tree
after values, i, 2, , nine have been inserted. Assume, as in (a) that every node can hold up to 5
keys.
(c) In general, suppose a B+-tree node can hold a maximum of m keys, and you insert a long
sequence of keys in increasing order. Then what approximately is the avg. number of keys
in every leaf level node.
(i) In the normal case, and
(ii) With the insertion as in (b).
16. Consider a bank database with only 1 relation
transaction (transno, acctno, date, amount)
The amount attribute value is positive for deposits and negative for withdrawals.
(a) describe an SQL view TP containing the info.
(acctno, Ti.date, T2.amount)
for every pair of transactions Ti, T2 such that Ti and T2 are transaction on the identical account
and the date of T2 is the date of Ti.
(b) Using only the above view TP, write a query to obtain for every account the minimum balance
it ever reached (not including the 0 balance when the account is created). presume there is at
most 1 transaction per day on every account, and every account has had atleast one
transaction since it was created. To simply your query, break it up into two steps by defining an
intermediate view V.

Earning:   Approval pending.