Unformatted text preview:

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

UNC-Chapel Hill COMP 122 - Final Exam

Documents in this Course
Load more
Download Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?