CS 5315, Quiz 2, Thursday, April 2, 2009

1. What is Kolmogorov complexity?

2. Estimate Kolmogorov complexity of a binary sequence 110110...110 (110 repeated 1,000 times).