(a) Given the following alphabet = (a, g, h, i,l, m, o,r, t) and corresponding...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(a) Given the following alphabet Σ = (a, g, h, i,l, m, o,r, t) and corresponding frequencies, use Huffman's algorithm to compute an optimal prefix-free code. Represent the prefix-free code as a binary tree, with either 0 or 1 on each edge. Letter a m 0 r t Frequency 0.14 0.06 0.10 0.17 0.07 0.11 0.10 0.08 0.17 (b) What is the expected encoding length (average number of bits per element) of this alpha- bet? Entropy is a mathematical formulation of the uncertainty and/or the amount of information in a data set. Consider a data set D consisting of n characters, each character independently chosen from a set C according to a specified probability distribution p. That is, for c E C and 0 ≤ i ≤n, the probability that the ith character of D is c is p(c). Note that Ecec P(c) = 1. The entropy of data set D is then defined to be np(c)log₂ (1/p(c)). cec Intuitively, the entropy measures the information-theoretic minimum number of bits needed to represent the data set. (c) Calculate the entropy of a corpus, which contains the letters in the same frequencies as (a). View the frequencies as probabilities for the entropy calculation. (Note that the frequencies sum up to 1.) Compare the entropy with the compression achieved by Huffman coding and indicate whether Huffman encoding yields the best possible compression. More generally, do you think entropy captures the limit of how much that corpus can be compressed? Explain briefly in words. (a) Given the following alphabet Σ = (a, g, h, i,l, m, o,r, t) and corresponding frequencies, use Huffman's algorithm to compute an optimal prefix-free code. Represent the prefix-free code as a binary tree, with either 0 or 1 on each edge. Letter a m 0 r t Frequency 0.14 0.06 0.10 0.17 0.07 0.11 0.10 0.08 0.17 (b) What is the expected encoding length (average number of bits per element) of this alpha- bet? Entropy is a mathematical formulation of the uncertainty and/or the amount of information in a data set. Consider a data set D consisting of n characters, each character independently chosen from a set C according to a specified probability distribution p. That is, for c E C and 0 ≤ i ≤n, the probability that the ith character of D is c is p(c). Note that Ecec P(c) = 1. The entropy of data set D is then defined to be np(c)log₂ (1/p(c)). cec Intuitively, the entropy measures the information-theoretic minimum number of bits needed to represent the data set. (c) Calculate the entropy of a corpus, which contains the letters in the same frequencies as (a). View the frequencies as probabilities for the entropy calculation. (Note that the frequencies sum up to 1.) Compare the entropy with the compression achieved by Huffman coding and indicate whether Huffman encoding yields the best possible compression. More generally, do you think entropy captures the limit of how much that corpus can be compressed? Explain briefly in words.
Expert Answer:
Answer rating: 100% (QA)
a To compute the optimal prefixfree code using Huffmans algorithm we start by building a binary tree ... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Solve these equations algebraically. Show all work. This means that you must State as a piecewise function Solve both parts of the piecewise function Verify the solution for each part (i.e. the...
-
Students will present a draft IMC strategy for a start-up company and be asked to analyze its potential effectiveness, identifying gaps and making recommendations for improvement of the strategy....
-
Use a graphing utility to graph f and g in the same viewing window. What is the relationship between the two graphs? Use the Binomial Theorem to write the polynomial function g in standard form. 1. f...
-
Aniline Corporation owns a small printing press that prints leaflets, brochures, and advertising materials. Aniline classifies its various printing jobs as standard jobs or special jobs. Anilines...
-
A friend has asked you for help. She is an entrepreneur and would like to start a company to pursue her dream of designing and selling a line of childrens toys. She has heard the term stakeholder...
-
Cost-Volume-Profit Analysis and Return on Investment (ROl) posters.com is a small Internet retailer of high-quality posters. The company has $1,000,000 in operating assets and fixed expenses of...
-
(a) A company has an EPS of Rs. 2.5 for the last year and the DPS of Rs. 1. The earnings is expected to grow at 2% a year in long run. Currently it is trading at 7 times its earnings. If the required...
-
On January 1, 2022, Mobile Technology, Incorporated issued $850,000 of $1,000 par value, 6%, 6-year bonds. Interest is payable semiannually each January 1 and July 1 with the first interest payment...
-
ABC Corporation purchased a new delivery truck for $50,000 cash on January 1, 2022. The company estimates that the truck will have a useful life of 5 years and a salvage value of $5,000. The company...
-
T/F Underpricing tends to discourage investors from participating in the IPO market.
-
Bondholders are willing to pay a premium to acquire a bond because the ______. Multiple choice question. bond's stated interest rate is lower than the market interest rate bond's stated interest rate...
-
The cost of common stock equity is ________. Question 9 options: the cost of the guaranteed stated dividend expected by the stockholders the after-tax cost of the interest obligations the rate at...
-
Argue that 2 x 2 matrices of rank 1 is a manifold. Denote this space by M(2, 2), i.e. we consider M(2, 2) to be a subspace of M2,2 (R) = = R4.
-
Compare and contrast deb financing and equity financing. Under what conditions is either one advantageous?
-
2. Payback Consider the following projects: Cash Flows ($) Project Co C3 C4 C5 A -1,000 +1,000 B -2,000 +1,000 +1,000 +4,000 +1,000 +1,000 -3,000 +1,000 +1,000 0 +1,000 +1,000 a. If the opportunity...
-
Suppose the index goes to 18 percent in year 5. What is the effective cost of the unrestricted ARM?
-
Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant: At the start of each iteration of the while loop of lines 4-6, the subarray A[1 . .A.heap-size] satisfies the max-heap...
-
Prove that the running time of an algorithm is (g (n)) if and only if its worst-case running time is O(g (n)) and its best-case running time is (g (n)).
-
Write the TREE-PREDECESSOR procedure.
-
A single-tank liquid-level system with inflow rate \(q_{i}\) as its input and liquid level \(h\) as its output is modeled as \(R A \dot{h}+g h=R q_{i}(t), h(0)=0\), where \(R, A, g=\) const. If the...
-
The mechanical system in Figure 8.37, where all parameter values are in consistent physical units, is subject to initial conditions \(x_{1}(0)=1, x_{2}(0)=1, \dot{x}_{1}(0)=-1, \dot{x}_{2}(0)=1\)....
-
Find the state vector via the formal-solution approach. \(\dot{\mathbf{x}}=\left[\begin{array}{cc}5 & 1 \\ -4 & 1\end{array} ight] \mathbf{x}+\left[\begin{array}{c}1 \\ -1\end{array} ight] u, \quad...
Study smarter with the SolutionInn App