EXERCISES (First and final posting May 08 2006)
The excercises,
unless
indicated otherwise, are selected from our textbook
Elements of Information
Theory by Thomas M. Corver and Joy A. Thomas.
Answers should be
returned
by end the end of the course year (say in June 2006), preferably on paper.
Later
submission is accepted as well, but don't expect evaluation on short
notice in that case.
Electronic submissions causing processing problems will be rejected.
Cooperation between students is permitted under the following conditions:
-- the group
shoudn't
exceed three people.
-- the cooperation must
be
clearly indicated on all solutions submitted
-- a group starting to
cooperate must persist in this cooperation till the end
of the
course.
-- the group will be
graded
as a collective; it is the responsibility of the
people
cooperating to prevent abuses.
Use of the teacher's support manual
which exists for this book (supposed to be unavailable to students) is
strictly forbidden.
In case of noticeble similarity
between the solutions submitted and this (or other inelegible material)
may lead to
disqualification of the results
whence no grade will be given for the course.
Chapter
2.
2.1 Flipping a coin until success.
2.2 Are values
relevant?
2.3
Characterization of minimal entropy distributions.
2.5 Computation reduces Entropy
2.6 When does
conditional entropy vanish?
2.7 How to
obtain fair coin flips from a biased coin.
2.9 A
discrete source with infinite Entropy.
2.10
Conditionalizing may both increase and decrease shared uinfdormation.
2.14 Impact of
replacement when drawing multiple balls from an urn.
2.18 Entropy of
the sum of two sources.
2.28 Impact of
mixing.
2.32 When does
processing not affect conditional Entropy?
Chapter 3
3.2 Another limit
3.3 AEP
and source coding
3.6 Two
approaches at radom boxes in unbounded dimension
Chapter 4
4.1
Doubly Stochastic Matrices
4.2
Predicting the future versus reconstructing the past
4.4 Some
inequalities for stationary processes
4.8
Pairwise independence isn't full independence !
4.11 A random walk on
a small chessboard
Chapter 5
5.1 Which Inequalities can you expect to hold?
5.2 Find the
unknown alphabet size
5.3 Strict
inequality and undecodable messages
5.4
Construction of a Huffman code
5.5
Sensitivity of Huffman coding result for the actual distribution.
5.6
Impossible Huffman outputs.
5.9
Optimal code length exceeding the entropy by almost one
5.14 Yet another
Huffman code
5.24 An algorithmic test for unique decodability.
Chapter 7
7.1 Kolmogorov Complexity of a pair of sequences
7.2 Kolmogorov
Complexity of the sum of two numbers
7.3
Kolmogorov Complexity of simple pictures
z
7.4 Kolmogorov
Complexity of useful programs
7.10 More
Kolmogorov Complexity of Pictures; NB! I consider the phrasing of
the Excercise Ambiguous,
so you should make
explicit how you interprete this question.
Chapter 8
8.1 An instance of misguided assistance
8.2 Analysis
of a simple repetition code
8.5 Channel
capacity of a symmetric channel
8.6
Channel capacity of pair of channels.