Below are five problems of varying complexity, please try to solve as many as you can.
The deadline for submission of answers is Sunday, February 25, 2018 at 23:59 GMT.
1. (20%) Let A = {a, ..., z, A, ..., Z, 0, ..., 9}. Let q = q1, ..., q m and w = w1, ..., wn be finite-
length words in A
*
. Find an efficient procedure which decides whether there is a permutation
p: A to A such that p(w1), ..., p(wn) appears as a consecutive sub-string of q. Describe time
and memory complexity of your solution.
2. (20%) A string S of length n = 100,000,000 bits is transmitted via a noisy channel. The
errors in the channel may flip bits, may insert or delete single bits. The probability of error is
p = 0.01 (each time an error happens it is decided uniformly at random, what type of error it
would be).
a. Suppose you are given both the original and the noisy version of the string. Propose an
efficient algorithm which given as input an index in the original string would output the
closest corresponding index in the second string. Assume that large number t of such
queries needs to be answered. Describe the algorithm and its complexity (memory and
time).
b. Propose a scheme that would allow one to transmit information correctly over this
channel (max half-page).
3. (20%) Find all functions for which (when x ≠ 0,1): f(x) + f(1/(1-x)) = 1 + 1/(x(1-x)).
4. (20%) The C function given below has 4 arguments: r, a, and b are pointers to arrays of
type uint32_t. The integer n specifies the length of these arrays (i.e. all 3 arrays contain
the same number of elements). The return value is of type int.
a. What operation does this function perform? (you can give a concrete example and
describe the array r and return value c)
b. How can you reduce the execution time of the function (for example using inline x86
assembly), write down the modified source code.
int function(uint32_t *r, const uint32_t *a, const uint32_t *b, int n)
{
int i;
uint32_t ri, c=0;
for (i = 0; i < n; i ++)
{
ri = a[i] + b[i] + c;
c = ((ri < a[i]) || ((ri == a[i]) && c));
r[i] = ri;
}
return ((int) c);
}
5. (20%) Explain how the position shown in the figure below could happen after exactly four
moves of both sides from the starting chess position: