20CS472001  Design and Analysis of Algorithms II  Winter 2011 


Alice in Cincinnati wants to send a secret binary message (1s and 0s) to her friend Bob in Cleveland. Alice and Bob know that their lines are tapped by Eve so they decide to encode Alice's message by translating every consecutive pair of bytes in the message to a positive integer and sending that integer. The translation scheme is based on the following sequence of numbers which are dreamed up by Bob:
x[1]: 1 x[2]: 3 x[3]: 5 x[4]: 10 x[5]: 20 x[6]: 42 x[7]: 85 x[8]: 170 x[9]: 400 x[10]: 780 x[11]: 1517 x[12]: 3050 x[13]: 6100 x[14]: 13000 x[15]: 25189 x[16]: 50456The translation proceeds as follows: suppose the next two bytes are in a bit array m[1..16]. Then the number transmitted by Alice is
sum from i=1 to 16 of m[i]*x[i] Example: the message 1001100010100111 has m[1]=1, m[2]=0, m[3]=0, m[4]=1, m[5]=1, etc. and is sent as the number 1+10+20+400+1517+13000+25189+50456 = 90593Is it possible for Bob to write a very fast (less than 32 arithmetic operations (+*/) per two bytes) algorithm which recovers, from every number which Alice sends, exactly two bytes of a message that Alice has encoded? If so, state such an algorithm and its worstcase complexity if one were to use it to encode n bytes at a time. If not, state why not.
Hint: carefully study the properties of the x[1] ... x[16] sequence.