Jump to content

Comp sci/data compression puzzle


Recommended Posts

Some types of compressed files can be compressed further, losslessly...


yet it is known that there is no possible algorithm that can losslessly compress all possible input data. This puzzle's about that.




There is a type of data stream that is a fixed length N bits of binary data.
The data is statistically random; every possible variation of 0s and 1s is as likely as any other.
There is an optimal lossless compression algorithm that reduces the data size of as many of the possible data variations as is mathematically possible, and produces a variable-length output of M bits.
The uncompress algorithm knows the value of N and the size of the compressed data stream.
1. How many of the possible data streams cannot be compressed, ie. where M >= N?
2. For large N, what's the average size savings achieved by the algorithm?
3. Describe or write pseudocode for such an algorithm (compress and uncompress).
4. The CEO of Hooli is offering $1M for your algorithm. Do you take it, or try to develop it with your own startup company?



Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.