Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. You would liek to send a message of length n over a channel. You know that, at most, k packets may be dropped along the way and of the packets not dropped, at most j may be corrupted. How many packets do we need to send in order to guarentee a successful decoding? Why?
We must send n + k + 2j packets. Let's say the worst thing happens and all k possible packets are dropped and all j packets are corrupted. We ned to send k extra packets in order to protect from the erasure errors, and then 2j more packets to protect from general errors. 2. How many different polynomials of degree d over GF(p) are there if we know k values, where k <= d?
pd+1-k. We need d+1 points to make the polynomial, and if we know 0 points, then every point can be anything in the span of p. As soon as we start finding more points, the amount of non-fixed points becomes less and less, until k = d+1, where we are left with one polynomial.3. Secret sharing is a crucial application of Polynomials. We have 4 TAs and 14 readers, and we want to share a secret among them such that either 2 or more TAs, at least 1 TA and at least 2 readers, or at least 4 readers can reconstruct the secret. Describe such a scheme.
A TA is essentially 2 readers, so if we make a polynomial of degree 3 such that P(0) is the secret, each reader gets one point while each TA gets 2 points. This will be a perfect scheme.