Frequently Asked Questions

We will attempt to answer commonly asked questions and try to clarify any confusing points in the homework, lectures notes, or any other parts of the course.

Comments on First Problem Set (9/8/2008)

Comment 3 is a hint for problems 1 and 4.

1. In problem 1 for 13 coins you may not be able to tell if the bad coin is heavy or light.
2. In problem 3 by general solution we mean general solution with the maximum possible number of coins. (There is no solution at all for 1 weighing and if you have two less than the maximum number of coins for any number of weighings there is no solution.)
3. The answer to problem 5 tells you exactly which of the possible columns correspond to coins in the construction given in class and in the latest notes. Armed with this information you can find 2 of these columns that add up to the negative of the good coin and can eliminate those 2 and the good coin along with the all 0 column and get a good matrix for 11 coins. And you can find three of those columns that add up to the negative of the good coin to handle the 10 case. These easily generalize to more than three weighings. This approach can be used to solve problems 1 and 4.
4. In problem 4 assume that there are at least 3 weighings. 5. In problem 6 only the lower bound is asked for. As noted elsewhere, assume the bad coins have the same weight.

In RSA encoding, the message length m must be less than N=pq, otherwise, the algorithm fails.

10/3/06
A parity bit added at the end of each codeword means the sum (Mod 2) of each bit of the codeword. For example, the codewords {000, 001, 010, 110} with a parity bit added at the end becomes {0000, 0011, 0101, 1100}.