A computer science professor wrote the following note (please read… A computer science p

A computer science professor wrote the following note (please read… A computer science professor wrote the following note (please read thouroughly):”Every so often a company will claim to have created a ‘perfect’ compression algorithm – analgorithm that can always reduce the size of a file.If such a magic algorithm actually existed, then it could be applied repeatedly to any file to makeit smaller and smaller. Download times would drop to nothing. Perhaps it is the allur of suchfantastic benefits that keeps a steady stream of gullible consumers investing in these doomedideas.It is easy to show that an algorithm capable of always compressing a file is impossible. Here isone easy to follow argument.Suppose David tells you that his program, BelchZip, can compress any file to at most somefraction p of its original size.For example, if David says he can give you gauranteed compression of 80% (p = 0.8) and yougive BelchZip a 100 byte file, you will always get back a file of 80 bytes.Let’s examine BelchZip on all files of length n bits.Essentially, David’s program is a function, f, from the set of files of length n to the set of files oflength pn. There are 2″ files of length n, and we will call this set of files A. There are 2p filesof length pn, and we’ll call this second set B.Since (A) > |BI, the program / cannot be injective. That is f must map multiple files from Ato the same file in B. Thus, the program f cannot have an inverse. Consequently, no reliabledecompression program can exist for files compressed with f, so David’s program either does notexist or is useless.”What facts and results from our Discrete Math course did the explanation above use?(a) injective and bijective functions(b) the Pigeonhole Principle and Counting Principles(c) invertible functions(d) all of the above(e) none of the above Math MATHEMATIC 2305 Share QuestionEmailCopy link