Entrance Examination (June 2011)
PhD in Computer Science

TinlC: 2 Hours Max. Marks: 75
Hall Ticket Number:


INSTRUCTIONS

1.
Vritc your Hall Ticket Numher in tIll' hox abovp. AND on tho nI1.'iwer sc:ript.

2.
This question paper collsi," of t!iO parts: PART A and PAin II. DOTU PARTS ARE COJ-IPULSORY. Plea;c writ" answers for IUUllipk'choicc qursliom' of PART A ill th" tahJe> provided on 2 of till" QuC'Stion puper um} the Qucstions in PABT D ronsl unswrcd on the 8C"ript.

3.
This test. i,.. for 2 houl1l duration carrying 75 marks. There is a negative n18rking of 0.33 mark for CVfJr) wrong answer in PAltT A.

4.
questions in order.


.3, Give prccL"ic WJsWCfti and write dearly.
6.
Do all the' rough work only on In...' page of the anSW('f scnpt, nowhere eire. Lahel the page 'Rough Work'.

7.
of non-programmable calculator lUlel Jng-tahlffi is allowed.

8.
Submit both the qUE"St.ion paper lUlCI sc:ripllo the invigilntor before leaving the exfUIlinntion bn.ll.


I

PART
40 OBJECTIVE TYPE QUESTIONS OF ONE MARl< EACH
'Question No. I Answer Question NO] Answer I I I 21 II 22 C-I I 3 IL 23
4J [24 II
I 5T 25I
26
I 7 I 27 II
I 8T 28I OJ
L 9. 2!1
1O-J L 33 I
C "14 .IL34 I I

1-12 r 36 I"·I
7L J

L 18 I I
JII 4DI I
u .u
2


1. Heap sort algorithm is the same as which of the following algorithms, except for the fact that it uses the heap data structure
A. Bubble Sort
B. Shell Sort
C. Merge Sort
D. S<'!cction Sort
2. Consider the graph G given below:

graph G is
A. Hamiltonian and Euclidean
B. Euclidean but not Hamiltonian
C. Hamiltonian hut not Euclidean
D. Neither Hamiltonian nor Euclidean
3. Which of the following is in eorr""t LEXICOGRAPHIC order when using ASCII code?
A. an, OR, AND
B. 15, 125
C. AND, OR, 8n
D. 15, 125, 5
4. Thenumberoftimesthestatement"x=x+1"isexecutedin thefollowing program fragment using e notation in terms of n is
3









A.
B. 6(logll)
C. 8(112)
D. 8(nlogn)
5. A liHt of illtt'gef' is almost sorted with only the largest number being out of pllU·C'. If this information is not known to the algorithm, then of thl! following all.l0rithms can sort t.hl! list the fastest?
A. Buhble Sort
B. Selection sort
C. Iusertion Sort
D. Shl'll Sort.
6. The Depth First and Brl'lldth First Traversal visit the nodes in exactly tI", slllue order in which of the following type of
A. Binary Tn'C
B. Linear Chain
C. Complete Graph
D. None of thl' ubo"e
7. TI,,· postfix expression is equivalent to whieh of the fol­lowing prefix expression'!
A. *j*A+BCDE
B. j*A+J3C*DE
C.
D.
8. Algorithm for finding strongly l'onncctl'd compOllents in linenr time makes use of
A. DFS
B. llFS
C. Shortest Path
D. None of the
9. Vhat is the vnlnc uf C lanp;ndgc l'xprNlsion
A. n2+n-1

B. n"

C.
D. n2
10. Which of the following rcs11lt.s in thl' ma'dmum valuc iftheir dcclnratioiIs ar.. int x double z 10.0; char c faJ·• (ASS11111" the ASCIl of is 97)
A.
B.
C.
D.
11. Considcr the following function:
double power(double base, unsigned int exponent) if (exponent return 1.0; else if (even(exponent» return power(base*base, exponent/2);
else return pover(base*base. exponent/2)*base;
How many multiplications arc executed as a result of the cnll power(5.0, (Do not inc'lude divisions in this total)
A.
B. 8
C.
D. 12
12. Consider the followin!!; prop;rnm scp;ment:
k
vh11e

if (odd{k»

Z
X
k


Wht'll loop t('fJnilllltf'S. which of the following he true?
A. x-btl
B. z b"
C. h Z"
D. X"
13. the following
#include <stdio.h>
mainO


float sum 0.0, j=1.0. i=2.0;
while 0.001)



sum=sum+i/j;
printf(n%f



When this eoue is ex('Cut..d, whkh of the followinl; intel;ers bC'st. approx­imates the last nmnhC'1" that is printeu'!
A. 0
B. 1
C. 2
D. 3
Thrashin! problem in operut,ing systC'ms cun not solved hy

Incrl'asing t.he of ulIlltiprogrllmminl;


hlereasinl; the spC'Cd of the processor


Dccrcasinl; the del;l"ec of multiprogramming


Increasing the JIl('mory

A.
and

B.
aud

C.
lind

D.
and


15. In operating syst..ms when does multi-level feedback sdlL'duling become
A. When the time for migration is infinit.e
B. When the priority is same for all proee;;"CS
C. Vhen time slice is same
D. Quantum of time needed by each process is same
16. Consider a reference sequence rio r2, ra,..., rn with a FIFO page replllrc­ment algorithm and that gives page faults with; page frames allott.ed. When the number of page frames is then for Kj and Kj which of tbe following is always true TRUE when i
7
A. K; Kj
B. K; K j
C. K i J(j
D. None of the above
17. If Il system has 1GB RAM with a page size of 8KB and the operating system occupies 16 MB of how many page frames docs the system hllve for user processes?
A. 129024
B. 1209211
C. 1:3H172
D. 119864
18. III datahasl'S, spurious Ullly occur due to Barl 1I(.rmnlization

Tht'ta joius
Updatiup; tables from joins other than theta joins


A.
Duly

B.
alld

C.
alld

D.
and ouly


19. Iu eontl'xt of dlltahas<'S, entity integrity constraint states that
A. key mlue ClU' not be NULL
B. Foreigu key yaille cau not be NULL
C. Every relat iou has at one superkey
D. SlIperkey of smaU"st size should chosen as primary key
Suppose' there is an OPl'u(l'xtemal) hash table with four bUl'kets, lIum­bered 3. Suppose iut egers are ha..hed into these buckets lL.ing hash functiou r mod 4. If the se<jue'nee of perfect squares 9,...,P.... is hashed iuto the tllble, then as the total nnmber of entries in the table' grmvs, whllt will happen?
A. All buckets will receive approximately the same number of entries
B. All entries will go into one particular bucket
C. Three of the buckets will cadi approximately one-third of the entries, and the fourth bucket will remain empty
D. Two of the buckets will lIpt approxilllllt.eIy half the and thc other two will remain almost empty
21. The truth table for V A is S!lIlle as truth table for
A. (pVq) A
B. (pVq) Ar
C. (pVq)A(pAr)
D. pVq
22. The Ilumb('r of distiuct reguhu binary tre", that be ('onstructed with 7 nodes uamed lIS a. b. c. d. e. f. g is
A.
B. 1120

C
•
D. None of the abo"e
23. The boolean function that is equivalent to the boolean functiou V is
A. q
B. r
C. pAr
D. pVq
24. In odal, the twelve-bit two's complement of the hcxadeciulll.l number 2AF'16 is
A. 65228
B. 62518
C. 65218
9
D. 65128
25. What is the radix of the numbers if the solution to the quadratic equation x2 -IOx +31 0 is x 5 and x
A. IO
B. 11
C. 13
D. NOlie of the above
26. A 36-bil. f1oating-poillt billllIy 1I11111ber has eight hits plus sign bit for the expOJll'lIt alld 26 hits pins sign bit for the mantissa. The mantissa is a nonnaliz('d fraction. Numbers in the mantissa and exponent arc in signed magnit uell' representation. The largest nnel sllIallest positive quail! 1hnt call reprL.,;entl'd I'xdllding zero are
A. (2 2ti) x 2 ·21jG
2 12r•fi

B. :l-2r.G
C. (l x 2+2t"lfi. 2 25!i
D. of abov,'
27. Usillg Karullu!h IlIlIp. four vllriubl(' booll'lm funetion 11, 13,1·1. Ifi) simplified to
A. CD
B. BCD of ABC +ABD
C. AJ3("D+ABC+CD
D. of I h"
Ll'I 1(1 11'0 and t be three regular expressions corn,gpol(ling to regular sets Sand then which olle of the following is TRUE?
A. Se R
B. Re S
C. Te S
D. of the aboye 29. Which of the following is FALSE about Context FrN.'

Context Free Lnnguages ar" closed under intersection.


Context Free Languages are closed under concat·l'llulion.


Context Free Lnnguagcs arc c1oSl'd tmder Kleenl"s closure.

A.
only

B.
only

C.
and only

D.
and onl.·


30. Which of the following b lIndecidable

Dl'tl'rminution of ulllbiguit. pf context frec granlmars.


Given two cont('xt grllllInars G1 and G2 detl'nnilling they generat" ('xuetly thl' language.


Detl'l'll,iniug thl' language accepted by II Turiug mllclline is fmite or infinitl'.

A.
only

B.
and onl.v

C.
and only

D.
aud


31. Consider the following whel'll >.. deJlotcs the null string S IlSb 8 bSa S SS S >.. Which of the followiug best characteri:tes the language generated h.v the above graIIlInllI?
A. All strings of the form aibiak where j k
B. All palindromes over a and b
C. All strings with equal nllluher of and
D. All even-leugth strings of /LillI
32. In computer networking, an Internet socket or network socket is an end­point. of a bidirectional inter-process communication flow across an In­ternet Protocol-based computer network. A socket address combines which of the following?
A. A http URL and an IP address
B. An IP address and a port number
C. An IP address and a proxy address
D. An IP and a PID (process identifier)
Questions -34 arl' based on the following:
In a Oistaucl' VC<'tor routing algorithm each node x maintains

n. distance "cctor n.c whcre costs of paths from node x to any othpr node 11 in the network with nodes are estimated. Each node then updutm its OV IJnsed on t.he OV update frOIn its neighbor vas: nodI' 11 in N
:l3. CClJIsidl'r t.he case when aftc'r an updllt'l does not change, then it impliffi that.
A. ulglll'1tluu is unstablc'
B. a pn.th t hun Il c'stimllte is found
C. t.hl' algorithm converged
D. therl' is np,'c>ssarily a count to infinity problem
Consider case aeLer an update Dx has dJanged, then which of the following

The Upd,ltl' hplps to find a least-cost path froIU node x to 11.


TIIC' updatt' nce·ds to be communicated to neighbours in an asyn­dmmolls fashion.


There is nl'Ccssarily a C'ollnt to infinity problem


A.
B. UIld only
C. only
D. and only
35. A router software had a bug that set TTL field values to NULL whell forwarding IP packets. irrespective of the actual TTL value. How many hops further will these IP packets be forwarded
A. 0
B. 1
C. infinity times since TTL is NULL
D. TTL field dors not rrally mattrr for this
36. Consider the queuing dt'lay in a !"uter buffer(prcceding nn outbound link). Suppose all packets a.re L bits, the transmission rate is R bps and that N packets ",rriYe buffer pvery If: seconds. The average queuing delay of II packt is
A.
I.
B
2
C.

D
• 2
37. UDP checksum for two 16 bit numbers: 11100110011001 10,1101010101010101 is
A. 0100010001000011
B. 1011101110111100
C. 0011010111110100
D. 1011101110111111
After rearling the following passage carefully, lUlswcr questions 38 -40 on the basis of what is stated or implied in the passage.
There was a table set out under a tree in front of the house, and the March Hare and the Hatter were having tea at it: a Dormouse was sit­ting between them, faBt asleep, and the other two were IJ..9ing it as a cushion, resting their elbows on it, and talking Oller its head. "Very uncomfortable for the D017T1ouse," thought Alice; "only as it asleep, I suppose it doesn't mind."
The table was a large one, but the three were all crowded together at one ramer oJ It. "No room! No room!" they cried out when they saw Alir.e cnrning. "There's plenty oJ room!" said Alir.e indignantly, and she sat down in a large ann-chair at one end oJ the table.
38. Who were "the three" sitting at one corner of the table?
A. Alice, l'!areh Hare and the Hatter
B. Mareh thC' Hatter and the Dormouse
•
C. March Hare, Dormousc and Alice
D. the Hatter and Alice
39. Aeeording to AIicC', which of Ihe following is TRUE?
A. Thew's no room at the table
B. Dormousc is talking in its slrep
C. You don't fCC'1 uneomfortable sleeping at a table
D. Yon 1lI1cOlnfortabl,' only if you are awake
·10. Which of the following is TIWE from the above passage?
A. Uare!l Hare. I,he lIaU,-r LUlll till' DorlllOlL,e wanted Alice to join thcm at the table
B. Illlreh Hare and the Hat""r an-sitting next to one another
C. There llre only thrL'e chairs at 1he table
D. TherC' are only three chairs at one end of the table.
PART SHORT ANSWER QUESTIONS (35 Marks) Answer any SEVEN Questions. Each carries FIVE Marks.
1. A digital computer has a common bus sYstem for 16 registers of 32 bits each. The bus is constructed with multiple.xcrs.

How many selection inputs are there in each multiplpxer?


What size of multiplexPIb arp


How many multipll'xers arp in thp bus?


2. The lU'.cess time of II cache· lll"U'OI1' is lOOns and that of main memory is It is estimatl'd that 8U% of the memory rcqupsts me for read lUld the remaining for writ.e. Thl' hit ratio for read accesses only is
0.9. A write-through procedure is used.

What is average time of the ronsidering only mem­ory rf'ad


What is the averagc access timl' of the system considering both the


read and write rf'Cjuests? (el What is the hit ratio taking int.o consideration t.he write
The size of a file is in a file system that uses 2KB os the block size, How many index blocks nrc nc'Cded to store this file in indcxed allocation? Assuming the inode structure, how nnlJlY levels of indexing is ncccled? How many disk blocks, othf'r than the inode, need to be read to access the 300'" block?
Design Push Down Automaton for the language consisting of all words of the fonn anbmambn, where 1L 0 over the alphabet E b}. Also provide a context frc'C grammar that this language,
Show that the following grammar is ambiguous, where A is the start symbol and A is null string:
A bBaAC





6.
Prove for 0

7.
Suppose the delete-min algorithm for a min-heap is carried out as follows: Delete the root and adjust the heap by moving up the minimum of its ehild nodes. Continue this operation recursively. DOL'S this algorithm work? Explain.

8.
an algorithm to find a maximum cost spanning tree, Lc., the span­ning tree with highest possible cost. Suppose the edges are sorted ac­cording to non-im'reasing order of their costs and ,-tored in a list. If there nn. n nod(·s in the input graph then will the first n-1 edges of this list always he part of the maximum tree? Justify your answer.

9.
Suppose that G is a connected planar graph with less than 12 regions and SUdl that p.IIch vI,rtex of G degree 3. Then prove that G hIlS n n'gion of 4.

10.
Consider thp f611mving relation STUDY and functional dependencies Fl. F2, F3, F4 nnd F5.




Relation
STUDY [Slid. Namp, Birthdotp, COllrsecode, Title, Credits, Dept, Dnal1le,
Location, Senu·sll'r. Grade]
Functional Dependencies
FI; {Stid} {Name. llirlhdate}
F2: {Courst'l:odc} {Title. Credits, Dept}
F3: {Depl} {Dnmne. Location}
F4: {Stid, {Spmeslcr, Marks, Grade}
F5: {lIarks} {Grade}


Find all candidatp keys for relation STUDY.


What is the highc,;t norlllal form of relation STUDY? Dccompose STUDY (if required) into BCNF. For each decompo­sition you make. identify the normal form of the original and the


result.ing relations? Give brief jnstification for each normalization step.
11.
In C language, bow do you dL'Clnre and define tVo dimE'nsionnl arrny D of integers with r rows and c columns dynamically In C language, a two dimensional array !If with 4 rows and 6 columns lllay be dcclured lIS a formal parameter to function as .AI[ but not as JIJ Why?

12.
A machine uses /l 16-bit two's ('omplrlllent reprcsentation for integers, and little-endian byte-ordermg, tlris meuns that the lenst significuut bytl' of an integer is stor",1 at the lowE'r address. Dctl'rnlin" what following program fragment will print:


int 16 signed integer
char (char
x Ox0013;
printf("x is
printf(";'d