=========================preview======================
(MATH132)final98F.pdf
Back to MATH132 Login to download
======================================================
Dept Math,HKUST,
Name: IDNo. ClassSection: TutorialSection:
ProblemScore 1(27) 2 (15) 3 (10) 4(10) 5 (10) 6(10) 7(10) 8(8) Total(100)

1.(27,each3pts)Fillintheblankspaceforeachofthefollowingproblems.
(a)Thenumberofarrangementsofrelementsfromasourceofnelementsis. (b)Thenumberofsubsetsofrelementsfromasetofnelementsis. (c)Thenumberofwaysofselectingrelementsfromasourceofnelementswithrepetitionis
. (d)Everytreewithmorethanonevertexhasatleastleaves. (e)ThenumberoflabeledsubgraphswithnverticesofthecompletegraphKnis.
(f)Thenumbercyclesoflength4inthecompletebipartitegraphKmnis.
(g)ThesixlettersA,A,B,B,B,andCcanbearrangedinways.
(h)Theheightofabinarytreewithnverticesisboundedby.

(i)ForsetAandB,ifAj.mandBj.n,thenthenumberofinjectivefunctionsfromAtoB is.
2.(15,each3pts)Pleasecircleoneandonlyonewhichiscorrect.
(a)i.Theimplication!cannotberepresentedby:,_,and^.
ii.Thenegation:cannotberepresentedby_,^,and!.
iii.Thedisjunction_cannotberepresentedby:,^,and!.
iv.Theconjunction^cannotberepresentedby:,_,and!.

v.Noneofabove. (b)i.Theuniversalquanti.er8cannotberepresentedby9and:. ii.Theexistentialquanti.er9cannotberepresentedby8and:. iii.Forthesentencesp(k)withk.1,p(1)^(8k.1p(k)!p(k+1))!(8k.1p(k))is atautology. iv.Noneofabove. (c)LetAandBbe.nitesetsandletf:A;!Bbeafunction. i.Iffisinjective,thenfmaynotbesurjective. ii.Iffisissurjective,thenfmaynotbeinjective. iii.Iffisinjectiveorsurjective,thenfisaone-to-onecorrespondence. iv.Noneofabove.
3.(10.5+5pts)
1
(b)Findth
k.12....

4.(10pts)UseEuler'sformulaforplanargraphstoshowthatthefollowinggraphisnotplanar.
eexplicitexpressionforthesequencef(n).4f(
)+8withf(1).8,wheren.4,


5.(10.3+3+4pts)LetKmndenotethecompletebipartitegraphKmn,i.e.,V(Kmn)canbedivided intotwodisjointunionoftwosetsV1,V2withjV1j.m,V2.n,andeveryvertexofV1isadjacent witheveryvertexofV2.
(a)ForwhatvaluesofmandnthatKmnhasanEulertour.
(b)ForwhatvaluesofmandnthatKmnhasaHamiltoncycle.
(c)ForwhatvaluesofmandnthatKmnisplanar.

6.(10.6+4pts) (a)(6pts)UseDepth-FirstSearchandBreadth-FirstSearchmethodsto.ndaspanningrooted followinggraph.Theorderoftheverticesisthealphabeticalorder.

(b)(4pts)Findaminimalspanningtreeforthefollowingweightedgraph.
2

22 5 2
7
def
18
15
14 1
g j
hi
21
13
20k
lm

3

8
9
23
12
16
6 19
n pq
7.(10.4+3+3pts)LetA1denotethesetofin.nitesequencesofnumbers0and1.LetRbea relationonA1 ,de.nedbyaRbifandonlyifthetwoin.nitesequencesaandbaredi.erentat only.nitenumberofpositions.
(a)ShowthatRisanequivalencerelation.
(b)ForeachequivalenceclassofR,isita.niteset,in.nitecountableset,oruncountableset. Pleasecircleone(noneedreason):FINITE,INFINITECOUNTABLE,UNCOUNTABLE.
(c)Isthesetofequivalenceclassescountable.Pleasecircleone(noneedreason):YESorNO.
8.(8pts)FindthelanguageL(M)ofthefollowingdeterministic.niteautomatonM,wherethe startingstateisats0andthe.nalstatesares3ands4.

b
3