Jawaharlal Nehru Technological University Hyderabad 2002 B.Tech Computer Science and Engineering gate - Question Paper

learner relation provide the student‘s roll number, name and the degree program
for which the learner is registered in the university. The INTERVIEW relation
provide the date on which a students is interviewed by a company. The OFFER
relation provide the salary offered to a learner who is successful in a company‘s
interview. The key for every relation is indicated by the underlined attributes.
s
p
-
(a) Write relational algebra expressions (using only the operator ,
,
,
,
)
for the subsequent queries:
(i) List the rollnumbers and names of those students who attended at lowest one
any
interview but did not receive
job offer.
(ii) List the rollnumbers and names of students who went for interviews and
every
received job offers from
company with which they interviewed.
(b) Write an SQL query to list, for every degree program in which more than five
students were offered jobs, the name of the degree and the avg. offered
salary of students in this degree program.
16. For relation R = (L, M, N , O, P), the subsequent dependencies hold:
M ‰ O NO ‰ P P ‰ L and L ‰ MN
R is decomposed into R
=(L, M, N , P) and R
= (M, O).
1
2
(a) Is the above decomposition a lossless-join decomposition? discuss.
(b) Is the above decomposition dependency-preserving? If not, list all the
dependencies that are not preserved.
(c) What is the highest normal form satisfied by the above decomposition?
+
17. (a) The subsequent table refers to search times for a key in B-trees and B
-trees.
B-tree B
-tree
+
Successful Search Unsuccessful search Successful Search Unsuccessful search
X
X
X
X
1
2
3
4
successful
A
search means that the key exists in the database and
unsuccessful
means that it is not current in the database. every of the entries
Constant
Variable
Constant
X
, X
, X
and X
can have a value of either
or
.
1
2
3
4
means that the search time is the same, independent of the specific key
Variable
value, where
means that it is dependent on the specific key value
chosen for the search.
provide the accurate values for the entries X
, X
, X
and X
(for example X
=
1
2
3
4
1
Constant, X
= Constant, X
= Constant, X
= Constant).
2
3
4
Join All India M ock G AT E Classroom T est Series - 2006 conducted by GATE Forum in over 25 cities all over India. ques.
Papers including part tests and full tests are designed by Iisc alum ni according to the recent syllabus. Percentile, All India Rank,
interaction with Iisc alum ni in our online discussion forum s, and m ore. Registration begins 10
M ay, 2005. For m ore details,
th
visit
www
.
gateforum
.
com
Think GATE Think G ATE Forum

GATE CS - 2002 GATE Forum www.gateforum .com
Join discussion of this test paper at http://forum .gatem entor.com
R(A,B)
(b) Relation
has the subsequent view described on it:
CREATE VIEW V AS
(SELECT R1.A,R2.B
FROM R AS R1, R AS R2
WHERE R1.B=R2.A)
(i) The current contents of relation R are shown beneath. elaborate the contents of
the view V?
A B
1 2
2 3
2 4
4 5
6 7
6 8
9 10
additional
(ii) The tuples (2,11) and (11,6) are now inserted into R. elaborate the
tupels that are inserted in V?
18. (a) Draw the process state transition diagram of an OS in which (i) every process
is in 1 of the 5 states: created, ready, running, blocked (i.e. sleep or
wait), or terminated, and (ii) only non-preemptive scheduling is used by the
OS. tag the transitions appropriately.
(b) The functionality of atomic TEST-AND-SET assembly language instruction is
provided by the subsequent C function.
int TEST-AND-SET (int *x)
{
int y;
A1:y=*x;
A2:*x=1;
A3:return y;
}
(i) Complete the subsequent C functions for implementing code for entering and
leaving critical parts based on the above TEST-AND-SET instruction.
int mutex=0;
void enter-cs()
{
while (…………………………………);
}
Join All India M ock G AT E Classroom T est Series - 2006 conducted by GATE Forum in over 25 cities all over India. ques.
Papers including part tests and full tests are designed by Iisc alum ni according to the recent syllabus. Percentile, All India Rank,
interaction with Iisc alum ni in our online discussion forum s, and m ore. Registration begins 10
M ay, 2005. For m ore details,
th
visit
www
.
gateforum
.
com
Think GATE Think G ATE Forum

GATE CS - 2002 GATE Forum www.gateforum .com
Join discussion of this test paper at http://forum .gatem entor.com
void leave-cs()
{
…………………………………..;
}
(ii) Is the above solution to the critical part issue deadlock free and
starvation-free?
(iii) For the above solution, show by an example that mutual exclusion is not
ensured if TEST-AND-SET instruction is not atomic.
19. A computer system uses 32-bit virtual address, and 32-bit physical address. The
physical memory is byte addressable, and the page size is four kbytes. It is decided
to use 2 level page tables to translate from virtual address to physical address.
Equal number of bits should be used for indexing 1st level and 2nd level page
table, and the size of every page table entry is four bytes.
(a) provide a diagram showing how a virtual address would be translated to a
physical address.
(b) What is the number of page table entries that can be contained in every
page?
(c) How many bits are available for storing protection and other info in
every page table entry?
20. The subsequent solution to the single producer single consumer issue uses
semaphores for synchronization.
#define BUFFSIZE 100
buffer buf[BUFFSIZE];
int first=last=0;
semaphore b_full=0;
semaphore b_empty=BUFFSIZE;
void producer()
{
while (1) {
produce an item;
p1: …………………..;
put the item into buff (first);
first=(first+1)%BUFFSIZE;
p2: …………………..;
}
}
void consumer()
{

gateforum
.

GATE CS - 2002 GATE Forum www.gateforum .com
Join discussion of this test paper at http://forum .gatem entor.com
while (1) {
c1:……………………..
take the item from buf[last];
last=(last+1)%BUFFSIZE;
c2: ……………………..;
consume the item;
}
}
(a) Complete the dotted part of the above solution.
(b) Using a different semaphore variable, insert 1 line statement every
immediately after p1, immediately before p2, immediately after c1, and
immediately before c2 so that the program works correctly for multiple
procedures and consumers.
21. We require a 4 state automaton to recognize the regular expression
( )
ab abb
* .
(a) provide an NFA for this purpose.
(b) provide a DFA for this purpose.
22. (a) Construct all the parse trees corresponding to i + j * k for the grammar
E ‰ E+E
E ‰ E*E
E ‰ id
(b) In this grammar, what is the precedence of the 2 operators * and +?
(c) If only 1 parse tree is desired for any string in the identical language, what
modifications are to be made so that the resulting LALR(1) grammar is non-
ambiguous?

Earning:   Approval pending.