=========================preview======================
(COMP271)1998Fall_Final.pdf
Back to COMP271 Login to download
======================================================
TheHongKongUniversityofScience&Technology
DepartmentofComputerScience
COMP271,Section2:DesignandAnalysisofAlgorithms
.nalexamination

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.
(b)Whatistopologicalsort.Willthetopologicalorderingofadirectedacyclicgraphbe unique.Giveanexampletoillustrateyouranswer.
(d)Discusshowsomereal-lifeproblemthatcanbemodeledasminimumspanningtree problem.
(f)DoesPNP.Argueyouranswerbrie.y.
(h)Givethede.nitionsofintractableproblemsandNP-Completeproblems,comparethe di.erencebetweenthem.
(a)Whatisthedi.erencebetweensingle-sourceshortest-pathproblemandall-pairsshortest-pathproblem.
(b)GiventhefollowinggraphG.(VE),startwithsource1,tracetheactionsofDijkstra's algorithm.Foreachiteration,writedownthedvalueofeachvertex.
4


D(k)

duringeachiteration.
(a)Whatisthemeaningofpre.x-freecode.Whyisitsoimportanttoensuretheproperty ofthepre.x-freecodes.
(b)Hu.maninventedagreedyalgorithmtoconstructanoptimalpre.x-freecodecalled Hu.mancode.WhatisbeingoptimizedinHu.mancodingprocedure.Arguebrie.ywhy Hu.mancodeispre.x-free.
0

AnindependentsetofagraphG.(VE)isasubsetVVofverticessuchthateachedge
0

inEisincidentinatmostonevertexinV.Theoptimizationversionoftheindependent setproblemisto.ndamaximum-sizeindependentsetofG.
(a)Findthemaximum-sizeindependentsetofthefollowinggraph.
c
db

e
f

(b)Whatistherelateddecisionversionfortheindependentsetproblem.
(Hint:Reducefromthecliqueproblem.)
GiveanO(n2)dynamicprogrammingalgorithmwhich.ndsthelongestmonotonically increasingsubsequenceofasequenceofnnumbers.Youralgorithmshouldbeself-contained, i.e.,itshouldnotcallanyalgorithmasasubroutine.Analyzetherunningtimeofyour algorithm.
Inotherwords,thealgorithmshould.ndthelargestsubsetofthesequencesuchthateach successivenumberisgreaterthanitspredecessor.Fortheinputsequence152736, thealgorithmshouldproduce1236.
(Youneednottoarguethecorrectnessofyouralgorithm.)