I tried to answer this question (http://tau-cs1001-py.wikidot.com/local--files/exams/exam_2011b_moed-b.pdf) and I thought the answer was (a), since we proved in class that a universal compression algorithm doesn't exist, when I checked the answer, I saw the correct answer was actually (b), which confused me.
What is the trivial algorithm mentioned in this question, that can compress any bit sequence?
Date: 25 Jan 2016 14:34
Number of posts: 2
RSS: New posts
This question is a bit tricky, I must admit.
There are 2**n-1 strings of length n, excluding the zero string, and the exact same number of strings of length < n (1 string of length 0, 2 strings of length 1, etc.). Since the two sets are of the same size, there is a trivial bijection (פונקציה חד חד ערכית ועל) between them. Had the zero string not been excluded, this mapping could not be possible.
I find it tricky, mostly because the empty string is not really a legal transmission. So in the context of digital communication, it doesn't make sense to compress something into the empty string (how would you transmit it? how would the other party know you transmitted it?)
Anyhow, the exam on Sunday will not include such tricks.
BTW - I would not focus on the exams from the first two semesters of this course (the oldest 4 exams). Their structure does not represent the structure of more recent, and Sunday's exam.