Log out Go to App
Go to App

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.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

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

Prove the following two properties of the Huffman encoding scheme.

(a) If some character occurs with frequency more than 25, then there is guaranteed to be a codeword of length 1 .

(b) If all characters occur with frequency less than13 , then there is guaranteed to be no codeword of length 1 .

Show that if an undirected graph with n vertices has k connected components, then it has at least n - k edges.

Ternary A server has customers waiting to be served. The service time required by eachcustomer is known in advance: it is ciminutes for customer i. So if, for example, the customers are served in order of increasing i , then the ithcustomer has to wait Pij=1tjminutes. We wish to minimize the total waiting time.

T=Xni=1(time spent waiting by customer ).

Give an efficient algorithm for computing the optimal order in which to process the customers.

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.

Suppose you are given a weighted graph G=(V,E) with a distinguished vertex s and where all edge weights are positive and distinct. Is it possible for a tree of shortest paths from s and a minimum spanning tree in G to not share any edges? If so, give an example. If not, give a reason.
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Systems

Read Explanation

Theory of Computation

Read Explanation

Game Design in Computer Science

Read Explanation

Big Data

Read Explanation

Databases

Read Explanation

Functional Programming

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.

Sign-up for free