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

Suppose we want to find the minimum spanning tree of the following graph.

(a) Run Prim’s algorithm; whenever there is a choice of nodes, always use alphabetic ordering (e.g., start from node A). Draw a table showing the intermediate values of the cost array.

(b) Run Kruskal’s algorithm on the same graph. Show how the disjoint-sets data structure looks at every intermediate stage (including the structure of the directed trees), assuming path compression is used.

The basic intuition behind Huffman’s algorithm, that frequent blocks should have short encodings and infrequent blocks should have long encodings, is also at work in English, where typical words like I, you, is, and, to, from, and so on are short, and rarely used words like velociraptor are longer.

However, words like fire!, help!, and run! are short not because they are frequent, but perhaps because time is precious in situations where they are used.

To make things theoretical, suppose we have a file composed of m different words, with frequencies f1,...,fm. Suppose also that for the ithword, the cost per bit of encoding is ci. Thus, if we find a prefix-free code where the ithword has a codeword of length Ii, then the total cost of the encoding will be localid="1659078764835" ∑fi·ci·li.

Show how to modify Huffman’s algorithm to find the prefix-free encoding of minimum total cost.

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

A binary counter of unspecified length supports two operations: increment (which increases its value by one) and reset (which sets its value back to zero). Show that, starting from an initially zero counter, any sequence of n increment and reset operations takes time O(n); that is, the amortized time per operation is O(1) .

Give You are given a graphG=(V,E)with positive edge weights, and a minimum spanning tree T=(V,E)with respect to these weights; you may assume GandTare given as adjacency lists. Now suppose the weight of a particular edge e∉E'is modified fromw(e)to a new value w'(e). You wish to quickly update the minimum spanning tree T to reflect this change, without recomputing the entire tree from scratch. There are four cases. In each case give a linear-time algorithm for updating the tree.

(a) e∉E'and w'(e)>w(e) .

(b) role="math" localid="1658907878059" e∉E'and w'(e)>w(e) .

(c) role="math" localid="1658907882667" e∉E'and w'(e)>w(e) .

(d) role="math" localid="1658907887400" e∉E'and w'(e)>w(e) .
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Systems

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Organisation and Architecture

Read Explanation

Computer Network

Read Explanation

Big Data

Read Explanation

Issues 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.

Sign-up for free