=========================preview======================
(COMP271)1998Fall_Midterm_SOL.pdf
Back to COMP271 Login to download
======================================================
TheHongKongUniversityofScience&Technology
DepartmentofComputerScience
COMP271,Section2:DesignandAnalysisofAlgorithms
mid-termexamination
Date:12:00-2:00p.m.,1November,1998.
Venue:LTD

Studentname: StudentID: e
mail:
Question
1
2
3
4
Total
Grade
/12pts
/12pts
/12pts
/12pts
/48Pts
Problem1:
Answerthefollowingshortquestions.
(a)Discussbrie.ywhyacorrectalgorithmisnotalwaysdesirable.
(b)Intheclass,wetalkedabouttheMax-DominanceProblem.Givenasetofpoints P.fp1.p2.:::.png,eachrepresentedbyitsxandycoordinates,wewantto.ndasetof maximalpointsofP.Amaximalpointpihasthepropertythatitisnotdominatedbyany otherpointinP.
Arguebrie.ywhyifweoutputthemaximalpointsinascendingorderwithrespecttox, thenwewillhavetheycoordinatesbedescendingwithrespecttoy.
(c)Giveonenameofanylineartimesortingalgorithm.Discussbrie.ytheassumptionfor inputnumbers.
(d)Discusshowonereal-lifeproblemcanbemodeledasagraphproblem.
Problem2:
(a)ConsiderthefollowingdigraphG.(V.E).TraversethefollowingdigraphusingDepth-Firstsearchstartingfromvertexa.Youmustusetheadjacentlistrepresentationgiven below.Showthetreestructure(boththeedgeclassi.cationandtimestamps)produced duringthesearchprocess.
a:!d.c.b b:!c.e c:!d.e d:!f.g e:!g f:!g.e g:!.(empty)

(b)Whatistopologicalsortofadirectedacyclicgraph.Whatisthetopologicalsortof thegraphinpart(a).
(c)Mr.CarelessisastudentoftheclassCOMP271.Heclaimsthathecanproducea topologicalsortofanydirectedgraph.Discussbrie.yifheiscorrectorheiswrong.
Problem3:
Thisquestionisaboutminimumspanningtreeproblem.Givenanconnected,undirected graphG.(V.E),aspanningtreeisanacyclicsubsetofedgesT.Ethatconnectsall theverticestogether.Assumingthateachedge(u.v)ofGhasanumericweightorcost, w(u.v),wede.nethecostofspanningtreeTtobethesumofedgesinthespanningtree
X
w(T).w(u.v):
(uv)2T
Aminimumspanningtree(MST)isaspanningtreeofminimumweight.
(a)InclasswestudiedtheKruskal'salgorithmtosolvetheMSTproblem.Writedown thepseudocodeofKruskal'salgorithm.Discussbrie.ytheideaofKruskal'salgorithm.
(b)GiventhefollowinggraphG.(V.E).RunKruskal'salgorithmonthegraph.Youonly needtoshowthe.nalminimumspanningtree,andcomputethecorrespondingweightof thetree.
7 103
7
2 7 5 8 2 6

5
5
87
6

(c)ThetrickypartofKruskal'salgorithmishowtodetectwhethertheadditionofanedge willcreateacycle.OnewaytosolvetheproblemistousethedisjointsetUNION-FIND datastructure.Thisdatastructuresupportsthreeoperations:
Create-Set:Createasetcontainingasingleitem.
Find-Set:Findthesetthatcontainsagivenitem.
Union:Mergetwosetsintoacommonset.
DiscusshowUNION-FINDdatastructurecanhelpustodetectwhethertheadditionofan edgewillcreateacycle.
Problem4:
(a)YouaregiventhefollowingdigraphG.(V.E).Startwithsources,tracetheactions ofDijkstra'salgorithm.Findtheshortestpathsfromsourcestoalltheothervertices.In eachstep,youneedtoshowthedvalueofeachvertex.

5

(b)LetG.(V.E)beaweighted,directedgraphsuchthattheweightsoftheedgesare nonnegativeandaretakenfromthesetf0.1.2.:::.