Comp sci/data compression puzzle

[md65536]

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

http://www.fastcompany.com/3050180/tech-forecast/these-engineers-just-built-their-own-pied-piper-compression-algorithm

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?

 

 

[fiveworlds]

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

 

video to msd. It isn't lossless but I wouldn't notice the difference on my crappy screen

Edited August 30, 2015 by fiveworlds