=========================preview======================
(COMP271)1998Fall_Final_SOL.pdf
Back to COMP271 Login to download
======================================================
TheHongKongUniversityofScience&Technology
DepartmentofComputerScience
COMP271,Section2:DesignandAnalysisofAlgorithms
.nalexamination(ANSWER)
Date:12:30-3:30p.m.,12December,1998.
Venue:LG1SportsHallLobby
Studentname: StudentID: e
mail:
Question
1
2
3
4
5
Total
Grade
/24pts
/12pts
/8pts
/12pts
/8pts
/64pts
(a)Mr.Carelessclaimsthattherunningtimeofdepth-.rstsearchonagraphGcanalways bedoneinO(jVj+jEj)time,whichisindependenttotheinputgraphrepresentation. Discusshisclaim.
Iftheinputgraphisrepresentedbyadjacentmatrix,thentherunningtimeisO(jVj2).
(b)Whatistopologicalsort.Willthetopologicalorderingofadirectedacyclicgraphbe unique.Giveanexampletoillustrateyouranswer.
AtopologicalsortofaDAGisalinearorderingoftheverticesoftheDAGsuchthatfor eachedge(u.v),uappearsbeforevintheordering.Notethatingeneral,theremaybe manylegaltopologicalordersforagivenDAG.
Dijkstra'salgorithmmaintainsanestimateoftheshortestpathforeachvertex,callthis d[v].Wewillalwaysrequirethatd[v]equalsthecostofsomeknownpath.Asthealgorithm isrunning,itattemptstoupdated[v]foreachvertexinthegraph,untilallthed[v]values convergetothetrueshortestdistances.Theprocessbywhichanestimateisupdatedis calledrelaxation.
(d)Discusshowsomereal-lifeproblemthatcanbemodeledasminimumspanningtree problem.
Acommonproblemincommunicationsnetworksandcircuitdesignisthatofconnecting togetherasetofnodes(communicationsitesorcircuitcomponents)byanetworkofminimal totallength(wherelengthisthesumofthelengthsofconnectingwires).
Dynamicprogrammingapproachdividestheproblemintorecursivesubproblems(asin divide-and-conquer)butunlikedivide-and-conquerthereisoftenoverlapbetweenthesub-problems.
(f)DoesP.NP.Argueyouranswerbrie.y.
PisasubsetofNP(i.e.,P.NP).Sincewecansolveaprobleminpolynomialtime,then wecancertainlyverifythecorrectnessofthesolutioninpolynomialtime(orelsewecan't solvetheprobleminpolynomialtime).
Cook'stheorem:SATisNPcomplete. Supposewedon'thaveCook'stheorem,accordingtode.nitionofNP-complete,ifwewant toprove.isNP-complete,wehavetoreduceEVERYprobleminNPto..Butthereare in.nitelymanysuchproblems,wehavenohopetodothis.ThankstoCook'stheorem,we cannowtakeSATisNP-completeanddeducefromSATtoprove.isNP-complete.
(h)Givethede.nitionsofintractableproblemsandNP-Completeproblems,comparethe di.erencebetweenthem.
IntractableProblems:Noalgorithmcanexistthatrunsinpolynomialtime.
NP-CompleteProblems:Thereexistalgorithmsfortheseproblems,buttheyrunintime exponentialintheinputsize.Peoplesuspectthatnopolynomial-timealgorithmsexistfor theseproblems.
Themaindi.erencebetweenthemiswebelieveNP-completeproblemsareintractable,but nobodyhascomeupwithaproofyet.
(a)Whatisthedi.erencebetweensingle-sourceshortest-pathproblemandall-pairsshortest-pathproblem.
GivenagraphG.(V.E),thesingle-sourceshortest-pathproblemonlyrequirestheshortest pathfromagivensourcevertexs2Vtoeveryvertexv2V.Butinthecaseofall-pairs shortest-pathproblem,weneedto.ndtheshortestpathfromutovforeverypairof verticesuandv2V.
(b)Gi