Class Assignments

Review

• An Introduction to Informatation Theory  Chapter 2 Basic Concepts of Discrete Probability (except 2-19)
   
  
• Snell's Introduction to Probability Chapters 1 and 3.
   
  
• http://en.wikipedia.org/wiki/Logarithm contains more information about Logarithms than we need but is worth a quick review.
   
  
• Huffman Code Review
   
  
• Linear Algebra Review
   
  
• The Ball Weighing Problem
   
  
• Decoding Notes
   
  
• Test 1 Answers
   
  
• Test 1r Answers
   
  
• Phillip M. Lombardo's project from a previous semester.

Assignments

1. Due February 5 - Is the Hamming [7,4,3]₂  code also correcting in the Hamming Distance sense? Why?

2. Due February 14 -
   

   • Solve the 6 ball Weighing Problem. As with the 12 ball problem the balls are identical except one weights more or less than the others. Your solution should compute the appropriate "Shannon Clue" as to the number of steps needed and for each step how much Shannon Information is being obtained.

   • I choose a ball at random from a bag containing 3 red balls and 1 blue ball and I choose a card at random from an ordinary deck of playing cards.
     If I choose a red ball I tell you the cards rank (A,2,3....,K).
     If I chose the blue ball I tell you the cards suit (S,H,D,C).
      
     
     • How bits of Information do you expect to get by learning the result of my experiment?
     • Considering this as a two stage Experiment, verify that the appropriate Partition Formula produces the correct result.

     Some Observations:   Information about the color of the ball is redundant. If I tell you a rank, you know the ball was red. If I tell you a suit, you know the ball was blue.
     The Partition Formula for this problem is almost identical to the one done in class: Something like.

           H(X) = H(Y) + p₁H(Z₁) +p₂ H(Z₂)

     will work. The two level tree for this problem is more complicated in that the bottom subtrees are of different sizes, and less complicated in that each bottom subtree has equiprobable.branches.  

   • Due March 7 -
     • Compute H(X,Y) and H(X|Y) for a Binary Symmetric Channel and input vector [ p₁, p₁]
       
     • Compute the Channel Capacity for a Binary Symmetric Channel in terms of p.
     MacKay's Lectures 6,7, and 8 cover about the same material I will in the next few lectures and should be useful for this assigned exercise and those exercises and assigned exercises to follow prior to the Exam.

   • Due April 11.
     Given: p=11 , q=17
     and Alphabet Encoding: A =1 , B=2, C=3
     and message string: CAB
     Find an appropriate e and d then Encode -> Encipher -> Decipher the message.
     Notes: 1. There was a typo on the "Number Theory Page." It was 5- x= 2 is x= 4 mod(7) it now reads 2- x= 5 is x= 4. Thanks to your fellow student, who brought this to my attention.
     2. I added a note to the worked out RSA example. Some of you were appropriately concerned about the choice of message size. As I mentioned in the note the details of the example are sort of correct but are of a somewhat historical nature.
   • Due April 18.
     1. What Category is log(n²+7)?
     2. Suppose your computer can perform 10,000,000 integer long divisions per second(don't worry about the size of the integers). Suppose you know that n=pq , a product of primes is 400 digits long. Worst case, approximately how long would it take to factor n by brute force. Remember you only have to check up to the square root of n?
   • Due April 25.
     1. Show A={aⁿb^mcⁿ} n,m ≥0 is a CFL
     2. Show A={aⁿbⁿaⁿbⁿ}n > 0 is not a CFL.

   • Due May 2.