Questions for Examination 1.

1. Find a on adaptive weighing scheme for 41 potentially bad coins and one definitely good one, and produce a spreadsheet that automatically finds the bad coin given the outcomes of your 4 weighings.

2. Outline in pseudocode or in computer code in an appropriate language two of the first few of our sorting algorithms other than Batchers. (It is not appropriate to use the command "sort".

3. Construct a Batcher spreadsheet sorter for 32 keys.

4. You can actually sort 5 items with 7 comparisons not 8, and can start from 2 sorted pairs and finish the job with 5 more comparisons

a) find a way to do this

b) find the bound on finding the median obtainable from this fact and the old argument..

5. Compute the entropy of information H(p1,p2,…) given a frequency list f1,f2,….

6. Outline a proof of Shannon's (first) Theorem, (bounding compression using only frequency information), in your own words (prove in both directions).

7. Given a list of message frequencies in order, compute optimal Hu Tucker and Huffman codes, and compute the average message length in them.

8. Outline a proof of Shannon's Second Theorem, on the proportion of check bits necessary and sufficient to be able to correct a proportion p of errors, for p<1/2.

9. State Stirlings formula; determine its proportional error for n!, for n=1 to 30

10. State and Outline a proof of the (weak) law of large numbers in your own words.

11. You have 10 tiny red balls, and 10 tiny blue balls. You have two pockets in which you may place them. An enemy will reach into a pocket at random and pick a ball at random (and go to the other pocket if that one is empty). How can you minimize the enemy's chance of getting a blue ball? What will that chance be?

12. Suppose you bet one dollar every day for 3 years on an even game, and you win one dollar on each winning day and lose one on each losing day.

Assume that each day is independent of each other day. What is the distribution of your winnings; in particular what is the probability that you win at least $10. At least break even? Lose at least $10?

Now suppose the odds of the game are slightly against you, so that you only win with probability 16/33 each day. What are the same chance as before under the same conditions?

13. Construct a 15 bit matrix code encoder error finder and decoder.

14. Given a polynomial p of degree 6, answer the following questions:

is it primitive. What is the corresponding p₃? p₅?

15 State and prove enough relations between s's (elementary symmetric functions) and t's (power sums) to find expressions for s₁ s₂ and s₃ in terms of the t's assuming 3 or fewer errors. And find them.

16.For any given primitive polynomial of degree 6, which powers x obey which equations?

17. Produce a spreadsheet that codes, adds errors corrects and decodes using your favorite degree 5 primitive polynomial for division.

18. Suppose we take the equation for two errors: rem s₂ + s₁y +y² =0 at x^e1 and x^e2, and divide these equations by y before evaluating them, then sum them

what do you get? This suggests that you can get a two error correcting code by taking the product of a primitive polynomial and its reverse, and getting s₂ = t₁/t_-1. Will this work?.

19. Suppose you seek a 9 error correcting BCH code on 255 total bits. How many check bits and message bits will you have? Be careful this is tricky.Same question for correcting 18 bits?

20. How many errors must you correct in a BCH code with 255 bits given a probability of 10^-5 of error per bit, to reduce the probability of an error per message getting by to 10^-15, while having the probability of having to resend because you cannot correct the error to at most 10^-10 per message? Use the fact that when you make more errors than you correct, most of the time you will have to resend. (estimate how much of the time this will happen).