第1題Inthevideo,ProfessorMaintroducedabriefhistoryofmathematics,fromthebasicmathematicsinthe16thcenturythroughanalysis,whichinvolvesadvancedmathematicsandlinearalgebra,allthewaytosettheoryandthemathematicsoftoday.Thesebasicallycorrespondwiththemathematicsfromhighschool,universityandpostgraduateeducation.Sowhichofstageofmathematicsareyouat?(thisquestiondoesnotcounttowardsyourgrade)AbasicmathematicsBanalysismathematicsCmodernmathematicsDmanyyearssincelasthavingstudiedmathematicsEelse正確答案：E第1題AT-shirtwillbeprintedwithamagicsquareofsize3.Howmanydifferentprintsarepossible?A1B2C6D8SufferingParchmentRoll--Homework第1題Inthehistoryofcombinatorics,whosemanuscriptonstomachionswasrecordedonparchment,andhasrecentlybeensolvedbyscientistsusingmoderntechnology?AEulerBLeibnizCArchimedesDGaloisTalkingAboutCombinatorialMathematics--IsYourP第1題Accordingtothevideo,whichpicturesofthebellowingcanbesetasthepasswordofandroidphone?(multiplechoices)ABCDEF正確答案：ACFBrute-forceEnumarationORAbstractConversion--Homework第1題CombinatorialMathematicsisanusefulclass,pleasechoosethereasonyoulearnit:ApersonalinterestincombinatoricsBtoprepareforpre-postgraduateexamsCforthehighschoolexamsDarequiredcourseinuniversityEtoentercompetitionsininformaticsFasjobinterviewpreparationGwanttogetacertificateofTsinghuaUniversityHcuriousaboutaMOOCtaughtbyafemaleprofessorfromTsinghuaIelse正確答案：IHomework1第1題Thefigurebelowshowsapartial4X4matrix，istheresomewayoffillinguptherestoftheomittedentriestoproduceamagicsquareofsize4usingnumbers1-16？AnoByes第2題Whichnumberbelow,ifusedasthemagicsum,allowsustoconstructmagicsquaresofsize3,usingonlynon-repeatedpositiveintegers?A12B23C18D34E20CombinatorialtripofaPingpongball--Permutation第1題Pleaseinputthespecificnumericalvalues：C(n,0)=____P(n,0)=____C(4,5)=____CombinatorialtripofaPingpongball--VariousPer第1題EightDiagram(Bagua)contains____typesofdifferentarrangementways.Pleasecalculatetheexactnumber第2題Thecoefficientnumberofa2b2c2intheexpandedequationof(2a+b+c)6is____.PleasecalculatetheexactnumberCombinatorialtripofaPingpongball--DifferentK第1題Combinationnumberofputting5ballsinto4boxes：1)5differentballs,4differentboxes,thenumberofballsinsideaboxisnotlimited,allowsemptybox,andcontainstotal____differentsolutions.【Pleasecalculatetheexactnumber】2)5identicalballs,4differentboxes,allowsemptybox,andcontainstotal____differentsolutions.【Pleasecalculatetheexactnumber】CombinatorialtripofaPingpongball--Permutation第1題PleasecalculatehowmanydifferentsongsaretherewhichcanbemadefromthechangeringingintheTrinityChurch?(12bells,eachringonceandindifferentorders)Pleasecalculatetheexactnumber,youmayuseacalculator____Homework2第1題InaGoldenFraudcardgame(ApolularpokergameinChina),useadeckofcardswhichhavejokersremoved,intotalthereare4shapeswith52cards,playerscompetetheirwin/losebythe3cardsinthehands,therearedifferentcardpatternsintherules:Leopard:3identicalcards,forexampleAAAor222.ShunJin(Flush):Straightwithidenticalshape,suchasSpade456orHeart789.GoldenFlower:Identicalshape,non-straight.Forexample,Spade368andDiamond145.Straight:Straightwithdifferentshape,forexample,Spade5Heart6Diamond7.ThesmalleststraightisA23.AndthelargeststraightisQKA.Pair:2identicalcards,suchas223and334.Random:3cardswhichdonotfallunderanycardpattern.Special：235withdifferentshapes.（Duetothatdifferentareamaycontaindifferentcardrules,itisnotbeingconsideredunderthisquestion）Then,ifweconsidertheprobabilitiesforthosepatterns,howtoorderthem?:ALeopard<Flush<GoldenFlower<Straight<Pair<RandomBLeopard<Flush<Straight<GoldenFlower<Pair<RandomCFlush<Leopard<GoldenFlower<Straight<Pair<RandomDLeopard>Flush>GoldenFlower>Straight>Pair>RandomEFlush<Leopard<Straight<GoldenFlower<Pair<Random正確答案：EGeneratingFunction&CountingRules--Homework第1題InG(x)=a0+a1x+a2x2+..+anxn+?,generatingfunctionisconcernedof:AVariablexBTargetfunctionG(x)CCoefficientai第2題Thedefinitionofgeneratingfunctionisraisedby?ABernoulliBLaplaceCEulerGeneratingFunction--SimpleApplicationOfGenerat第1題Thereare3piecesof1gramweight,4piecesof2gramsweight,2piecesof4gramsweight,howmanydifferentwaystoweighthevalueof6-gram?____正確答案：:4FerrersDiagram--Homework第1題Thepartitionnumberofpositiveintegernbeingpartitionedintoseveralpositiveintegers,inwhichthelargestintegerisk,equalstothepartitionnumberofpositiveintegernbeingpartitionedintokpositiveintegers.ATrueBFalseHomework3第1題GiventherecurrencerelationofFibonaccisequenceisF(n)=F(n-1)+F(n-2),setG(n)=F(2n),thentherecurrencerelationofG(n)is：G(n)=___G(n-1)+___G(n-2)+____G(n-3)Pleasechoosethecoefficientvalue：A1,1,1B1,1,0C3,1,0D3,1,1E3,-1,0F3,-1,1正確答案：E第2題GivengeneratingfunctionG(x)=3+78x1?3x?54x2,findthecorrespondingsequence{an}A{an}=7?(?9)n+4?6nB{an}=7?9n?4?6nC{an}=7?9n?4?(?6)nD{an}=7?(?9)n?4?6nE{an}=7?(?9)n+4?(?6)nF{an}=7?(?9)n?4?(?6)n第3題Positiveintegernispartitionedintoseveralpositiveintegers(1,2,3，…).Ifrepetitionisnotallowedanddoesnotconsiderthepartitionordering,thenthepartitionnumberisequaledtowhichofthefollowings?AThesolutionnumberforputtingnidenticalballsintonidenticalboxes(allowemptybox)BThenumberofpartitionstopartitionpositiveintegernintoevennumbers(2,4,6，…)withoutconsiderationoforderingandtherepetitionisallowed.CThenumberofpartitionstopartitionpositiveintegernintooddnumbers(1,3,5，…)withoutconsiderationoforderingandtherepetitionisallowed.DThesolutionnumberofputtingnidenticalballsintondistinctboxes(allowemptybox)FibonacciSequence--Homework第1題Whichequationofthefollowingisincorrect?AF12+F22+...+Fn2=FnFn+1BF1+F2+F3+...+Fn=Fn+2?1CF1+F3+F5+...+F2n?1=F2n+1LinearHomogeneousRecurrenceRelation--Applicatio第1題F1002?F101F99=____noticethatF1=F2=1正確答案：:-1LinearHomogeneousRecurrenceRelation--Homework第1題Therecurrencerelationofsequence{an}isan?2an?1=4an?2?5an?3sothecharacteristicequationisAx3?2x2+4x?5=0Bx3?2x2?4x+5=0C5x3?4x2?2x+1=0D?5x3+4x2?2x+1=0HomeworkOfWeek4第1題Thegeneratingfunctionofsequence{an}is11?x+x2,soit'srecurrencerelation(whenn≥2)is:Aan?an?1?an?2=0Ban+an?1?an?2=0Can+an?1+an?2=0Dan?an?1+an?2=0第2題Givenan=an?12an?23,a0=1,a1=2,thentheexpressionofanisA23n+3(?1)n4B22n?1C23n+(?1)n2D23n?(?1)n4MagicalSequences--CatalanNumbers第1題Therearesixpeopleinalibraryqueuingup,threeofthemwanttoreturnthebook“InterviewingSkills”,and3ofthemwanttoborrowthesamebook.Ifatthebeginning,allthebooksof“InterviewingSkills”areoutofstockinthelibrary,howmanywayscanthesepeoplelineupsothatthosethreepeoplecouldborrowthebooks?____正確答案：:180ExponentialGeneratingFunctions--Homework第1題Whatistheexponentialgeneratingfunctionofthesequence{1,k,k2,k3,...}AexB11?xCekxD11?kxMagicalSequences--Derangements第1題Thereare5fathersandeachfatherhasakidwithhim(10peopleintotal).TheyaretakingpartinaTVshowcalled“Dad,wherearewegoing?”Inthisprogramthereisagamecalled"ExchangetheFather",afatherhastotakeakidwhoisnothisownchild.Sohowmanydifferentgroupscanbemadewiththisconstraintinmind?____正確答案：:44MagicalSequences--StirlingNumbers第1題HowmanywayscanyoudividefourpeopleABCandDintotwogroups?____正確答案：:7MagicalSequences--HomeworkofWeek5第1題Placendistinctballsinmidenticalboxeswherenoboxisempty.ThedifferentwaystodosoisknownastheStirlingnumbersofthesecondkindS(n,m).SowhatdoesS(n,n-1)equal?AC(n,1)BC(n,2)CC(n,3)DC(n,4)第2題Using5numbers1，2，3，4,5tofillin1x6grids,eachgridisfilledwithonedigit.Ifthereareoddnumberofgridsthathave1writtenonthem,andanevennumberofgridswith2,thenhowmanyarrangementstherefor1*6grids?____正確答案：:3906Inclusion-ExclusionPrincipleAndPigeonholePrinc第1題Given|A|=10,|B|=7,|A∪B|=10,then|A∩B|=____正確答案：:7Inclusion-ExclusionPrincipleAndPigeonholePrinc第1題Isthefollowingstatementtrueorfalse?Of3000people,atleast9shouldhavethesamebirthday?AtureBfalseInclusion-ExclusionPrincipleAndPigeonholePrinc第1題Thereisapositiveinteger,dividedby2theremainderis1;dividedyby3theremainderis2,what'stheminimumnumbercansatisfythecondition?____正確答案：:5Inclusion-ExclusionPrincipleAndPigeonholePrinc第1題x1+x2+x3+x4=20,1≤x1≤6,0≤x2≤7,4≤x3≤8,2≤x4≤6,calculatethenumberofintegralsolutions.____正確答案：:96第2題Oftheintegernumbersfrom1to10000,howmanyareneitherasquarenoracubeofaninteger？____正確答案：:9883Q:MajorityElement第1題Givenanarbitraryinputarray,thecandidatefoundbyMooreandBoyer'sincrementalalgorithmisforsurethemajorityelement.Q:AlgorithmComplexity第1題WemeasuretherunningtimeofalgorithmsusingRAMmodel.AlgorithmAandBbothhave

nbasicoperations,butamongthoseoperationsalgorithmAcontainsmorememoryaccesswhichistimeconsumingonmostcomputersintherealworld.ThereforeundertheRAMmodel,wecansaythatalgorithmAhaslongerrunningtimethanB.Q:AsymptoticAnalysis第1題If

f(n)=Ω(g(n))then

g(n)=O(f(n))HomeworkofWeek7第1題FindthemajorityelementinthearraybelowbyexploitingMooreandBoyer'sincrementalalgorithm.Whatisthevalueofcountwhenthealgorithmterminates?Inputarray:XYXXZYXZXXYA0B1C2第2題Wecanprove

f(n)=O(g(n))tobefalsebygivingaspecificpairof

(n,c)

suchthat

f(n)>cg(n).第3題Forthefunctions,

nkandcn,whatistheasymptoticrelationshipbetweenthesefunctions?Assumethat

k≥1and

c>1

areconstants.Ankis

O(cn)Bnk

is

Ω(cn)Cnk

is

Θ(cn)第4題Thestatement,"TherunningtimeofalgorithmAisatleastO(n2)",ismeaninglessbecauseAThephrase"atleast"ismeaninglesswhendiscussingtherunningtimeofanalgorithm.BThephrase"atleast"andthebig-Onotationtogetherleadtoacontradiction.COnlythe

Θnotationismeaningfulwhendiscussingtherunningtimeofanalgorithm.Q:LoopInvariant第1題Aloopinvariantis:AAsetofvariableswhosevalueswon'tchangealltheway.BApropositionwhichisalwaystrueabouttheproblem,regardlessofwhattheactualalgorithmis.CApropositionwhichiskepttrueatthebeginningofeveryiterationandalsoattheendoftheloop.Q:InsertionSort第1題Whatifwechangedtheloopinvariantofinsertionsortinto:"Atthestartofeachiteration,A[1..j-1]isinsortedorder"?AThenewloopinvariantwouldnotremaintrueforeachinteration.BThenewloopinvariantwouldnotprovethecorrectnessofthealgorithm.CThiswouldmakenodifference.Q:2-ColorDutchNationalFlagProblem第1題Considerthealgorithmshownintheslideswhichsolvesthe2-colorDNFproblem.Ifwewanttokeeptherelativeorderwithinelementsofthesamecolor,isthealgorithmabletosatisfythisrequirement?AOnlywithinredelements.BOnlywithinblueelements.CBothsatisfied.DBothunsatisfied.HomeworkofWeek8第1題Whatisthebest-caseandworst-caserunningtimeofinsertionsort?AΘ(n)and

Θ(n2)BΘ(n2)

and

Θ(n3)CBoth

Θ(n2)第2題Bubblesortisalsoapopularsortingalgorithm.Itworksbyrepeatedlyswappingadjacentelementsthatareoutoforder.BUBBLESORT(A)

fori=1toA.length-1forj=A.lengthdowntoi+1ifA[j]<A[j-1]

exchangeA[j]withA[j-1]Comparedasymptoticallytoinsertionsort,bubblesort:Ahasshorterworst-caserunningtime.Bhasthesameworst-caserunningtime.Chasshorterbest-caserunningtime.Dhaslongerbest-caserunningtime.正確答案：BD第3題Whichofthefollowingstatementsarecorrectaboutinsertionsort?Notes:1.Asortingalgorithmissaidtobestableiftwoobjectswithequalkeysappearinthesameorderinsortedoutputastheyappearintheinputarraytobesorted.2.Auxiliaryspaceofanalgorithmistheextramemoryitconsumesapartfromtheinputandtheoutput.AInsertionsortisstable.BInsertionsortisunstable.CInsertionsortrequires

O(n)auxiliaryspace.DInsertionsortrequires

O(1)auxiliaryspace.正確答案：AD第4題LetA[1..n]beanarrayof

ndistinctnumbers.If

i<jandA[i]>A[j],thenthepair

(i,j)iscalledaninversionofA.Whatistherelationshipbetweentherunningtimeofinsertionsortandthenumberofinversionsintheinputarray?ANotrelated.BTherunningtimeofinsertionsortisalinearfunctionofthenumberofinversions.

CTherunnningtimeofinsertionsortisaquadraticfunctionofthenumberofinversions.Q:MergeSort第1題Merge2sortedlistsofsize

mandn,respectively.Thenumberofcomparisonsneededintheworstcasebythemergeprocedurewillbe:Am+nBm+n?1Cmax(m,n)Dmin(m,n)Q:Select:Partition第1題WhatistheresultafterapplyingthePARTITIONproceduretothearraybelow?Inputarray:74289510A54279810B42579810C54278910Q:Select:LinearTime第1題Wehaveknownthattheworst-caserunningtimeofinsertionsortisΘ(n2).Insertionsortisappliedtoevery5-elementgroupatline2inLinear-timeSELECT.WhydowesaythatthislinecontributesrunningtimeofΘ(n)?ABecausehereweusethebest-caserunningtimeofinsertionsort,

Θ(n).BBecause5isaconstantsotherunningtimeofinsertionsortona5-elementgroupisconsideredtobeΘ(1).CTheslidesmakeanerrorhere.Q:SubstitutionMethod第1題UsethesubstitutionmethodtosolvetherecurrenceT(n)=2T(n/2)+n:Assumethat

T(k)≤cklgkforsomesuitablelarge

candk<n.Finishtheproofyourself.Whatcondition

cshouldmeetiftheproofistohold?Ac≥0Bc≥1Cc≤1Q:RecursionTreeMethod第1題ConsidertherecurrenceT(n)=T(n/3)+T(2n/3)+O(n).Whichofthefollowingisclosesttotheheightoftherecursiontree?AlgnBlog3nClog32nQ:TheMasterMethod第1題Solvetherecurrence

T(n)=7T(n/3)+n2usingthemastermethod.Whichofthefollowingiscorrect?AT(n)=Θ(nlog37)BT(n)=Θ(nlog37lgn)CT(n)=Θ(n2)DThemastermethoddoesn'tapplybecausetheregularityconditionisnotsatisfied.HomeworkofWeek9第1題WhatvaluedoesthePARTITIONproceduregivenintheslidereturnwhenallelementsinthearray

A[p..r]havethesamevalue?ApBrCfloor((p+r)/2)第2題Trytosolvetherecurrence

T(n)=3T(n/3)+nlgnwiththemastermethodandchoosethecorrectanswer.AT(n)=Θ(n)BT(n)=Θ(nlgn)CT(n)=Θ(nlgnlgn)DThemastermethoddoesnotapply.第3題Usingthemastermethod,wecanshowthatthesolutiontotherecurrence

T(n)=4T(n/2)+nisT(n)=Θ(n2).Wecanalsoproveitbysubstitutionmethod.Whichofthefollowingshouldbeaproperassumptiontoholdourproof?AT(n)≤cn2BT(n)≤cn2?dCT(n)≤cn2?n第4題UsearecursiontreetogiveanasymptoticallytightsolutiontotherecurrenceT(n)=T(n?a)+T(a)+cn,where

a≥1and

c>0areconstants.AΘ(n)BΘ(nlgn)CΘ(n2)DΘ(n2lgn)Q:IndicatorRandomVariable第1題Xand

Yarerandomvariables.Underwhatcircumstancesdoes

E[X+Y]=E[X]+E[Y]hold?AOnlywhen

Xand

Yareindependent.BOnlywhen

X

and

Yarecorrelated.CTheequationalwaysholds.Q:HiringProblem第1題InHIRE-ASSISTANT,assumingthatthecandidatesarepresentedinarandomorder,whatistheprobabilitythatyouhireexactlyonetime?Whatistheprobabilityyouhireexactly

ntimes?A1n!,

1n!B1n,

1nC1n,

1n!D1n!,

1nQ:RandomizedAlgorihtm第1題Arandomizedintegersortingalgorithmshouldbelongto:ALasVegasBMonteCarloQ:RandomizedSelect第1題WhatistheworstcaserunningtimeofRANDOMIZED-SELECT?Suchworstcaseisdeterminedby...?AO(n);thedistributionoftheinputBO(n2);thedistributionoftheinputCO(n);theoutputofrandom-numbergeneratorDO(n2);theoutputofrandom-numbergeneratorHomeworkofWeek10第1題Useindicatorrandomvariablestocomputetheexpectedvalueofthesumof

ndice.A6nB3.5nC3nDn第2題Useindicatorrandomvariablestosolvethefollowingproblem,whichisknownasthehat-checkproblem.Eachof

ncustomersgivesahattoahat-checkpersonatarestaurant.Thehat-checkpersongivesthehatsbacktothecustomersinarandomorder.Whatistheexpectednumberofcustomerswhogetbacktheirhat?A12B1C1nDn2第3題WhenRANDOMIZED-SELECTruns,howmanycallsaremadetotherandom-numbergeneratorRANDOMintheworstcase?Whataboutinthebestcase?AΘ(n);

Θ(1)BΘ(n2);

Θ(1)CΘ(n);

Θ(n)DΘ(n2);

第4題Howmanypeopleatleastmusttherebeinaroom,suchthattheprobabilitythatsomeonehasthesamebirthdayasyoudoisnotsmallerthan

12?A76B183C253D314Q:MaximumSubarray第1題WhatistherunningtimeofMaximum-Subarray(th