=========================preview======================
(MATH132)final99F.pdf
Back to MATH132 Login to download
======================================================
Name: ClassSection:
IDNo. TutorialSection:

Problem1(16)2(16)3(10)4(10)5(15)6(14)7(10)8(9)Total(100) Score
1.Forthefollowingmultiplechoicequestions,pleasechooseoneandonlyoneanswer.(4ptseach)
(a)Whichofthefollowingisanin.nitecountableset. i.Thesetofrealnumbers. ii.Thesetofcomplexnumbers. iii.Thesetofirrationalnumbers. iv.Thesetofprimenumbers. v.Thesetofallnumbersappearedsomewhereinabookinourworldatthemoment. (b)AsubsetSofthesetf:^_!$gissaidtobeadequateifeverysymboliclogicsentencewithout quanti.erscanbeexpressedbythesymbolsofS.WhichofthefollowingsetsisNOTadequate. i.f^_!$g ii.f:_!$g iii.f:^!$g iv.f:^_$g v.f:^_!g (c)LetG.(VE)beasimplegraph,i.e.,Ghasnoloopsandmultipleedges.Whichofthefollowing iscorrect. i.IfGhasnocycles,thenGisatree. ii.IfjEj.jVj;1,thenGisatree. iii.Ifthereexistsauniquepathbetweeneverypairofdistinctvertices,thenGisatree. iv.Ghasatleasttwoleaves. v.Noneoftheabove. (d)Whichoneofthefollowingisthebestlowerboundfortheheightofanm-ary(m.2)treewithn leaves. i.lognm ii.logmn iii.nlogmn
iv.n
v.Noneoftheabove.

2.(4ptseach.noneedreason)
(a)Whatisthechromaticpolynomialofatreewithn(.2)vertices.
Answer:

(b)Howmanywaysaretheretoput10identicalballsto3distinctboxessothateachboxcontainsat leastoneball. Answer:
(c)Whatistheprobabilityofselecting5cardsfromapokerof52cardssothatthereareexactly3red cardsand2blackcards. Answer:
(d) Given3national.ags,3HKSAR.ags,and2UST.ags.onasinglepolevertically. Answer: Inhow m a n y w ayscanthe5.agsbeput
1

(p) (b)Letf(n).3f(n2)+3andf(1).3,wheren.2k ,k.12....Findf(n).(5pts)

4.Letfg:R;f0;1g;!R;f0;1gbefunctionsde.nedbyf(x).x 1andg(x).;(x+1)respectively.
(a)Chooseoneandonlyoneofthefollowing:(3pts) i.Onlyfisaone-to-onecorrespondence. ii.Onlygisaone-to-onecorrespondence. iii.Bothfandgareone-to-onecorrespondences. iv.Noneofthemisaone-to-onecorrespondence. (b)IsthesetF.fh1.h2.....hk:h1h2...hkareeitherforgk.1ga.niteset.Ifso,listall membersofF.(7pts)
(a)IsRasymmetricrelationonV.Ifso,drawa(undirected)graphGfortherelationR. (b)DoesGhaveanEulercircuitorEulerpath.Ifso,.ndanEulercircuitorEulerpath.
(c)DoesGhaveanHamiltoncycle.Ifso,.ndaHamiltoncycle. (d)Drawthe(undirected)graphfortherelationR.R.
(e)Let.beabinaryrelationonVde.nedbya.bifandonlyifa;bisamultipleof4.Is.an
equivalencerelationonV.Ifso,.ndthesetV.ofequivalenceclassesanddrawthequotient
graphG..

(b)ApplyPreorderandPostordermethodstovisittheverticesoftherootedtree.(4pts)

(c)Findaminimalspanningtreeoftheweightedgraph.(4pts)

13 14

8.DesignaDeterministicFiniteAutomatonMonalphabetset..fabgthatacceptsallstringswhich beginwithaaandendwithbb.(9pts)