5251 Syllabus Spring 2008
5251 Practice Exam 1
Exam 1 Grade Distribution
5251 Practice Exam 2
HW#1 Due Wed. Feb. 6 Chap. 1: 11,29,40,49,56 Chap. 2: 3,4,5
Extra problems for HW #1:
#1: Let X be a random variable on a finite probabilty space \Omega. For a function f(x), let Y be the random variable f(X). How is H(Y) related to H(X)?
#2: Let (p1,...,pn) and (q1,...,qn) be probability distributions.
(a) Show that for any number A between 0 and 1,
rA =A*(p1,...,pn)+(1-A)* (q1,...,qn)
is another probability distribution.
(b) Use the basic H inequality to show that
H(rA) &ge A*H(p1,...,pn)+ (1-A)* H(q1,...,qn).
HW#2 Due Wed. Feb. 20 Chap. 3: 2,5,6 Chap. 4: 2,4,5,9,11
Extra problems for HW #2:
#1: (a) Is the code C={0,10,001} uniquely decipherable?
(b) Is the code C={0,01,011,0111,1111} uniquely decipherable?
(c) Is the code C={1,10,100,1000} uniquely decipherable?
(d) Which of the codes in (a), (b), and (c), if any, are instantaneous?
#2: Suppose that an instantaneous binary code C includes the words {0,10}. What is the maximum number of code words of length 7 that could be added to C and still make C instantaneous?
#3: Let \Omega be an n-point probability space with the uniform distribution, this means that each point in \Omega has probability 1/n.
(a) If n is a power of 2, what will the lengths of the code words
be in a Huffman encoding of \Omega?
(b) Find the lengths of the Huffman codewords for n=9.
(c) If 2k is the largest power of 2 which is at most n,
what is the length distribution of codewords in a Huffman code?
(d) What is the average length of a code word in a Huffman
code, in terms of n and k?
HW#3 Due Wed. Mar. 12 Chap. 6: 23,31,38,50,51,53,55,67,76; Chap. 8: 2,6,12,17,19,30,35
HW#4 Due Wed. Apr. 2 Chap. 8: 21,22,23,26,33,39; Chap. 9: 3,6,10,11,22 Chap. 10: 4,7,11 Chap. 11: 2,7,8
HW#5 Due Wed. Apr. 23 Chap. 11: 2,7,8,10 Chap. 12: 1,2,10,15 Chap. 13 1,2
HW#6 Due Mon. May 5 Chap. 13: 4,7 Chap. 14: 4 Chap 17: 7
Extra problems:
#1. Construct a finite field k with 4 elements using a monic irreducible polynomial of degree 2 over Z/2. Show that there are 15/3=5 different directions for vectors of length 2, with entries in k. Use these 5 directions to explixcitly define a parity check matrix of a 4-ary Hamming (5,3,3)-code. Give a generator matrix for your code.
#2. What do the sphere packing, Singleton, Plotkin and Gilbert-Varshamov bounds say about the existence of a binary (11,k,6)-code? What do they say about k?
Exam 2 Makeup problems Due Wednesday Apr 16
You must show your work.
1. Solve for x: 25x+101= 56 mod 277.
2. Let p(x)=x6+x+1, q(x)=x7+2x+1, both in Z/3[x]. Find d(x)=GCD(p(x),q(x)), and polynomials a(x), b(x) in Z/3[x] such that a(x)p(x)+b(x)q(x)=d(x).
3. Factor x6+4x+1 in Z/11[x] into irreducibles, and prove your factors are irreducible.