This file contains the exercises, hints, and solutions for Chapter 1 of the book ”Introductionto the DesignandAnalysis ofAlgorithms,” 2ndedition,by A.Levitin. The problems thatmightbe challenging forat least some students aremarkedby; thosethatmightbedifficultforamajorityof studentsare markedby . Exercises1.1 1. Do some researchonal-Khorezmi (also al-Khwarizmi), the manfrom whosenametheword“algorithm”isderived. Inparticular, youshould learnwhat theorigins of thewords“algorithm”and“algebra”havein common. 2. Giventhattheofficial purposeof theU.S. patentsystemisthepromo- tionof the“useful arts,”doyouthinkalgorithmsarepatentableinthis country? Shouldtheybe? 3. a. Write down driving directions for going from your school to your home withtheprecisionrequiredbyanalgorithm. b. Writedownarecipeforcookingyourfavoritedishwiththeprecision requiredbyanalgorithm. 4. Designanalgorithmforcomputing ¸ √ n|foranypositiveintegern. Be- sidesassignmentandcomparison, youralgorithmmayonlyusethefour basicarithmeticaloperations. 5. a. Findgcd(31415,14142)byapplyingEuclid’salgorithm. b. Estimatehowmanytimesfasteritwill betofindgcd(31415, 14142) byEuclid’s algorithmcomparedwiththealgorithmbasedonchecking consecutiveintegersfrommin¦m, n¦downtogcd(m, n). 6. Prove the equality gcd(m, n) = gcd(n, mmodn) for every pair of positive integersmandn. 7. WhatdoesEuclid’salgorithmdoforapairofnumbersinwhichthefirst numberissmallerthanthesecondone? Whatisthelargestnumberof times this can happen during the algorithm’s execution on such an input? 8. a. WhatisthesmallestnumberofdivisionsmadebyEuclid’salgorithm amongallinputs1 ≤ m, n ≤ 10? b. Whatisthelargestnumberof divisionsmadebyEuclid’salgorithm amongallinputs1 ≤ m, n ≤ 10? 9. a. Euclid’salgorithm,aspresentedinEuclid’streatise,usessubtractions rather thaninteger divisions. Write apseudocode for this versionof Euclid’salgorithm. 1 b.Euclid’sgame(see[Bog])startswithtwounequal positivenumbers ontheboard. Twoplayersmoveinturn. Oneachmove, aplayerhas towriteontheboardapositivenumber equal tothedifferenceof two numbersalreadyontheboard; thisnumbermustbenew, i.e., different from all the numbers already on the board. The player who cannot move losesthegame. Shouldyouchoosetomovefirstorsecondinthisgame? 10. The extended Euclid’s algorithmdetermines not onlythe greatest commondivisordoftwopositiveintegersmandnbutalsointegers(not necessarilypositive)xandy,suchthatmx + ny = d. a. Lookupadescriptionof theextendedEuclid’salgorithm(see, e.g., [KnuI],p. 13)andimplementitinthelanguageofyourchoice. b. Modifyyour programfor findinginteger solutions totheDiophan- tineequationax + by=cwithanysetof integercoefficientsa, b, and c. 11. Locker doors Therearenlockers inahallwaynumberedsequentially from1ton. Initially,allthelockerdoorsareclosed. Youmakenpasses bythelockers, eachtimestartingwithlocker#1. Ontheithpass, i= 1, 2, ..., n, youtogglethedoorof everyithlocker: if thedoorisclosed, youopenit, if itisopen, youcloseit. Forexample, afterthefirstpass every door is open; on the second pass you only toggle the even-numbered lockers (#2, #4, ...) sothat after thesecondpass theevendoors are closedandtheoddonesareopened;the thirdtimethroughyouclosethe doorof locker#3(openedfromthefirstpass), openthedoorof locker #6(closedfromthesecondpass),andsoon. Afterthelastpass,which locker doors are open and which are closed?How many of them are open? 2 HintstoExercises1.1 1. It isprobablyfaster todothisbysearchingtheWeb, but your library shouldbeabletohelptoo. 2. One can find arguments supporting either view. There is a well established principlepertinenttothematterthough: scientificfactsormathematical expressions of them are not patentable. (Why do you think it is the case?) Butshouldthisprecludegrantingpatentsforallalgorithms? 3. You may assume that you are writing your algorithms for a human rather than a machine. Still, make sure that your descriptions do not contain ob- viousambiguities. Knuth[KnuI],p.6providesaninterestingcomparison betweencookingrecipesandalgorithms. 4. Thereisaquitestraightforwardalgorithmforthisproblembasedonthe definitionof ¸ √ n|. 5. a. JustfollowEuclid’salgorithmasdescribedinthetext. b. Comparethenumberofdivisionsmadebythetwoalgorithms. 6. Provethatifddividesbothmandn(i.e., m=sdandn=tdforsome positiveintegerssandt), thenitalsodividesbothnandr=mmodn and vice versa. Use the formula m = qn+r(0 ≤ r < n) and the fact that ifddivides two integersuandv,italso dividesu +vandu −v. (Why?) 7. Performoneiterationofthealgorithmfortwoarbitrarilychosenintegers m < n. 8. The answer topart (a) canbe givenimmediately; theanswer topart (b) canbe givenbycheckingthealgorithm’s performance onall pairs 1 < m < n ≤ 10. 9. a. Usetheequality gcd(m, n) = gcd(m − n, n)form ≥ n > 0. b. The key is to figure out the total number of distinct integers that can be writtenonthe board,starting withan initialpair m, nwhere m > n ≥ 1. Youshouldexploitaconnectionof thisquestiontothequestionof part (a). Consideringsmallexamples,especiallythosewithn = 1andn = 2, shouldhelp,too. 10. Ofcourse,forsomecoefficients,theequationwillhavenosolutions. 11. Tracingthealgorithmbyhandfor,say,n = 10andstudyingitsoutcome shouldhelpansweringbothquestions. 3 SolutionstoExercises1.1 1. Al-Khwarizmi (9thcenturyC.E.) wasagreat Arabicscholar, most fa- mousfor hisalgebratextbook. Infact, theword“algebra”isderived fromtheArabictitleofthisbookwhiletheword“algorithm”isderived from a translation of Al-Khwarizmi’s last name (see, e.g., [KnuI], pp. 1-2, [Knu96],pp. 88-92,114). 2. Thislegal issuehasyettobesettled. Thecurrentlegal stateof affairs distinguishes mathematical algorithms, whichare not patentable, from otheralgorithms, whichmaybepatentableif implementedascomputer programs(e.g.,[Cha00]). 3. n/a 4. Astraightforwardalgorithmthatdoesnotrelyontheavailabilityof an approximatevalueof √ ncancheckthesquares of consecutivepositive integers until the first square exceeding n is encountered. The answer will bethenumber’simmediatepredecessor. Note: Amuchfasteralgorithm forsolvingthisproblemcanbeobtainedbyusingNewton’smethod(see Sections11.4and12.4). 5. a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) = gcd(1618, 1513) = gcd(1513, 105) = gcd(1513, 105) = gcd(105, 43) = gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1. b. Toanswerthequestion, weneedtocomparethenumberofdivisions thealgorithmsmakeontheinputgiven. Thenumberof divisionsmade byEuclid’salgorithmis11(seeparta). Thenumberofdivisionsmade bytheconsecutiveintegercheckingalgorithmoneachofits14142itera- tionsiseither1and2; hencethetotal numberof multiplicationsisbe- tween 114142 and 214142. Therefore, Euclid’s algorithm will be between 114142/11 ≈ 1300and214142/11 ≈ 2600timesfaster. 6. Letusfirstprovethatif ddividestwointegersuandv, italsodivides both u+vand u−v. By definition of division, there exist integers s and tsuchthatu = sdandv = td. Therefore u ± v = sd ± td = (s ± t)d, i.e.,ddividesbothu + vandu − v. 4 Alsonotethatif ddividesu, italsodividesanyintegermultiplekuof u. Indeed,sinceddividesu,u = sd. Hence ku = k(sd) = (ks)d, i.e.,ddividesku. Nowwecanprovetheassertioninquestion. For anypair of positive integersmandn, ifddividesbothmandn, italsodividesbothnand r = mmodn = m−qn. Similarly, if d divides both n and r = mmodn = m − qn, it alsodivides bothm=r+ qnandn. Thus, thetwopairs (m, n)and(n, r)havethesamefinitenonemptysetofcommondivisors, includingthelargestelementintheset,i.e.,gcd(m, n) = gcd(n, r). 7. Foranyinputpairm, nsuchthat0 ≤m< n,Euclid’salgorithmsimply swapsthenumbersonthefirstiteration: gcd(m, n) = gcd(n, m) because mmodn = m if m < n. Such a swap can happen only once since gcd(m, n) = gcd(n, mmodn) implies that the first number of the new pair (n) will be greater than its second number (mmodn) after every iteration ofthealgorithm. 8. a. Foranyinputpairm ≥ n ≥ 1,inwhichmisamultipleofn,Euclid’s algorithmmakesexactlyonedivision; itisthesmallestnumberpossible fortwopositivenumbers. b. The answer is 5divisions, whichis madebyEuclid’s algorithmin computinggcd(5, 8). Itisnottootimeconsumingtogetthisanswerby examiningthenumber of divisionsmadebythealgorithmonall input pairs1 < m < n ≤ 10. Note: Apertinent general result (see[KnuII], p. 360) is that for any inputpairm, nwhere0 ≤n 0 temp ← 2 ∗ a x1 ← (−b + sqrt(D))/temp x2 ← (−b − sqrt(D))/temp 10 returnx1, x2 elseif D = 0return −b/(2 ∗ a) elsereturn‘noreal roots’ else//a = 0 if b ,= 0return −c/b else//a = b = 0 if c = 0return‘all real numbers’ elsereturn‘noreal roots’ Note: SeeamorerealisticalgorithmforthisprobleminSection11.4. 5. a. Dividethegivennumbernby2: theremainderr n (0or1)will be the next (from right to left) digit of the binary representation in question. Replacenbythequotientof thelastdivisionandrepeatthisoperation untilnbecomes0. b. AlgorithmBinary(n) //Thealgorithmimplementsthestandardmethodforfinding //thebinaryexpansionofapositivedecimalinteger //Input: Apositivedecimalintegern //Output: Thelistb k b k−1 ...b 1 b 0 ofn’sbinarydigits k ← 0 whilen ,= 0 b k ← nmod2 n ← ¸n/2| k ← k + 1 6. n/a 7. a. π,asanirrationalnumber,canbecomputedonlyapproximately. b. Itisnatural toconsider, asaninstanceof thisproblem, computing π’s value with a given level of accuracy, say, with n correct decimal digits. Withthisinterpretation,theproblemhasinfinitelymanyinstances. 8. n/a 9. Thefollowingimprovedversionconsidersthesamepairofelementsonly onceandavoidsrecomputingthesameexpressionintheinnermostloop: AlgorithmMinDistance2(A[0..n − 1]) //Input: AnarrayA[0..n − 1]ofnumbers //Output: Theminimumdistancedbetweentwoofitselements 11 dmin ← ∞ fori ← 0ton − 2do forj ← i + 1ton − 1do temp ← [A[i] − A[j][ if temp < dmin dmin ← temp returndmin Afasteralgorithmisbasedontheideaofpresorting(seeSection6.1). 10. Polya’sgeneralfour-pointapproachis: 1. Understandtheproblem 2. Deviseaplan 3. Implementtheplan 4. Lookback/check 12 Exercises1.3 1. Consider thealgorithmfor thesortingproblemthat sorts anarrayby counting, for eachof its elements, thenumber of smaller elements and thenusesthisinformationtoputtheelementinitsappropriateposition inthesortedarray: AlgorithmComparisonCountingSort(A[0..n − 1],S[0..n − 1]) //Sortsanarraybycomparisoncounting //Input: ArrayA[0..n − 1]oforderablevalues //Output: ArrayS[0..n − 1]ofA’selementssortedinnondecreasingorder fori ← 0ton − 1do Count[i] ← 0 fori ← 0ton − 2do forj ← i + 1ton − 1do if A[i] < A[j] Count[j] ← Count[j] + 1 elseCount[i] ← Count[i] + 1 fori ← 0ton − 1do S[Count[i]] ← A[i] a. Applythisalgorithmtosortingthelist60,35,81,98,14,47. b. Isthisalgorithmstable? c. Isitinplace? 2. Namethealgorithmsforthesearchingproblemthatyoualreadyknow. Giveagoodsuccinctdescriptionof eachalgorithminEnglish. (If you knownosuchalgorithms,usethisopportunitytodesignone.) 3. Designasimplealgorithmforthestring-matchingproblem. 4. Königsberg bridges The Königsberg bridge puzzle is universally accepted as the problem that gave birth to graph theory. It was solved by the great Swiss-bornmathematicianLeonhardEuler (1707—1783). Theproblem askedwhetheronecould, inasinglestroll, crossall sevenbridgesofthe city of Königsbergexactly once and return to a starting point. Following isasketchoftheriverwithitstwoislandsandsevenbridges: a. Statetheproblemasagraphproblem. 13 b. Doesthisproblemhaveasolution? Ifyoubelieveitdoes, drawsuch astroll; if youbelieveitdoesnot, explainwhyandindicatethesmall- estnumberofnewbridgesthatwouldberequiredtomakesuchastroll possible. 5. IcosianGame Acenturyafter Euler’s discovery(seeProblem4), an- otherfamouspuzzle–thisoneinventedbytherenownIrishmathemati- cian Sir William Hamilton (1805-1865)–was presented to the world under the name of the Icosian Game. The game was played on a circular wooden boardonwhichthefollowinggraphwascarved: FindaHamiltoniancircuit–apaththatvisitsallthegraph’svertices exactlyoncebeforereturningtothestartingvertex–forthisgraph. 6. Consider thefollowingproblem: Designanalgorithmtodeterminethe bestrouteforasubwaypassengertotakefromonedesignatedstationto anotherinawell-developedsubwaysystemsimilartothoseinsuchcities asWashington,D.C.,andLondon,UK. a. Theproblem’sstatementissomewhatvague, whichistypical ofreal- lifeproblems. Inparticular, whatreasonablecriterioncanbeusedfor definingthe“best”route? b. Howwouldyoumodelthisproblembyagraph? 7. a. Rephrase the traveling salesman problem in combinatorial object terms. b. Rephrasethegraph-coloringproblemincombinatorialobjectterms. 8. Considerthefollowingmap: 14 a b c d e f a. Explainhowwecanusethegraph-coloringproblemtocolorthemap sothatnotwoneighboringregionsarecoloredthesame. b. Use your answer to part (a) to color the map with the smallest number ofcolors. 9. Designanalgorithmforthefollowingproblem: Givenasetof npoints intheCartesianplane, determinewhether all of themlieonthesame circumference. 10. Writeaprogramthat reads as its inputs the(x, y) coordinates of the endpointsoftwolinesegmentsP 1 Q 1 andP 2 Q 2 anddetermineswhether thesegmentshaveacommonpoint. 15 HintstoExercises1.3 1. Tracethealgorithmontheinputgiven. Usethedefinitionsofstability andbeinginplacethatwereintroducedinthesection. 2. Ifyoudonotrecallanysearchingalgorithms,youshoulddesignasimple searching algorithm (without succumbing to the temptation to find one in thelatterchaptersofthebook). 3. Thisalgorithmisintroducedlater inthebookbut youshouldhaveno troubletodesignitonyourown. 4. If youhavenotencounteredthisprobleminyourpreviouscourses, you may look up the answers on the Web or in a discrete structures textbook. Theanswersare,infact,surprisinglysimple. 5. Noefficientalgorithmforsolvingthisproblemforanarbitrarygraphis known. ThisparticulargraphdoeshaveHamiltoniancircuitswhichare notdifficulttofind. (Youneedtofindjustoneofthem.) 6. a. Putyourself (mentally)inapassenger’splaceandaskyourself what criterionforthe“best”routeyouwoulduse. Thenthinkofpeoplethat mayhavedifferentneeds. b. The representation of the problem by a graph is straightforward. Give somethoughtsthoughtostationswheretrainscanbechanged. 7. a. Whataretoursinthetravelingsalesmanproblem? b. It wouldbe natural toconsider vertices coloredthe same color as elementsofthesamesubset. 8. Create a graph whose vertices represent the map’s regions. You will have todecideontheedgesonyourown. 9. Assumethatthecircumferenceinquestionexistsandfinditscenterfirst. Also,donotforgettogiveaspecialanswerforn ≤ 2. 10. Becarefulnottomisssomespecialcasesoftheproblem. 16 SolutionstoExercises1.3 1. a. Sorting60, 35, 81, 98, 14, 47bycomparisoncountingwill workas follows: ArrayA[0..5] 60 35 81 98 14 47 Initially Count[] 0 0 0 0 0 0 Afterpassi = 0 Count[] 3 0 1 1 0 0 Afterpassi = 1 Count[] 1 2 2 0 1 Afterpassi = 2 Count[] 4 3 0 1 Afterpassi = 3 Count[] 5 0 1 Afterpassi = 4 Count[] 0 2 Finalstate Count[] 3 1 4 5 0 2 ArrayS[0..5] 14 35 47 60 81 98 b. The algorithmis not stable. Consider, as acounterexample, the resultofitsapplicationto1 ,1 . c. Thealgorithmisnotinplacebecauseitusestwoextraarraysofsize n: CountandS. 2. Answersmayvarybutmoststudentsshouldbefamiliarwithsequential search, binary search, binary tree search and, possibly, hashing from their introductoryprogrammingcourses. 3. Alignthepatternwiththebeginningof thetext. Comparethecorre- spondingcharactersofthepatternandthetextleft-torightuntil either allthepatterncharactersarematched(thenstop–thesearchissuccess- ful) or thealgorithmruns out of thetext’s characters (thenstop–the search is unsuccessful) or a mismatching pair of characters is encountered. Inthelattercase, shiftthepatternonepositiontotherightandresume thecomparisons. 4. a.Ifwe representeachoftheriver’sbanks andeachofthetwo islandsby verticesandthebridgesbyedges,wewillgetthefollowinggraph: 17 b a c d b a c d (Thisis,infact,amultigraph,nota graph,becauseithas morethanone edge between the same pair of vertices. But this doesn’t matter for the is- sue at hand.) The question is whether there exists a path (i.e., a sequence of adjacent vertices) in this multigraph that traverses all the edges exactly once and returns to a starting vertex. Such paths are called Euleriancir- cuits;if a path traverses all the edges exactly once but does not return to itsstartingvertex,itiscalledanEulerianpath. b. Euler proved that an Eulerian circuit exists in a connected (multi)graph ifandonlyifallitsverticeshaveevendegrees,wherethedegreeofaver- texisdefinedasthenumberofedgesforwhichitisanendpoint. Also, anEulerianpathexistsinaconnected(multi)graphifandonlyifithas exactly two vertices of odd degrees; such a path must start at one of those twoverticesandendattheother. Hence,forthemultigraphofthepuz- zle,thereexistsneitheranEuleriancircuitnoranEulerianpathbecause allitsfourverticeshaveodddegrees. If wearetobesatisfiedwithanEulerianpath, twoof themultigraph’s vertices must be made even. This can be accomplished by adding one new bridgeconnectingthesameplacesastheexistingbridges. Forexample, a new bridge between the two islands would make possible, among others, thewalka − b − c − a − b − d − c − b − d b a c d b a c d Ifwe want a walkthat returns to its starting point,allthe vertices in the 18 corresponding multigraph must be even. Since a new bridge/edge changes theparityoftwovertices,atleasttwonewbridges/edgeswillbeneeded. Forexample,hereisonesuch“enhancement”: b a c d b a c d Thiswouldmakepossiblea − b − c − a − b − d − c − b − d − a, among severalothersuchwalks. 5. AHamiltoniancircuitismarkedonthegraphbelow: 6. a. Atleastthree“reasonable”criteriacometomind: thefastesttrip, a tripwiththesmallestnumberoftrainstops,andatripthatrequiresthe smallestnumberof trainchanges. Notethatthefirstcriterionrequires theinformationabouttheexpectedtravelingtimebetweenstationsand thetimeneededfortrainchangeswhereastheothertwocriteriadonot requiresuchinformation. b. Anatural approachis tomimicsubwayplans byrepresentingsta- tionsbyverticesof agraph, withtwoverticesconnectedbyanedgeif there is a train line between the corresponding stations. If the time spent onchangingatrainistobetakenintoaccount(e.g.,becausethestation inquestionisonmorethanoneline), thestationshouldberepresented bymorethenonevertex. 19 7. a. Find a permutation of n given cities for which the sum of the distances betweenconsecutivecitiesinthepermutationplusthedistancebetween itslastandfirstcityisassmallaspossible. b. Partitionall thegraph’sverticesintothesmallestnumberofdisjoint subsets so that there is no edge connecting vertices from the same subset. 8. a. Createagraphwhosevertices represent themap’s regions andthe edgesconnecttwo verticesifand onlyifthe corresponding regionshave a commonborder(andthereforecannotbecoloredthesamecolor). Here isthegraphforthemapgiven: b c b a d c e f Solvingthegraphcoloringproblemforthisgraphyieldsthemap’scolor- ingwiththesmallestnumberofcolorspossible. b. Without loss of generality, wecanassigncolors1and2tovertices canda, respectively. Thisforcesthefollowingcolorassignmenttothe remaining vertices: 3 to b, 2 to d, 3 to f, 4 to e. Thus, the smallest number ofcolorsneededforthismapisfour. Note: It’sawell-knownfactthatanymapcanbecoloredinfourcolors or less. This problem–known as the Four-Color Problem–has remained unresolved for more than a century until 1976 when it was finally solved by theAmericanmathematiciansK.AppelandW.Hakenbyacombination ofmathematicalargumentsandextensivecomputeruse. 9. If n=2, theanswer is always “yes”; so, wemayassumethat n ≥3. SelectthreepointsP 1 ,P 2 ,andP 3 fromthesetgiven. Writeanequation oftheperpendicularbisectorl 1 ofthelinesegmentwiththeendpointsat P 1 and P 2 , which is the locus of points equidistant from P 1 and P 2 . Write anequationoftheperpendicularbisectorl 2 ofthelinesegmentwiththe endpointsatP 2 andP 3 ,whichisthelocusofpointsequidistantfromP 2 and P 3 . Find the coordinates (x, y) of the intersection point Pof the lines l 1 andl 2 bysolvingthesystemoftwoequationsintwounknownsxand y. (If thesystemhas nosolutions, return“no”: suchacircumference doesnotexist.) Computethedistances(ormuchbetteryetthedistance squares!)from Pto each of the points P i , i = 3, 4, ..., n and check whether all of them are the same: if they are, return “yes,” otherwise, return “no”. 20 Exercises1.4 1. Describehowonecanimplementeachof thefollowingoperationsonan arraysothatthetimeittakesdoesnotdependonthearray’ssizen. a. Deletetheithelementofanarray(1 ≤ i ≤ n). b. Delete the ithelement of asortedarray(the remainingarrayhas tostaysorted,ofcourse). 2. If youhavetosolvethesearchingproblemforalistof nnumbers, how canyoutakeadvantageof thefactthatthelistisknowntobesorted? Giveseparateanswersfor a. listsrepresentedasarrays. b. listsrepresentedaslinkedlists. 3. a. Showthestackafter eachoperationof thefollowingsequencethat startswiththeemptystack: push(a),push(b),pop,push(c),push(d),pop b. Showthequeueafter eachoperationof thefollowingsequencethat startswiththeemptyqueue: enqueue(a),enqueue(b),dequeue,enqueue(c),enqueue(d),dequeue 4. a. LetAbetheadjacencymatrixofanundirectedgraph. Explainwhat propertyofthematrixindicatesthat i. thegraphiscomplete. ii. thegraphhasaloop,i.e.,anedgeconnectingavertextoitself. iii. thegraphhasanisolatedvertex,i.e.,avertexwithnoedgesincident toit. b. Answerthesamequestionsfortheadjacencylistrepresentation. 5. Giveadetaileddescriptionof analgorithmfortransformingafreetree intoatreerootedatagivenvertexofthefreetree. 6. Prove the inequalities that bracket the height of abinarytree withn vertices: ¸log 2 n| ≤ h ≤ n − 1. 7. IndicatehowtheADTpriorityqueuecanbeimplementedas a. an(unsorted)array. 21 b. asortedarray. c. abinarysearchtree. 8. Howwouldyouimplement adictionaryof areasonablysmall sizenif you knew thatallitselementsaredistinct (e.g.,names of50 statesofthe United States)? Specify an implementation of each dictionary operation. 9. For each of the following applications, indicate the most appropriate data structure: a. answeringtelephonecallsintheorderoftheirknownpriorities. b. sendingbacklogorderstocustomersintheordertheyhavebeenre- ceived. c. implementingacalculatorforcomputingsimplearithmetical expres- sions. 10. Anagramchecking Designanalgorithmforcheckingwhethertwogiven wordsareanagrams, i.e., whetheronewordcanbeobtainedbypermut- ingtheletters of theother. (For example, thewordstea andeat are anagrams.) 22 HintstoExercises1.4 1. a. Takeadvantageofthefactthatthearrayisnotsorted. b. Weusedthistrickinimplementingoneof thealgorithmsinSection 1.1. 2. a. Forasortedarray, thereisaspectacularlyefficientalgorithmyoual- mostcertainlyhaveheardabout. b. Unsuccessfulsearchescanbemadefaster. 3. a. Push(x)putsxonthetopofthestack,popdeletestheitemfromthe topofthestack. b. Enqueue(x)addsxtotherearofthequeue,dequeuedeletestheitem fromthefrontofthequeue. 4. Just use the definitions of the graph properties in question and data struc- turesinvolved. 5. Therearetwowell-knownalgorithmsthatcansolvethisproblem. The firstusesastack, thesecondusesaqueue. Althoughthesealgorithms arediscussedlaterinthebook,donotmissthischancetodiscoverthem byyourself! 6. The inequality h ≤ n−1 follows immediately from the height’s definition. Thelowerboundinequalityfollowsfrominequality2 h+1 − 1 ≥n, which canbeprovedbyconsideringthelargestnumberofverticesabinarytree ofheighthcanhave. 7. You need to indicate how each of the three operations of the priority queue willbeimplemented. 8. Because of insertions anddeletions, usinganarrayof the dictionary’s elements(sortedorunsorted)isnotthebestimplementationpossible. 9. Youneedtoknowaboutthepostfixnotationinordertoansweroneof thesequestions. (Ifyouarenotfamiliarwithit,findtheinformationon theInternet.) 10. Thereareseveral algorithmsforthisproblem. Keepinmindthatthe wordsmaycontainmultipleoccurrencesofthesameletter. 23 SolutionstoExercises1.4 1. a. Replacetheithelementwiththelastelementanddecreasethearray sizeby1. b. Replacetheithelementwithaspecialsymbolthatcannotbeavalue ofthearray’selement(e.g., 0foranarrayofpositivenumbers)tomark theithpositionasempty. (Thismethodissometimescalledthe“lazy deletion”.) 2. a. Usebinarysearch(seeSection4.3if youarenot familiar withthis algorithm). b. Whensearchinginasortedlinkedlist, stopas soonas anelement greaterthanorequaltothesearchkeyisencountered. 3. a. d push(a) push(b) b pop push(c) c push(d) c pop c a a a a a a b. enqueue(a) enqueue(b) dequeue enqueue(c) enqueue(d) dequeue a ab b bc bcd cd 4. a. Fortheadjacencymatrixrepresentation: i. Agraphis completeif andonlyif all theelements of its adjacency matrixexceptthoseonthemaindiagonal areequal to1, i.e., A[i, j]=1 forevery1 ≤ i, j ≤ n,i ,= j. ii. Agraphhas aloopif andonlyif its adjacencymatrixhas anele- mentequalto1onitsmaindiagonal,i.e.,A[i, i] = 1forsome1 ≤ i ≤ n. iii. An(undirected, withoutloops)graphhasanisolatedvertexif and onlyifitsadjacencymatrixhasanall-zerorow. b. Fortheadjacencylistrepresentation: i. Agraphis complete if andonlyif eachof its linkedlists contains alltheotherverticesofthegraph. ii. A graph has a loop if and only if one of its adjacency lists contains the 24 vertexdefiningthelist. iii. An(undirected, withoutloops)graphhasanisolatedvertexif and onlyifoneofitsadjacencylistsisempty. 5. Thefirstalgorithmworksasfollows. Markavertextoserveastheroot ofthetree, makeittherootofthetreetobeconstructed, andinitialize astackwiththisvertex. Repeatthefollowingoperationuntil thestack becomesempty: Ifthereisanunmarkedvertexadjacenttothevertexon thetoptothestack, marktheformervertex, attachitasachildofthe top’svertexinthetree, andpushitontothestack; otherwise, popthe vertexoffthetopofthestack. Thesecondalgorithmworks as follows. Markavertextoserveas the rootofthetree, makeittherootofthetreetobeconstructed, andini- tializeaqueuewiththisvertex. Repeatthefollowingoperationsuntil the queuebecomesempty: Ifthereareunmarkedverticesadjacentto the vertex at the front of the queue, mark all of them, attach them as children tothefrontvertexinthetree,andaddthemtothequeue;thendequeue thequeue. 6. Sincetheheightisdefinedasthelengthofthelongestsimplepathfrom the tree’s root to its leaf, such a pass will include no more than n vertices, whichisthetotalnumberofverticesinthetree. Hence,h ≤ n − 1. Thebinarytreeofheighthwiththelargestnumberofverticesisthefull treethathasallitsh + 1levelsfilledwiththelargestnumberofvertices possible. The total number of vertices in such a tree is h l=0 2 l = 2 h+1 −1. Hence,foranybinarytreewithnverticesandheighth 2 h+1 − 1 ≥ n. Thisimpliesthat 2 h+1 ≥ n + 1 or, after takingbinarylogarithms of bothhandsides andtakinginto accountthath + 1isaninteger, h + 1 ≥ ¸log 2 (n + 1)|. Since ¸log 2 (n + 1)| = ¸log 2 n| + 1(seeAppendixA),wefinallyobtain h + 1 ≥ ¸log 2 n| + 1orh ≥ ¸log 2 n|. 7. a. Insertioncanbeimplementedbyaddingthenewitemafter thear- ray’slastelement. Findingthelargestelementrequiresastandardscan 25 throughthearraytofinditslargestelement. Deletingthelargestele- ment A[i] can be implemented by exchanging it with the last element and decreasingthearray’ssizeby1. b. Wewill assumethat thearrayA[0..n − 1] representingthepriority queue is sorted in ascending order. Inserting a new item of value v can be donebyscanningthesortedarray,say,lefttorightuntilanelementA[j] ≥vortheendof thearrayisreached. (Afasteralgorithmforfinding aplaceforinsertinganewelementisbinarysearchdiscussedinSection 4.3.)In the former case, the new item is inserted before A[j] by first mov- ingA[n − 1], ..., A[j]onepositiontotheright;inthelattercase,thenew itemissimplyappendedafterthelastelementofthearray. Findingthe largestelementisdonebysimplyreturningthevalueofthelastelement of the sorted array. Deletionofthe largest elementisdone bydecreasing thearray’ssizebyone. c. Insertionof anewelement isdonebyusingthestandardalgorithm forinsertinganewelementinabinarysearchtree: recursively, thenew keyis insertedinthe left or right subtree dependingonwhether it is smallerorlargerthantheroot’skey. Findingthelargestelementwill requirefindingtherightmost element inthebinarytreebystartingat therootandfollowingthechainoftherightchildrenuntilavertexwith norightsubtreeisreached. Thekeyof thatvertexwill bethelargest element in question. Deleting it can be done by making the right pointer ofitsparenttopointtotheleftchildofthevertexbeingdeleted;. ifthe rightmostvertexhasno leftchild,thispointerismade “null”. Finally,if the rightmost vertex has no parent, i.e., if it happens to be the root of the tree,itsleftchildbecomesthenewroot;ifthereisnoleftchild,thetree becomesempty. 8. Use abit vector, i.e., anarrayonnbits inwhichthe ithbit is 1if theithelementof theunderlyingsetiscurrentlyinthedictionaryand 0otherwise. Thesearch, insertion, anddeletionoperationswill require checkingorchangingasinglebitofthisarray. 9. Use: (a) apriorityqueue; (b) aqueue; (c) astack(andreversePolish notation–acleverwayof representingarithmetical expressionswithout parentheses,whichisusuallystudiedinadatastructurescourse). 10. Themoststraightforwardsolutionistosearchforeachsuccessiveletter ofthefirstwordinthesecondone. Ifthesearchissuccessful,deletethe firstoccurrenceoftheletterinthesecondword,stopotherwise. Another solutionis tosort theletters of eachwordandthencompare 26 theminasimpleparallelscan. Wecanalsogenerateandcompare“letter vectors”of thegivenwords: V w [i] = the number of occurrences of the alphabet’s ith letter in the word w. Suchavectorcanbegeneratedbyinitializingall itscomponentsto 0 and thenscanning the word and incrementing appropriate letter counts inthevector. 27