C_questions

shortestdistanceandthepathtoalltheremainingvertices. (16) Ans: Thesourcevertexis2(given). Step1 T={1,2,3,4,5,6} P=Q L(2)=0 StartingVertex L(x)=∞ forallxЄT,x≠2 Step2 V=2 (vertex2hassmallestlabel) P={2}T={1,3,4,5,6} CalculatenewlabelsforallverticesofT. L(1)=min(∞,0+3)=3 L(3)=min(∞,0+4)=4 L(4)=min(∞,0+∞)=∞ L(5)=∞ L(6)=∞ Step3 V=1 (PermanentlabelL(1)=3) P={2,1} T={3,4,5,6} CalculatenewlabelsforallverticesofT. L(3)=min(4,3+∞)=4 L(4)=min(∞,3+7)=10 L(5)=min(∞,3+∞)=∞ L(6)=min(∞.3+2)=5 Step4 V=3 (PermanentlabelL(3)=4) P={2,1,3} T={4,5,6} CalculatenewlabelsforallverticesofT. L(4)=min(10,4+∞)=10 L(5)=min(∞,4+6)=10 L(6)=min(5.4+∞)=5 Step5

V=6 (PermanentlabelL(6)=5) P={2,1,3,6} T={4,5} CalculatenewlabelsforallverticesofT. L(4)=min(10,5+3)=8 L(5)=min(10,5+∞)=10 Step6 V=4 (PermanentlabelL(4)=8) P={2,1,3,6,4} T={5} CalculatenewlabelsforallverticesofT. L(5)=min(10,8+1)=9 Thevertex 5 gotits permanentlabeland allthe vertices gottheir respectivepermanentlabelsasshowninthetablebelow. Vertex Perma (v) nent 1 LabelL 3 (v) 4 3 5 4 6 8 9 5 Now,assumingthesourcevertextobe2,theshortestdistanceandthepathto allremainingverticesareasfollows:- Vertex1 Shortestdistance=3 Pathis21 Vertex3 Shortestdistance=4 Pathis23 Vertex4 Shortestdistance=8 Pathis2164 Vertex5 Shortestdistance=9 Pathis21645 Vertex6 Shortestdistance=5 Pathis216 Q.246 Twostacksareimplementedusinganarray.Whatshouldbetheinitialvaluesof topforthetwostacks?Arrowsshowthedirectionofgrowthofthestack. ArrayA S1 S2 How canweimplementm stacksinacontiguousamemory.Explainhow the stacks willgrow andindicate the boundary condition.Write push and pop programsforsuchascenario. (10)

Ans: Twostackss1ands2canbeimplementedinonearrayA[1,2...N]asshowninthe followingfigure 1 2 3 4 n-3 n-2 n-1 n S1 S1S2 WedefineA[1]asthebottom ofstackS1andletS1“grow”totherightandwedefine A[n]asthebottom ofthestackS2andS2“grow”totheleft.Inthiscase,overflowwill occuronlyS1andS2togetherhavemorethannelements.Thistechniquewillusually decreasethenumberoftimesoverflowoccurs.Therewillseparatepush1,push2,pop1 andpop2functionstobedefinedseparatelyfortwostacksS1andS2.Thesewillbe definedasfollows:- initialvolumeoftopfor stackS1istop1=0and forstackS2istop2=n+1 S1.Push1(x) { if(top1+1==top2) printif(“StackS1isoverflowing”) Else { top1++ A[top1]=x } } S1.POP() { if(top1==0) printif(“stackS1isempty”) return(-1) } return(A[top--]) } S2.push2(x) } if(top1+1==top2) printif(“S2isoverflowing”) else { top2— A[top2]=x } } S2.POP2()

{ if(top2==n+1) } printif(“stackisempty”) return(-1) } else return(A[top2++]) } Q.247 Howcanwemodifyalmostanyalgorithm tohaveagoodbestcaserunningtime? (4) Ans: Guessananswer Verifythatitiscorrect,inthatcasestop. Otherwiseruntheoriginalalgorithm. OR Checkwhethertheinputconstitutesaninputattheverybeginning Otherwiseruntheoriginalalgorithm. Q.248 Sketchanalgorithm tofindtheminimum andthemaximum elementsfrom a sequenceofnelements.Youralgorithm shouldnottakemorethan (3n/2)-2 numberofcomparisonswherenisapowerof2. (6) Ans: Ratherthan processing each elementoftheinputbycomparing itagainstthe correctminimum andmaximum,atthecostof2comparisonsperelement,we processelementsinpairs.Wecomparepairsofelementsfrom theinputfirstwith eachother,andthenwecomparethesmallertothecurrentminimum andthelarger tothecurrentmaximum,atthecostof3comparisonsforevery3elements. Ifnisoff,wesetboththeminimum andmaximum tothevalueoffirstelementand theprocesstherestoftheelementsinpairs. Ifniseven,weperform 1comparisononthefirst2elementstodeterminetheinitial valuesofminimum andmaximum,andtheprocesstherestoftheelementsin pairs.Soifnisodd,weperform 3[n/2]comparisons. Ifniseven,weperform oneinitialcomparisonfollowedby3(n-2)/2comparisonsfor atotalof3n/2-2.Thusineither,numberofcomparisonsarealmost3[n/2] Q.249 WriteanO(1)algorithm todeleteanodepinasinglylinkedlist.Canweuse thisalgorithm todeleteeverynode?Justify. (7) Ans:

Onedeletionoperationconsistsindeletinganodeatthebeginningofthelistand returningthevaluestoredinit.Thisoperationisimplementedbyamemberfunction deleteFromHead()givenbelow.Inthisoperation,theinformationfrom thefirstnode istemporarilystoredinlocalvariableandthenheadisresetsothatwhatwasthe secondnodebecomesthefirstnode.Inthisway,theformerfirstnodecanbe deletedinconstantO(1)time. Deletingthefirstnode,from alinkedlistpointedby‘head’canbedoneisO(i)time head=headnext DeletinganotethatfollowsanodewithaddressPcanalsobedoneinO(i)time Pnext=(Pnext)next ButanodewithaddressPcannotbedeletedinO(i)time.Ittakeslineartime. //Deletethefirstnode deleteFromHead(structnode*q,intnum) { structnode*temp; temp=*q; *q=templink; free(temp); } Wecanusethisalgorithm todeleteeverynodebycallingitrecursively.Thebestcase iswhentheheadnodeistobedeleted,whichtakesO(1)timetoaccomplish.The worstcaseiswhenthelastnodeneedstobedeletedbecauseinthatcaseitwilltake O(n)performance. Q.250 Suggestanefficientsortingalgorithm to sortanarrayofnlargerecords,whileminimizingnumberofexchanges. (2) Ans: Selectionsort In allcases:n­2/2comparisons and n exchanges execution time is not sensitivetooriginalorderingofInputdata.

     HeadK SupposeKisthenodeafterwhichthelististobesplit.Then head2=kfront kfront=head headback=k P=head2 while(Pfront:=head) P=Pfront Pfront=head2 head2back=P Q.251 GiveanAVLtreeforwhichthedeletionofanoderequirestwodoublerotations. Drawthetreeandexplainwhytworotationsareneeded? (10) Ans:

Q.252 Afunnytreeisabinarytreesuchthat,foreachofitsnodesx,thenumberof nodesineachsubtreeofxisatmost2/3thenumberofnodesinthetree rootedatx.Drawthetallestfunnytreeof5nodes. (7) Ans: Q.253 Explaintheterm step-wiserefinement. (3) Ans: StepWiseRefinement Refinementisa processofelaboration.Hereone beginswith a statementof functionthatisdefinedatahigh-levelabstraction.Thatisthestatementdescribes the program/function conceptuallybutprovides no information aboutinternal working.Refinementcausestheprogrammertoelaborateontheoriginalstatement providing more and moredetail.In a stepwise refinement,ateach step of refinementoneorseveralinstructionsofthegivenprogram aredecomposedinto moredetailedinstructions.Thesuccessiverefinementterminateswhen allthe instructionsareexpressedintermsofatomicexpressionsofthelanguage. Q.254 Whatisthedifferencebetweentop-downandbottom-up,programming? (4) Ans:Top-downandBottom-upApproaches InTop-downprogrammingapproach,westartbyidentifyingthemajormodulesof theprogram,decomposingthem intotheirlowermodulesanditeratinguntilthe desiredlevelofdetailisachieved.ThisisalsotermedasStepWiseRefinement; startingfrom anabstractdesign,ineachstepthedesignisrefinedto amore concreteleveluntilwereachalevelwherenomorerefinementisneededandthe designcanbeimplementeddirectly,whereasinBottom-upprogrammingapproach, weidentifymodulesthatarerequiredbyprogramsanddecidehowtocombinethese modulestoprovidelargerones;tocombinethosetoprovideevenlargerones,and soon,tillwearriveatonebigmodulewhichisthewholeofthedesiredprogram. InBottom-upapproach,weneedtousealotofintuitiontodecideexactlywhat functionalityamoduleshouldprovide.ThisisnotthecaseinTop-downapproach. Q.255 Whatdoyoumeanbycomplexityofanalgorithm?Derivetheasymptotictime complexityofanonrecursive,binarysearchalgorithm. (7) Ans: Theterm complexityisusedtodescribetheperformanceofanalgorithm.Typically performance is measured in terms oftimeorspace.Space complexityofan algorithm istheamountofmemoryisneededtorunthealgorithm.Timecomplexity ofanalgorithm istheamountofcomputertimeitneedstorunthealgorithm.Most

commonnotationfordescribingtimecomplexity0(f(n)),wherenistheinputsize andfisafunctionofn.Analgorithm ~0(f(n))meansthereexistsNsuchthatforall n>Ntheruntimeofthealgorithm islessthanc.f(n),wherecisaconstant. Binarysearchcanbeappliedonasortedarraytosearchforaparticularitem. GivenarraypositionsA[l],thesearchisconductedinthefollowingway. Binsearch(x,l,n) { L=l; U=n; While(L<=U) {mid=(L+U)/2; If(A[mid]=x) Return.True; Else If(A[mid]>x) L=mid+1; Else U=mid-1; } returnFalse; } Thusateachstatethearrayishalvedintotwoequalparts.Intheworstcasethe algorithm terminateswhentheportionofthearrayconsideredisoflength1,Thusif n=2,intheworstcasethewhileloopwillhavetorepeatktimes.Wherek=logn. ThusasymptoticcomplexityisO(logn). Q.256 AssumethedeclarationofmultidimensionalarraysAandBtobe, A(-2:2,2:22)andB(1:8,-5:5,-10:5) (i)FindthelengthofeachdimensionandthenumberofelementsinAandB.(3) (ii)ConsidertheelementB[3,3,3]inB.FindtheeffectiveindicesE1,E2,E3andthe addressoftheelement,assumingBase(B)=400andthereareW =4wordsper memorylocation. (4) Ans: (i)A(-2:2,2:22),B(1:8,-5:5,-10:5)lengthof1stdimensioninA=2-(-2)+1 =2+2+1=5 lengthof2nddimensioninA=22-2+1=21 LI=lengthof1stdimensioninB=8-l+l=8 L2=lengthof2nddimensioninB=5-(-5)+1=11L3=lengthof3rddimensioninB=5-(- 10)+l=16No.ofelementsinA=5*21=105 No.ofelementsinB=8*11*16=1408

(ii)B[3,3,3],Base(B)=400,W=4 El=3-1=2 E2=3-(-5)=8 E3=3-(-10)=13 Address of B[3,3,3]=400+4(493) =2372 E1L2=2*11=22 E1L2+E2=22+8=30 (E1L2+E2)L3=30*16=480 (E1L2+E2)L3+E3=480+13=493 Q.257.(i)whatismeantbytheterms'row-majororder'and'column-majororder'? (2) (ii)Canthesizeofanarraybedeclaredatruntime? (2) (iii)ThearrayDATA[10,15]isstoredinmemoryin'row-majororder'. Ifbaseaddressis200andelementsizeis1.Calculatetheaddressofelement DATA[7,12]. (3) Ans:(i)Storingthearraycolumnbycolumnisknownascolumn-majororderand storingthearrayrowbyrowisknownasrow-major-order.Theparticularorderused dependsupontheprogramminglanguage,nottheuser.Forexampleconsiderarray A(3,4)andhowthisarraywillbestoredinmemoryinboththecasesisshownbelow (1,1) Column1 (1,1) Row1 (2,1) Column2 (1,2) Row2 (3,1) Column3 (1,3) (1,2) Column4 (1,4) Row3 (2,2) (2,1) (3,2) (2,2) (1,3) (2,3) (2,3) (2,4) (3,3) (3,1) (1,4) (3,2) (2,4) (3,3) (3,4) (3,4) (ii) No,thesizeofanarraycan'tbedeclaredatruntime,wealwaysneedto mentionthedimensionsofanarrayatthetimeofwritingprogram i.ebeforeruntime (iii)Baseaddress=200 ElementSize=l AddressofelementDATA[7,12] =200+[(7-l)*15+(12-l)]*l =200+[6*15+11] =200+[90+11]=301 AddressofDATA[7,12]=301 Q.258 Writeanalgorithm toinsertanodeafteragivennodeinalinearlinkedlist. (7) Ans:

SupposewearegivenavalueofLOCwhereLOCisthelocationofthenode 'A'inthelinkedlist. Thefollowingalgorithm insertsan'ITEM'intoLIST(givenLinkedlist)sothat‘TTEM' followsnode'A'. 1.IfAVAIL=NULL,Thenwriteoverflowandexit 2.setNEW =AVAILandAVAIL=:link[AVAIL][removefirstnodefrom AVAILLIST] 3.setINFO[NEW]=ITEM [copiesnewdataintonewnode] 4.ifLOC=NULLthen[insertasfirstnode] setLINK[NEW]=STARTandSTART=NEW else[insertafternodewithlocationLOC] setLINK[NEW]=LINK[LOC]andLINK[LOC]=NEW [endofifstructure] 5.exit Q.259 Showhowthefollowingpolynomialcanberepresentedusingalinkedlist. (4) 7x2y2-4x2y+5xy2-2 Ans: RepresentationofPolynomialusingLinkedList Eachnodewillhavefourparts(asshownbelow) Coeff Power PowerofNext of'x' 'y' address Thepolynomialis Q.260.Whatistheadvantageofdoublylinkedlistoversinglylinkedlist? (3) Ans: Advantagesofthedoublylinkedlistoversinglylinkedlist 1 Adoubly linked listcan be traversed in two directions;in the usual forwarddirection from the beginning of the list to the end,or in the backwarddirectionfrom theendofthelisttothebeginningofthelist. 2 Giventhelocationofanode'N'inthelist,onecanhaveimmediateaccesstoboth thenextnodeandtheprecedingnodeinthelist. 3 Givenapointertoaparticularnode'N',inadoublylinkedlist,wecandeletethe

Node'N'withouttraversinganypartofthelist.Similarly,insertioncanalsobe madebeforeorafter'N'withouttraversingthelist. Q.261 Whatisabinarytree?Writeanalgorithm forthepreordertraversalofabinary treeusingstacks. , (7) Ans: Abinarytree'T'isdefinedas Afinitesetofelements,callednodes,suchthat:either(i)or(ii)happens: (i)Tisempty(calledthe'nulltree'or'emptytree') (ii)T contains a distinguished node R,called the 'root'ofT and the remainingnodesof'T'form anorderedpairofthedisjointbinarytreeTl andT2. If'T'containsaroot'R'thenthetwotreesTlandT2arecalled,the'left'and 'right'subtreesofR,respectively. Algorithm forthepreordertraversalofabinarytreeusingastack A binarytreeTisinmemory,anarray'STACK'isusedtotemporarilyholdthe addressesofthenodes.\"PROCESS\"istheoperationthatwillbeappliedtoeach nodeofthetree. (1)SetTOP=1,STACK[1]=NULL and PTR=ROOT [initially pushnull onto Stack and initializePTR] (2)repeatsteps(3)to(5)whilePTR!=NULL (3)applyPROCESStoINFO[PTR] (4)[rightchild?] ifRIGHT[PTR]!=NULLthen[pushonSTACK] SetTOP=TOP+1bandSTACK[TOP]=RIGHT[PTR] [EndofIFStructure] (5)[LeftChild?] ifLEFT[PTR]!=NULLthen: setPTR=LEFT[PTR] else[POPfrom STACK] setPTR=STACK[TOP]andTOP=TOP+1 [EndofIFstructure] (6)Exit Q.262.AbinarytreeThas9nodes.TheinorderandpreordertraversalsofT (7) yieldthefollowingsequencesofnodes: InOrder:EACKFHDBG Pre order:FAEKCDHGB DrawthetreeT.Alsogivetheyieldofthepostordertraversal. Ans: Inorder:EACKFHDBG Preocder:EAEKCDHGB Tree‘T’is

PostorderTraversal-.ECKAHBGDF Q.263 Writeshortnotesonthefollowing: (i)Threadedbinarytree. (14) (ii) Buddy systems. (iii)B-trees. (iv)Minimum spanningtree. Ans: (i)Threaded binarytree:Considerthelinkedrepresentationofabinarytree'T. Approximatelyhalfoftheentriesisthepointerfields'LEFT'and'RIGHT'willcontain nullelements.This space maybe more efficientlyused byreplacing the null entriesby some othertype ofinformation.Specially we willreplace certain nullentries by specialpointers which points to nodes in the tree.These specialpointers 4 are called 'threads'and binarytrees with such pointers are called'threadedtrees'. Therearetwomajortypesofthreading:-onewaythreadingandtwowaythreading. IntheonewaythreadingofT,athreadwillappearintherightfieldofanodeandwill pointtothenextnodeintheinordertraversalofTandinthetwowaythreadingofT, athreadwillalsoappearintlleftfieldofanodeandwillpointtotheprecedingnode intheinordertraversalofT.Thereisanotherkindofonewaythreadingwhich correspondstothepreordertraversalofT. (ii)Buddysystems:Amethodofhandlingthestoragemanagementproblem iskept separatefreelistsforblocksofdifferentsizes.Eachlistcontainsfreeblocksofonly onespecificsize.Forexample,memorycontains1024 wordsthen itmightbe dividedintofifteenblocks,oneblockof256words,tblocksof128words,four blocksof64words,and8blocksof32words.Wheneversportisrequestedthe smallestblockiswhosesizeisgreaterthanorequaltothesizeneededtoreserve forexampleablockof97wordsisfieldbyablockofsizeof128butinthismethod thereare severallimitation,first,spaceiswasted due to internalfragmentation, second,arequestofblocksize300cannotbefilled.Thelargestsizeismaintainedis 256,thesourceofthisproblem isthatfreespacearenevercombined Avariationtothisschemeisbuddysystem andisquiteuseful.InBuddysystems severalfreelistconstituetsofvarioussizedblocksaremaintained.Adjacentfree blocksaresmallersizemayberemovedfrom listcombinedintofreeblocksoflarger size,andplacedonthelargersizefreelist.Theselargerblockscanbeusedintactto satisfyarequestforalargeamountofmemoryortheycanbesplitonceinto

theirsmallestconstituentstosatisfyseveralsmallerrequest. (iii)B-tree:A B-treeisabalancedm-waytree.Anodeofthetreemaycontain manyrecordsorkeyandpointerstochildren.Itisalsoknownasthebalanced sorttree.Itfindsitsuseinexternalsorting.Itisnotabinarytree. B-treeoforderm hasfollowingproperties: (1)eachnodehasamaximum ofm childrenandminimum ofm/2childrenor anynumberfrom 2tomaximum. (2)The no.ofkeys in a node is one less than its no ofchildren.The arrangement POKIPI....KnPn ΔΔΔ ToTITneachTlisam-waytree (3)Thekeys'inanodeKi— KnarearrangedinsortedorderK1<K2— <Kn.All thekeys presentinthesubtreepointedtobyapointerPiKi.Pi.Ki+1aregreater than (4)Whenanew keyistobeinsertedintoafullnode,thekeyissplitintotwo nodesandthekeywiththemedianvalueisinsertedintheparentnode.Incase theparentnodeisaroot,anewrootiscreated. (5)Alltheleavesareonthesameleveli.e.thereisnoemptysubtreeabovethelevel oftheleaves.AllthenormalnodesofB-tree(Except'root'andterminalnodes)have betweenm/2andm children. (iv)Minimum SpanningTree:GivenaweightedgraphG,itisoftendesiredtocreatea spanningtreeTforG,suchthatthesum ofweightsoftheedgesinTistheleast. Suchatreeiscalledaminimum spanningtreeandrepresentsthecheapestwayof connectingallthenodesinG .Thereareno.oftechniquestocreateaminimum spanningtreeforaweightedgraph.Forex.Kruskal'salgo.Prim'salgorithm. Example:-Thegivenconnectedweightedgraph Gis Oneoftheminimum spanningtreesofthegraphGis:- Minimum costofthespanningtree=14

Q.264. Whatis memory allocation? Explain the firstfitand bestfitalgorithms for storageallocation with suitable examples. (7) Ans: Memory Allocation:Itis the technique ofallocating memory storage toprogram inorderthattheprogram canberun. Firstfitalgorithm:The question asked forexamplesnotalgorithmsthe firstfitalgorithm maybeexplained. Suppose the memory allocation is as follows:suppose indicatesallocated block& denotesafreeblock.Thesizeofthe freeblocksareindicated.Supposethecurrentrequirementis8K.Thenthe firstfitalgorithm willallocateitfrom theblockof20K. Theadvantage;itispartdisadvantage:fragmentation. P=freeblock aloc=null q=null; while(p!=null&&size(p)<n) { Q=p; p=next(P) }/*endwhile*/ if(p!=null){/*thereisblocklargeenough*/ s=size(p); alloc=p+s-n;/*alloccontaintheaddressofthedesignedblock*/ if(s==n) /*removetheblockfrom thefreelist*/ if(q==null) freeblock=next(p); else next(q)=next(p); else /*adjustthesizeoftileremainingfreeblock*/ size(p)=s-n; }/*endif*/ TheBestfitalgorithm:Thebestfitmethodobtainsthesmallestfreeblock whosesizeisgreaterthanorequalton.Analgorithm toobtainsuchablock bytraversingtheentirefreelistfollows.Weassumethatthememsizeisthe totalno.ofwordsinmemory. TheBestfitalgorithm allocates the memory from the block thatfits therequirementbesti.e.theblockthathassizegreaterthantherequirement,

butnootherblockoflessersizecanmeettherequirement.Thusforthe aboveproblem the allocation willbe made from block ofsize 10 K. Advantage:fragmentationisreduced Disadvantage:moretime. p=freeblock;/*pisusedtotraversethefreelist*/ q==null;/*qisoneblockbehindp*/ r=null;/*rpointstothedesiredblock*/ rq=null;/*rqisoneblockbehindr*/ rsize=memsize+l;/*rsizeisthesizeoftheblockatr*/ alloc=null;/*allocwillpointtoblockselected*/ while(!=null) { if(size(p)>=n&&size(p)<rsize) { /*wehavefoundafreeblockcloserinsize*/ r=p; rq=q; rsize=size(p); } /*ENDIF*/ /*continuetraversingthefreelist*/ q=P; p=next(p); } /*endwhile*/ if{r!=null) { /*thereisblockofsufficientsize*/ alloc=r+rsize–n; if(rsize==n){ /*removetheblockfrom thefreelist*/if(rq= =null) freeblock=next(r); else next(rq)=next(r); elsesize(r)=rsize-n; }/*endif*/ Q.265.Considerthefollowinggraph

Fig2 LetthenodesbestoredinmemoryinanarrayGas:G;X,Y,Z,W (i)FindtheadjacencymatrixAofthegraphG. (ii)FindthepathmatrixPofGusingpowersoftheadjacencymatrix-A. (iii)IsGstronglyconnected? (3+3+1) Ans: AdjacercyMatrix'A'= XYZW X0111 (i)= Y0001 (ii)= Z0101 0111 W0010 A0001 = 0101 0010 A2= 01 1 1 0111 00 0 1 0001 01 0 1 0101 00 1 0 0010 0112 A2= 0 0 1 0 0111 0101 3=A2.A= 0 11 2 0 11 1

0 01 0 0 00 1 0 01 1 0 10 1 0 10 1 0 01 0 = 0 12 2 0 10 1 0 11 1 0 01 1 4=A3.A= 0 12 2 0 11 1 0 10 1 0 00 1 0 11 1 0 10 1 0 01 1 0 01 0 022 3 001 1 011 2 011 1 01 1 1 + 01 1 2 00 0 1 00 1 0 A4= 01 0 1 00 1 1 00 1 0 01 0 1 012 2 + 02 2 3 010 1 00 1 1 011 1 01 1 2 001 1 01 1 1 056 8 012 3 033 5 023 3 ’= 0 11 1

0 11 1 0 11 1 0 11 1 (iii)No,Gisnotstronglyconnected. Q.266.Whatisahashfunction?Describeanythreehashfunctions. (7) Ans: Hashfunction:Thisisthefunctionfrom theset'K'ofkeysintotheset'L'of memoryaddresses. H:KL Theseareusedtodeterminetheaddressofarecordwiththeuseofsomekey.Such afunction'H'maynotyielddistinctvalues:itispossiblethattwodiffkeysKland K2willyieldthesamehashaddress; Thissituationiscalledcollisionandsomemethodmustbeusedtoresolveit. Examples 1.Divisionmethod:Chooseanumber'm'largerthanthenumber'n'ofkeysinK: (Thenumberm isusuallychosentobeaprimenumber).Thehashfunction'H'is definedby H(K)=k(modm) WhereK(modm )denotestheremainderwhen'K'isdividedbym. 2.Midsquaremethod:Thekey'K'issquared,thenthehashfunction'H'isdefinedby H(K)=1Where1isobtainedbydeletingdigitsfrom bothends ofK2. 3.FoldingMethod:Thekey'K'ispartitionedintoano.ofpartsk1,k2,……kT,Where eachpartexcept,possiblythelast,hasthesamenumberofdigitsastherequired address.Thenthepartsareaddedtogether,ignoringthelastcarry,thatis H(k)=k1,k2,……kT,.Wheretheleadingdigitscarries,ifany,areignored.

Q.267 Writeanalgorithm forbubblesort.Whatistheasymptotictimecomplexityof bubble sortintheworstcase. (7) Ans: Algorithm forbubblesort: Let'A'bealineararrayofelementsandtempbethevariablefor interchangingthepositionoftheelements. 1.Input'n'elementsofanarray'a'. 2.initializei=0 3.repeattroughstep6while(i<n) 4.setj=0 5.repeatthroughstep6while(j<n-i-l) 6.if(a[j]>a|j+l]) (i)temp=a[j] (ii)a[j]=a[j+l] (iii)a[j+l]=temp 7.displaythesortedelements ofarray'a' 8.Exit. Inthissortingtechnique,eachelementiscomparedwithitsadjacentelement.Ifthe firstelementislargerthanthesecondonethenthepositionoftheelementsare interchanged,otherwiseitisnotchanged.Thennextelementarecomparedwithits adjacentelementandthesameprocessisrepeatedforalltheelementsinthearray. Duringthefirstpassthesameprocessisrepeatedleavingthelastelement.During thesecondpassthesecondlastelementoccupiesthesecondlastposition.The sameprocessisrepeateduntilnomoreelementsareleftforthecomparison.Finally thearrayissorted.OnemayuseaHagtocheckwhetherthereisanyinterchangein aparticularpass.Ifthereisnointerchangeinapass,thearrayhasalreadygotsorted, andthealgorithm canterminate. Timecomplexityinworstcase:inworstcase,thearraywillbeinreversesorted orderandtheno.ofcomparisonsarecalculatedasgivenbelow F(n)=l+2+3+4+———+(n-l) =n(n-l)/2=O(n2) Q.268 ApplyKruskal'salgorithm tofindaminimum spanningtreeofthegraphinthe following figure-Display execution of each step of thealgorithm. (8)

Fig3 Describetheinsertionsortalgorithm.Computeitsasymptotictimecomplexityfor worstcaseandaveragecase. (6) Ans: Thegivengraphisname the vertices asshown Tofindminimumspanningtreeofthegivengraph:- Edges: AB BC AD BE CF AE CE DE EF Weight: 2 1 2 1 2 2 1 2 1 Edges: DG EH FI GH HI GE HE Weight: 3 1 3 3 3 3 1 Edgesinincreasingorderofweights FI GH HI GE Edg BC BE CE EF EH HF AB AD CF AE DE DG e s

: Wei 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 g h t : Add yes yes no yes yes no yes yes no no no yes yes no no no : Step1 Add‘BC’ Step2 Add‘BE’ Step3Add‘EF’ Step4Add‘EH’ Step5Add‘AB’

Step6Add‘AD’ STEP7Add'DG' STEP8 Add'FI’

Costof the spanning Tree= 1+2+2+1+3+1+3+1=14 This is the required spanningtreeofthegivengraph. Q.269Defineaheap.Describethealgorithm toinsertanelementintotheheap. (2+5) Ans: InsertionSortAlgorithm: Consideranarray'A'with'N'elements 1.setA[0]=-infinity[initializesentinelelement] 2.Repeatsteps3to5forK=2,3..,.......N 3.setTEMP=A[K]andPTR=K-14RepeatwhileTEMP<A[PTR] (a)setA[PTR+1]=A[PTR][moveselementforward] (b)setPTR=PTR-1[Endofloop] 5.setA[PTR+1]=TEMP[insertselementsinproperplace] [Endofstep2loop] 6.Return Complexityofinsertionsort Worstcase:Theworstcaseoccurswhenthe-array'A'isinreverseorderand theinnerloopmustusethemaxnumberK-lofcomparisons.Hence F(n)=l+2+........+(n-l)=n(n-l)/2=0(n2) Averagecase:InAveragecasetherewillbeapproximately(K-l)/2comparisons intheinnerloop.Accordingly,fortheaveragecase, F(n)=l/2+2/2+...........+(n-l)/2=n(n-l)/4=0(n2) Q.270 Constructthe heap showing the insertion ofeach ofthe followingelements in separatefigures.44,30,50,22,60;50 (7) Ans: Heap:Suppose'H'isacompletebinarytreewith'n'elements.Then'H'iscalleda Heap,asa'maxheap',ifeachnode'N'of'H'hasthefollowingproperty: Thevalueat'N'isgreaterthanorequaltothevalueateachofthechildrenofN. Accordingly,thevalueatNisgreaterthanorequaltothevalueatanyofthedescerdants ofN. Algorithm toinsertanelementintotheheap:Consideraheap'H'with'N'elementsis storedin the array TREE and an ITEM ofinformation is given.This procedure inserts'ITEM'asanew elementof'H'.'PTR'givesthelocationofITEM asitrisesinthe tree,and'PAR'denotesthelocationoftheparentof'ITEM'.

1.[Addnewnodeto'H'andinitializePTR]setN=N+1andPTR=N 2. [ Find location to insert ITEM ] Repeatsteps3 to 6 while PTR>1 3. setPAR= [PTR/2](flooroperation) [Locationofparentnode]IfITEM<=TREE [PAR]thenstep4elsegotostep5. 4. setTREE [PTR]=ITEM andreturnEnd ofIfstructure 5.setTREE[PTR]=TREE[PAR] [movesnodedown] 6 setPTR =PAR//»u pdatesPT R //»Endof step2 loop 7. //»Comments Assign ITEM as the rootofH]setTREE[1]= ITEM 8.Return 10.(b)Constructionofheap: Step1 inserting44 Step2Inserting30 Step3Inserting50

Step4inserting22 Step5inserting60 step6 inserting50 Thisistherequiredheap. Q.271Givetheequivalentpostfixexpressionforthefollowingexpressions: (i)(A-B)/((D+E)*F) (ii)((A+B)/D)↑((E-F)*G) (3+4) Ans:

Convertthefollowinginfixexpressionsintopostfireusingastack.Show ateach stepthestackcontentsandtheoutputstring. (i)((A-B)/((B+E)*F))Add\"(\"tothestartingand\")\"attheendofexpr. Symbolsscanned Stack ExpressionP 1 (( A A 2 ( (( AB AB- 3 A (( AB- AB- 4 - ((- AB- AB-D 5 B ((- AB-D AB—DE 6 )( AB-DE+ AB-DE+ 7 / (/ AB-DE+F AB-DE+F* 8 ( (/( AB-DE+F*/ 9 ( (/(( 10 D (/(( 11 + (/((+ 12 E (/((+ 13 ) (/( 14 * (/(* 15 F (/(* 16 ) (/ 17 )

ThepostfixexpressionisP=AB-DE+F*/ (ii) Thegivenexpressionis(((A+B)/D)^((E-F)*G))Add\"('tothestartand \")attheendoftheexpression. Symbolsscanned Stack ExpressionP 1(( 2 ( (( 3 ( ((( 4 A ((( A 5 + (((+ A 6 B (((+ AB 7 ) (( AB+ 8 / ((/ AB+ 9 D ((/ AB+D 10 ) ( AB+D/ 11 ( AB+D/ 12 ( (( AB+D/ 13 ( ( (( AB+D/ 14 E ( (( AB+D/E 15 - ( ((- AB+D/E 16 F ( ((- AB+D/EF 17 ) (( AB+D/EF- 18 * ( (* AB+D/EF- 19 G ( (* AB+D/EF-G 20 ) ( AB+D/EF-G* 21 ) AB+D/EF-G* Thepostfixexpression‘P’=AB+D/EF-G* Q.272 SupposeaqueueismaintainedbyacirculararrayQUEUEwithN=12memorycells. FindthenumberofelementsinQUEUEif (i)Front=4,Rear=8. (ii)Front=10,Rear=3. (iii)Front=5,Rear=6andthentwoelementsaredeleted. (2+2+3) Ans:

Q.273Supposewewishtopartitionthesquarerootsoftheintegersfrom 1to100intotwo pilesoffiftynumberseach,suchthatthesum ofthenumbersinthefirstpileis ascloseaspossibletothesum ofthenumbersinthesecondpile.Ifyoucoulduse minimum computertimetoanswerthisquestion,whatcomputationswouldyou perform onthecomputerinthattime? (5) Ans: Accordingtoquestion,sum ofsquarerootsintwopilesshouldbeascloseaspossible. Forthatwecanaddsquarerootsofoddnumbers.Inonepileandsquarerootsofeven numbersinanotherpile.Sincefornaturalnumbersalsoifwewanttodivideintotwo piles according to nearest equalsumrequirement above solution will work i.e.1+3+………………….+99,2+4+…………..+100.Squarerootisastrictlyincreasingfunction forpositivenumbers.Soresultholdsforsquarerootalso. Computations 1.Checkwhetherno.isoddorevendividingbytwo,moduleiszeroornot. 2.Addthevariablesum computationtimefornnos.Itwillrequireθ(n)time. Q.274 Farelyfractionsofleveloneisdefined assequence(0/1,1/1).Thissequence isextendedinleveltwotoform asequence(0/1,½,1/1),sequence(0/1,1/3,½,2/3, 1/1)atlevelthree,sequence(0/1,¼,1/3,½,2/3,¾,1/1)atlevelfour,sothatateach leveln,anew fraction(a+b)/(c+d)isinsertedbetweentwoneighbourfractionsa/c andb/donlyifc+d<=n.Deviseaprocedure,whichforanumbernenteredbythe usercreates–byconstantlyextendingit–alinkedlistoffractionsatleveln. (8)

Ans: List{intinfo; intinfo; list*next;}; Farelyfractions(n){ listI0,I1,x; info1(I1)=00; info2(I1)=1; next(I1)=I2; info1(I2)=1; info(I2)=1; next(I2)=NULL; for(i=2;i<=n;i++){ x=head[L]; while(x!=nil&&info1(x)+info1(next)(xL)<=i){ listI; info(Ij)=info2(xo)+info2(next,x0)); info(Ij)=info1(x)+info1(next); listinsert(L,x); x=next(x)}}} Q.275 SupposethataBinarySearchTreeisconstructedbyrepeatedlyinsertingdistinct valuesintothetree.Arguethatthenumberofnodesexaminedinsearchingfora valueinthetreeisoneplusthenumberofnodesexaminedwhenthevaluewas firstinsertedintothetree. (7) Ans: Letusconsideranelementxtoinsertinabinarysearchtree.Soforinsertingthe elementxfirstatlevel0,thenlevel1andsupposeuptolevel(d-1).Whileexamineat(d -1)level,xmighthavelessormoreincomaprisontoelementat(d-1).Thenweinsert xeitherleftorright.Inbothcasesnoofexaminedcodewillbed.Now supposewe wantto search forx,thistime again traversesthe same path aswe traverse. Whileinserting the element,we stop at(d-1)the levelbutforsearching we examinenodeatdthlevelalsoi.e.thenodecontainingx.Thusnumberofnode examinewhileinsertingaredwhile incaseofsearchingitisd+1i.e.onemorethan whileinserting,hencetheresult.