/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q13E A long string consists of the fo... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 5: Q13E (page 162)

A long string consists of the four characters A,C,G,T ; they appear with frequency 31%,20%,9%and40% respectively. What is the Huffman encoding of these four characters?

Short Answer

Expert verified

Huffman encoding of the charactersA,C,G,T is01,001,000,1 respectively.

Step by step solution

01

Frequencies of the characters are sorted in increasing order

Write the given frequency distribution in the form of a table, in increasing order.

02

Represent the frequencies in a full binary tree

A binary tree in which every node has zero or two children is called a full binary tree.

Characters along with their frequencies in sorted order are placed at the leaf nodes, and Huffman encoding is done by following a path from the root to leaf where every left node is represented as 0 and every right node is represented as 1.Full binary tree created is shown:

03

Huffman encoding of alphabets

White the Huffman encoding of the given frequency distribution.

Thus, Huffman encoding of the given characters are 01,000,001,1.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Consider an undirected graph G=(V,E)with nonnegative edge weights role="math" localid="1658915178951" we鈮�0. Suppose that you have computed a minimum spanning tree of G, and that you have also computed shortest paths to all nodes from a particular node role="math" localid="1658915296891" s鈭�V. Now suppose each edge weight is increased by 1: the new weights are w0e=we+1.

(a) Does the minimum spanning tree change? Give an example where it changes or prove it cannot change.

(b) Do the shortest paths change? Give an example where they change or prove they cannot change.

The following table gives the frequencies of the letters of the English language (including the blank for separating words) in a particular corpus.

blank

18.3%

r

4.8%

y

1.6%

e

10.2%

d

3.5%

p

1.6%

t

7.7%

l

3.4%

b

1.3%

a

6.8%

c

2.6%

v

0.9%

o

5.9%

u

2.4%

k

0.6%

i

5.8%

m

2.1%

j

0.2%

n

5.5%

w

1.9%

x

0.2%

s

5.1%

f

1.8%

q

0.1%

h

4.9%

g

1.7%

z

0.1%

  1. What is the optimum Huffman encoding of this alphabet?
  2. What is the expected number of bits per letter?
  3. Suppose now that we calculate the entropy of these frequencies

H=鈭�t=026ptlog1pt

(see the box in page 143). Would you expect it to be larger or smaller than your answer above? Explain.

d. Do you think that this is the limit of how much English text can be compressed? What features of the English language, besides letters and their frequencies, should a better compression scheme take into account?

Give the state of the disjoint-sets data structure after the following sequence of operations, starting from singleton sets 1,鈥�,8. Usepath compression. In the case of ties, always make the lower numbered root point to the higher numbered ones.

union1,2,union3,4,union5,6,union7,8

,union1,4,union6,7,union4,5,find1

Under a Huffman encoding of symbols with frequenciesf1,f2,.....,fn , what is the longest a codeword could possibly be? Give an example set of frequencies that would produce this case.

Sometimes we want light spanning trees with certain special properties. Here鈥檚 an example.

Input: Undirected graph G=(V,E) ; edge weights we; subset of vertices U鈯�V

Output: The lightest spanning tree in which the nodes of U are leaves (there might be other leaves in this tree as well).

(The answer isn鈥檛 necessarily a minimum spanning tree.)

Give an algorithm for this problem which runs in O(ElogV) time. (Hint: When you remove nodes Ufrom the optimal solution, what is left?)
See all solutions

Recommended explanations on Computer Science Textbooks

Theory of Computation

Read Explanation

Data Representation in Computer Science

Read Explanation

Cloud Services

Read Explanation

Big Data

Read Explanation

Blockchain Technology

Read Explanation

Game Design in Computer Science

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.