COMP122 AlgorithmsandAnalysis Fall2004 FinalExam Thursday De 16 2004 ClosedBook ClosedNotes Thisexamhasthreepages Don tforgettowriteyournameorIDandpledgeontheexamsheet 1 12points Forea hproblem writeintheblankallelementsFoftheset f cid 2 O o cid 10 gsu hthatthestatementf x F g x isa orre tstatement oftheasymptoti relationshipbetweenfandg Thusiff x cid 10 g x and f x cid 2 g x andf x O g x aretheonlythreevalidasymptoti relationshipsbetweenfandg write cid 10 cid 2 Ointheblank Hint f x g x meansfgrowsfasterthang inthelimit f x o g x means fgrowsslowerthang inthelimit cid 2 meanstheygrowthesame roughly speaking a f x x2 1 g x 2x2 x b f x 2x 4x2 g x 3x x 1 f x x3 g x 3x 2 d f x 2x 1 g x 4log2x cid 0 1 e f x 2px g x 3logx f f x 3log2x g x 2log3 2x 2 10points Solvethere urren eT n 3T n 3 cid 2 n Indi atewhi h solutionmethodyouused 3 4points Whatistheasymptoti expe tedtimeforqui ksort 4 4points Whatistheasymptoti worst asetimeboundforqui ksort 5 4points Whatistheasymptoti worst asetimeboundforheap sort 6 4points Whatistheasymptoti expe tedtimeforheapsort 1 7 12points a Giveanupperboundontheheightofaredbla ktree havingninternalnodes b Ifaredbla ktreehasbla k height12 whatisitsmaximumheight Ifaredbla k treehasbla kheight12 whatistheminimumnumberofinternalnodesin thetree 12points a Howmany omparisonsareneededto cid 12 ndthemaxi 8 mumofnelements Giveanasymptoti bound b How many omparisonsareneededto cid 12 ndthemaximumandse ondlargestofn Howmany om elements Giveanasymptoti bound parisonsareneededto cid 12 ndthemedianofnelements Giveanasymptoti bound 9 10points Forhashingbythedivisionmethod whi hofthefollowingis thebestvalueforthemodulusm Giveabriefjusti cid 12 ationforyouranswer a 256 b 128 10 d 181 10 6points Ifahashtablehassize200andthereare150elementsinthe table whatistheloadfa tor ba b aba 11 10points Fillintheabovetablewiththenumbers i j andthe arrowsusedinthelongest ommonsubsequen ealgorithm Showthelongest ommonsubsequen e 12 10points Supposethesymbolsa b d e fareusedwiththeprobabilities 1 21 2 21 3 21 4 21 5 21 and6 21 respe tively Constru tanoptimal pre cid 12 x ode aHu cid 11 man ode forthesesymbols 2 ab 13 6points Supposethatadire tedgraph ontainsthefollowingedges Listthestrongly onne ted omponents f a b b a d e e f f g g d h i i j j k k h l m m n n l f i e j b k l g 14 5points Forea hofthefollowingproblems giveanasymptoti time boundforthebestknownalgorithms intermsofthenumberVofverti es inthegraphandthenumberEofedges a Todetermineifanundire tedgraphis onne ted b To cid 12 ndthestrongly onne ted omponentsofadire tedgraph Todetermineifadire tedgraphhasa y le d Givenadire tedgraphGandavertexxofG to cid 12 ndthelengthsofthe shortestpathsfromxtoeveryothervertexinG e To cid 12 ndthe onne ted omponentsofanundire tedgraph 15 10points Indi atean undire ted edge x y havingweightzby x y z ConsiderthegraphGhavingtheedgesf a f 1 f 2 b d 1 d e 4 d f 3 g SupposethesetofedgesA ontainsjusttheedge b d 1 a Whi hedgewouldbeaddedtoAnextinKruskal smethod b Whi hedgewouldbeaddedtoAnextinPrim smethod 16 6points Forthefollowingquestions givethebestmethodtouseto solvethesingle sour esortestpathsproblemonthekindofweighted dire ted graphspe i cid 12 ed Choi es A Bellman FordB DijkstraC Analgorithmthat issimplerandfasterthanDijkstra salgorithmonthespe i cid 12 edkindofgraphs a Forgraphswithnonegativeweightedges b Forgraphswithnonegativeweight y les Fordire teda y li graphs 17 10points EXTRACREDIT Compute1Xj 0j3j 18 10points EXTRACREDIT Solvethere urren erelationT n 2T pn cid 2 logn 19 10points EXTRACREDIT 10points a Howmany omparisonsare neededto cid 12 ndthemaximumandminimumelementsofasetofsixelements b Howmany omparisonsareneededto cid 12 ndthese ond Justifyyour largestelementofasetofeightelements answersbrie cid 13 y 3
View Full Document