UCSD CSE 101 - Homework#1 - D1837974

Home> Schools> University of California, San Diego> Computer Science & Engineering (CSE) > CSE 101> Homework#1

DOC PREVIEW

UCSD CSE 101 - Homework#1

School name University of California, San Diego

Course Cse 101- Design & Analysis of Algorithm

Pages 2

This preview shows page 1 out of 2 pages.

Save

View full document

Premium Document

Do you want full access? Go Premium and unlock all 2 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

Premium Document

Do you want full access? Go Premium and unlock all 2 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

Unformatted text preview:

Homework#1solutionscontinuedQuestion5.CLRS4-6.a. Ifmorethann/2chipsarebad,thenasubsetofthebadchipscanactlikegoodchips.Thenumberofblackchipsthatdothiscanbethesameasthenumberofgoodchips(whichislessthann/2),makingitimpossibletodiscernbetweentheseblackchipsandthegoodchips(bothsetsofthesamesize).Thismeansthatitispossibleforasubsetofthebadchips(thenumberofblackchipsinthissubsetisequaltothenumberofgoodchips)toreportaccuratelywhethertheotherchipisgoodorbad.Assumingthatthesebadchipsalwaysdothis,itwouldbeimpossibletotellthedifferencebetweenthegoodchipsandthesebadchips.Thatis,theredoesnotexistamethodbywhichtodeterminewhicharethegoodchips.Hereisanillustrationbelowthatillustratesthispoint:b. TheanswertothisquestionliesinthetwoquestionsthatareaskedbyProfessorKahngonthediscussionboard.Thefirstquestionis1)ifyouputtwochipsonthetester,andtheresultsaysthatoneofthemisbad,whathappensifyou“throwbothofthechipsaway”?Inthiscase,ifyouthrowbothofthechipsaway,thensinceyouknowthatatleastoneofthechipsisbad,thenyouarestillleftwithasetofchipsthathaveamajorityofgoodchips.Thesecondquestionis2)ifyouhaveKpairsofchips,eachofwhichisan“identicalpair”(i.e.,X-X,whereXcanbeeitherGoodorBad–youcan’ttell)–and,the2KchipstogetherhaveamajorityofGoodchips–isthereanywaythatyoucancomeupwithasmallersetofchipswhichstillhaveamajorityofGoodchips?Theanswertothisquestionisyes.Youcaneasilydothisbythrowingawayoneofthechipsfromeachpair.Then,youstillhaveamajorityofgoodchips.Therefore,combinethetwoquestions,sotospeak.Ifyouaregivennchips,beginapairwisecomparison.Ifoneormoreislabeledasbad,throwthembothout.Iftheyarebothlabeledasgood,storetheminapile,butattheendofthepairwisecomparisonsofallthechips,throwoutonechipfromeachpairwhichsaidthatthechipswerebothgood.Ifyoudothis,thenyouareguaranteedtohaveasetofBadchipsgoodchipssubsetofbadchipsactinglikegoodchipschipswithamajorityofgoodchips,wherethesizeofthesetishalfthesizeoftheoriginalset.Afterfinishingthisalgorithmyouwillbeleftwithonechip,whichwillbegood.c.

View Full Document


School:
Email:
New Password:
Confirm Password:

This preview shows page 1 out of 2 pages.

UCSD CSE 101 - Homework#1

Sign up for free to view:

Please select your school