20-CS-472-001 Design and Analysis of Algorithms II Winter 2011

## Algorithms

Due: Jan 12, 2011

1. If you are at all interested in this kind of work you will be delighted with your solution.

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]:  50456
```
The 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 = 90593
```
Is 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 worst-case 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.

2. Given a very very long racing circuit, a race car, and a collection of gasoline stations at various specified points along the circuit. Suppose the total gasoline in all the stations is exactly enough for the race car to traverse the circuit exactly once. We want to find a point on the circuit to start the car so that it can traverse the circuit exactly once without running out of gasoline. Design an optimal algorithm (most efficient possible) for finding such a point. Observe: do not necessarily start at the station with the most gas.