Q..No. 1 - 20 Carry One Mark Each 1, Which one of the following in NOT necessarily a property of a Group? (4) Commutativity (@) Asscciativity (©) Existence of inverse for every element (0) Existence of identity 2, Whatis the chromatic number of an n-vertex simple connected graph whjstl\do not contain any odd length cycle? assume n22 (2 @3 (nt ics 3, Which one of the following is TRUE for any simple connecteff'tndiested graph with more than 2 vertices? (A) No two vertices have the same degree. (8) Atleast two vertices have the same degree. (©) At least three vertices have the same degre (0) All vores nave the same dagree ce 4. Consider the binary relation R = {(,¥) p> (2y)} on the set fx,y,2} Which one af the follwing is TRUE? (8) Ris NOT symmetric but an (©) Ris both symmetric and arjeym Metric (0) Bis neither symmetrén, ymmetric 5. (1217)eis equivales (A) 12176. (BD (O28F Die (C) (2297 )10 (D) COB17)s6 6 What is @e minlffum number of gates required to implement the aaolean + fifwe have to use only 2-input NOR gates? «2 4 (o)s any 32k x 1 RAM chips are needed to provide amemory capacity of 256K- (8) 32 lorry (p) 128 A CPU generally handles an interrupt by executing an interrupt service routine (A) As soon as an interrupt is raised (8) By checking the interrupt register at the end of fetch cyde. (©) By checking the interrupt register after finishing the execution of the current instruction (©) By checking the interrupt register at fixed tme intervals.10. aL. az, 13. 14. 15. In which one of the following page replacement policies, Belady’s anomaly may occur? (4) FIFO (8) Optimal (Leu (D) MRU The essential content(s) in each entry of a page table is / are (4) Virtual page number (8) Page frame number (©) Both virtual pege number and page frame number (B) Access right inform ation What is the number af swaps required to sart n elements usi sort, in the werst case? (A) an) (8) en login) (©) 67) An? log n) ° S— asalpsb|ajb; the language generated by @ grammar aver the alphabet {a,b} is the set of (A) All palindrom es (8) All odd length palindromes. (©) Strings that begin end end with thélcamévayfnbol (0) All even length palindrom es Which of the following statéMent(S) is / are correct regarding Beliman-Ford shortest path algorithm? f--) ted cycle, if one exists P. Always finds a ne Q. Finds whether any\hegstivé weighted cyde is reachable fram the scurce (4) P only (8) Q only (©) bothp a &) () Neither P nor Q macan be solved deterministically in polynomial time, then P= NP. a, is NP-hard, then it is NP-complete. (©) mq may be undecidable. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+ 1)"0(0+1)*? (4) The set of all strings containing the substing 00. (8) The set of all strings containing at most two O's (©) The set of all strings containing at least two O's, (0) The set of all strings that begin and end wit either 0 or 116. az. 18. Which one af the following is FALSE? (4) There is unique minimal DFA for every regular language (8) Evary NFA can be converted to an equivalent PDA (©) Com plem ent of every context-free language is recursive. (0) Every nondeterministic PDA can be converted ta an equivalent deterministic PDA. Match all items in Group 1 with correct options fram those given in rot Group 1 Group 2 7 [eau enpressin Ses ena O Q. | Fushcown automata Code generation R. | Dataflow analysis S. | Register allocation Code optim e (A) P-4, Q-1, R-2, S-3 (@) Py S-2 (C) P-3, O-4, RA, SB ©) Consider the program below: # include < stdio.h> int funcint n, int * fp) intt f if(ne=1){ “fo return; Lexical analysis efelele fun (n-1, £9); tt fp. (a8 14 (po) 1s The coupling between different modules of a software is categorized as follows: 1. Content coupling IL, Common coupling IIL, Control coupling Iv Stamp coupling V. Date coupling Coupling between modules can be ranked in the order of strangest (least desirable) ta weakest (most desirable) as follows: (4) -I-IV-V¥(®) W-TV-III-II-1 (C)IAIY Ai-ty (0) ty at20, Cansider the HTML table definition given below: pst Sospan=2> 0 aire

ab
ef	gh
ik

The number of rows in each cclumn and the number of colurnns in (4) {22,3} and (2,9,21 @) (2,2,3} and (2,2, (©) (2.3.2) and (2,32) ©) (2.3.2} im Ey Q. No. 21 - 56 Carry Two Marks 21, An unblanced ce (with & feces, rum bere 0 6) 15. thrown. The probability thatthe face value Is oc le 30SG gf fe rpbsbilty tat the ecw valle is even. The probability of getting any ever face is the same. If the probability that the face is ok it it is greater than 3 is 0.75, which one of the following options is st 2 probability that the face value exceeds 37 (a) 9.459 (0) 0.46 < 0.405 (0) 0.492 22, For the com postion table, group shown below b a r a o cc b a a c d b d c a Which, Ge choices is correct? nerators (8) b, care generators generators (©) d, a are gonerators Ich one of the following is the most appropriate logical formula to represent statement? “Gold and silver ornaments are arecious”, The following notations are used G(x): # 15.2 gold ornament S(x): x is a silver ornam ent Pi): ¥ is procious (4) We (PL) + JA 8()}) @) Ve ((Gix)A5(0)} + P(x) (©) (6 (x) 45(%)) +7 6] ©) ve ([6 (2) ~3(2)} +P(x))24, 25. 26. 27. The binary operation ais defined as follows F a PeQ | | | 5 T T F T | 4} 5 Which one af the following is equivalent ta Pv Q? ) aQP (8) Pood (©) P00 (0) +P wa J (-tan)/(1+tanx)dx evaluates to a (0 @>1 Ome Consider the ‘llowing well-formed ‘a ulae: 1 ave(P (x). ax(P Ge 1 Which of the above are vase (4) [and 1 @)Tand Iv & ’and TIT (D) Nand Iv Given the following state table of ith twa states 4 and B, one input and one output Present Present TT iy Next Next) Output State A State B, Statea | State 8 a o 1 See 0 0 T 0 1 o D 1 0 1 1 1 1 o a 1 initial state is Al B=0, what is the minimum length of an input string ich will take the machine to the state A=0, B=1 with Gutaut=17 (3 @-4 Os (ys Consider a4 stage pipeline processor. The number of cycles needed by the four instructions 11, 12, 13, 14 in stages $1, $2, 3, 54 is shown below: St 32 33 s+ i 2 1 i i 1 1 3 2 2 re} 2 L 1 2 Tf T z z z23. 30. What is the number of cycles needed to execute the fullowing loop? 0.2) {113 12; 18; 143} (8) 23 j28 (p) 30 Consider a 4-way set associative cache (initially empty) with total 16 cache blocks. The main memory consists of 255 blocks and the request for mepmery blacks isin the following order: 0, 255, 1, 4, 3, 8, 193, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155, Which one af the following memory block will NOT be in cache if L adynent policy is used? (3 @)s (c) 129 (D), Consider a system with 4 types of resources Ri (3 ) A (2 units), RBC units), R4 (2 units), & non-preemptive resource allo alicy is used. At any given instance, a request is not entertained if j completely satisfied Three processes P1, P2, P3 request the a5 follows if executed indepencently, Process PL t=0: requests 2 units of R2 tet requests 1 unit of R3 Process Pz races PS: 20: requests 1 unit of Ra requests 2 units of requests 24its o requests 2 units of Ra releases 2 units of RL requests 1 unit of R2 requests 1 unit of RS Finishes 125: releases Lunt of R2 and 1 unit of RL 127: releases dunt of Ra t= requests 2 units t=10: Finishes Which one of ye Javowing statements is TRUE if all three processes run y start at time t=07 al se will finish without any deadlock nd Pz will be in deadlock. nly Pt and P3 will be in a deadlock three processes wil be in deadlock Consider a disk system with 100 cylinders, The requests to access the cylinders occur in following sequence: 4,34, 10, 7, 19, 73,2, 15, 6, 20 Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes ims to move from one cylinder ta adjacent one and shortest seek time first policy is used? (a) 95ms (@) 119ms (©) 233ms (D) 276ms32, In the fallowing process state transition diagram for a uniprocessor systern, assume that there are always same processes in the ready state: Now consider the following statements 1. Ifa process makes a transition 0, it would result in anathelfrccess making transition A immediately o IL, A process Pz in blocked state can make transi ‘wile another process Pr isin running state. III, The 0S uses preemptive scheduling IW, The 0 uses nen-preemptive scheduli Which of the above statements are TRU? (@) Land (8) Land 01 (C) Hand ttt (D) Vandy 33, The enter_cs() end leave process are realized usingg@Bicet void enter_cs(x) { jons to implement critical section of set instruction as follows: wile (testaane PROD); + void leave_cs above solution, X is @ memory location associated with the CS and is fiaNzed to 0. Now cansider the following state ents 1, The above solution ta CS preblem is deadlack-free Il, The solution is starvation tree II, The processes enter CS in FIFO order IV Mare than ane process can enter CS at the same time. Which of the above statements is TRUE? (4) T only @)Tand 0 () Mandir (D) IY only34, A multilevel page table is preferred in comparison to 2 single level page table for translating virtual address ta physical address because (4) Itreduces the memary access time to read or write e memory location (B) It helps to reduce the size of page table needed to implement the virtual address space of a process (©) Itis required by the translation lookaside buffer (0) Ithelps to reduce the number of page faults in page replacement algori 35, The running time of an algorithm is represented by the following UT Be relation: ™ O TO) = Leys erin Which one of the following represents the time complexity of th@tstGoritim? (a) an) (8) an login) (2) 90? (0) (PP leg n) 36, The keys 12, 18, 13, 2, 3, 23, S and 15 are insxted Jhto an initially empty hash table of length 10 using o2en addressing vi ction hk} = k mod 10 and linear probing, What is the resultant hash (ab @ [P @) v o) fe 1 r 1 2f 2 2[_12 2[ 122 af_23 af 13 3 [133,28 4 4[_2 + s/ is 3,3 S| 515 6 [23 6 7 7 7s 7 @ @[_i8 a[_18 a; 18 3 3 o[_is g o a7. WI eximum height of any AVL-tree with 7 nodes? Assume thet the hel tree with a single nade is 0. a 4 (0) 5 Consider the ‘ollowing graph:39. 40. 44. 42. Which one af the following is NOT the sequerce of edges added ta the minimum spanning tree using Kruskal’s algorithm 7 (4) 2) Cf (a,c) (0) (f.9) (ed) @) Ge) @A (0) (9) (b,c) (od) (C) (b.8) (a,c) Cf) Ge) (fg) (e.d) ©) (6,2) (A (b,c) (a,c) (fig) (ord) In quick sort, for sorting n elements, the (n/4)™ smallest element is selected as pivot using an O(n) time algorithm, What is the warst case time complexity quick sort? (4) On) (8) an login) (©) 9m?) (D) 96 n Let L=L,AL2, where Li and Lz are languages as defined belo Li = fz" 6” ca? b™ [m,n so} © «= feb 1ij,k 20} Then Lis (4) Not recursive (8) Regular (©) Context froe but nat rogular (0) Recursively enum erable but no u éts the set of all strings over {0,1} that her@nith O or 1 (@) end with o a (0) contain the substring a0. of the following statements are TRUE? There exist parsing algorithms for some programming languages whose com plesitios ara ass than (n°) TTA programming language which allows recursion can be implementad with static storage allceation TI No L-attributed definition can be evaluated in the framework of bottom-up parsing 1¥ Code improving transformations can be performed at both source lenguage and interm ediste code level (4) Land mt @)landw (@)mtardiy (BL tt andy43. 44, 45. Consider twa transactions 7; and T2, and four schedules 51, S2 $3 S40fT: and T2 as viven below: Tale] [x] Ly] T'Rele]Paly]wely] Si Ri DeRa[*]Ro Ly] mi [x] Ly] M2Ly] S2iRi[R]Ro[¥]Ro[y] i] ] We [vy] ™i[y] Sy:Rilx}™i (JR. [9] [y]Re Ly] We[v] so :Pa[s]e2[y]es[s]™le]oi [y]wely] Which of the above schedules are canflict-serial zable? (A) Sand Se (8) Seand Se (©) Saonly © The following key values ae inserted into a B+ - tree ofr of the internal nodes is 3, and that of the leaf nodes is 2, in the sequitme given below The order of intemal nodes is the maximum numbgs™f traz painters in each node, and the arder of leaf nades is the maximum data items that can be stored in it. The B+ - tee is initially empty. 10,3, 6,8, 4,21 The maximum number of times leaf nodes, split up as a result of these insertions is (a2 (B)3 < C4 (ys Let R and s be relational za = (abe) and S=(c}. Now consider the following queries on the dajaba I pans LOR ©) r(u=v[s]at=v[R-s])}} IL ftl te mes (ravi un. [tl te me ‘above queries are equivalent? (@) Land nr (©) Iandiv (D) U1 and Iv the RSA public key eryptosystem, the private and public keys are (en) and (din) respectively, where n=p%q and p and q are large primes. Besides, n is public and p and q are private, Let M be an integer such that O covre4sponds tp sector num ber: (4) 505035 (8) s0s036 (©) s0s037 (D) 505038 The address of the 1039" sector is53. 54, (#) (0.15,31) (8) (016,30) (©) (0.18,31) (©) (0,27,31) Common Data Questions: 53 & 54 A sub-sequence of a given sequence is just the given sequence with some elements (possibly none ar all) left cut, We are given two sequences X[m] and Yin] of lengths m and n, respectively, with indexes ef X and Y starting from We wish to find the length of the longest commen sub-sequence (LCS: rn and Yin] as (m,n), where an incam plate recursive definition for the furrtgan Mtb) to compute the length of the LCS af ™{m] and ¥[n] is given below If.) =0, if either i=0 or j exprl, ifi,je0 and x[i-t]= ¥[j-1 expra, ifi,je0 and x[i-t]= ¥[}-1 Which one of the following options is correct? (A) expriel(-1,j)+1 ey (C) expr2 =max(I(i-1j), Miint)) a (i-b5-2), 13) The values of I(i,j) could be obtained ic programming based on the correct recursive definition of (i,j) re given above, using an array LIM.NJ, where M= m-#1 and N= Which one of the following st pragramming sclution far the (4) all elem ents L shoul com puted, (8) The vaues of IG order of LCM (©) The value mat be cam puted in either row major arder ar cclumn major orc y (©) Lia.q)needsttetbe computed before L{r,s] if either per or ges. ° that Liiil = ii) ould ba TRUE regarding the dynamic etniien oF IG)? zed to 0 for the values of I(i,j) to be properly afibd computed in a row major order or column major Common Data Questions: 55 & 56 jer the fallowing relational schem a: pliers(sid:integer, sname:string, city:string, strest:sting) Parts(pid:integer, nam e:string, color: string) Catalog(sic: integer, pid:integer, costireal) Consider the following relational query on the above database SELECT S.sname FROM Suppliers S WHERE S.sid NOTIN (SELECT C.sid FROM Catalog ¢ WHERE C.pid NOT (SELECT P.pid FROM Parts P WHERE P.color< > ‘blue!))55. 87. 53. 60. Assume that relations corresponding to the above schema are nat empty, Which one of the following is the correct interpretation of the above query? (4) Find the nam es of all suppliers who have supplied a non-biue part, (8) Find the names of all suppliers who have not supplied a non-blue part (©) Find the names of all suppliers who have supplied only blue parts (0) Find the names of all suppliers who have nct supplied only blue parts: a city has a unique name, and (sname, city) forms a candidate key. functional dependencies are implied other than those implied by candidate keys. Which one of the following is TRUE about the aboy, (4) The schemaisin BCNF (8) The schemais in 3NF but not in BCNF (©) The schemais in 2HF but not in 3NF (D) The schem ais nat in 2NF ° Statement for Linked Answer © ns 57 & 58 (ex link between two hosts. The Ge transmitted into this link to Frames of L000 bits are sent ever a LoPbp: propagation time is 25ms. Framas maximally pack them in transit (wi What is the minimum number sequence numbers distinct! between transmission of (a) |=2 nk), that will be required to represent the e that no time gap needs to be given = @lr4 (pj les Suppose that the 3 dow protocol is used with the sender window size of 2) where | 2 pumber of bits identified in the earlier pert and acknowledgem/ ‘aye Elways piggy backed. After sending 2! frames, what is the minimum time nder will have to wait before starting transmission of the 2 (Identify the closest choice ignaring the frame aracessing time.) ©) 18ms (c) 20ms (0) 22ms tatement for Linked Answer Questions: 59 & 60 siver a binary max-heap im plem ented using an array. ich one of the following array represents @ binary max-heap? (4) {25,12,16,13, 10,8, 14} (@) (25,1413, 16,10,8,19} (C) {25,14,16,13,10,8,12} (©) {25,14,12,13,10,8,16} What is the content of the array after two delete operations an the correct answer to the previous question? (a) (24,1312, 10, 8} (8) (24, 12,13,6,10} (c) {14,19,0,12, 10} (©) {14,13,12,0, 19}