CS 70 Reading Quiz -- Week 7, Sunday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

1. Alice proposes the following method for sending a polynomial P(x) of degree ≤ n-1 over an unreliable channel, where up to k packets could be corrupted arbitrarily. She proposes that the sender should compute n+k encoded values using the standard erasure coding scheme we saw in class (i.e., c_i = P(i) mod q). Then, the sender will append a fingerprint of c_i to the end of each packet, so that the i-th packet consists of the triple (c_i, F(c_i,r), r). The receiver will check, for each received packet (c_i, f_i, r), that f_i is a valid fingerprint of c_i. The receiver discards every packet where the fingerprint is invalid (treating those packets as "lost"), and then applies the standard method we saw in class on Wednesday for decoding the erasure code (namely, Lagrange interpolation on the packets that remain).

Explain why this scheme isn't guaranteed to work, even if we're guaranteed that no more than k out of the n+k packets sent will be corrupted (i.e., even if we're guaranteed that at least n out of the n+k packets will be received correctly).

2. Suppose we are given a polynomial P(x) of degree ≤ n whose coefficients are in the range 0..q-1, and we are given a number i in the range 0..q-1. How many bit operations does it take to evaluate P(i) mod q? Express your answer using big-O notation.

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 70 home page