Data Structures

Computing

Quiz 15 :

Graphs and Digraphs

Quiz 15 :

Graphs and Digraphs

Question Type
search
arrow
Using the Huffman code developed in Exercise 7, encode the message "feed a deaf aged hag".
Free
Essay
Answer:

Answer:

Algorithm for Huffman:
Input:
Characters : [C 1 ,C 2 ,…………C n ]
Weight : [W 1 ,W 2 ,………W n ]
where W i is the weight of C i
Step 1 :
One-node binary tree list is initiated.
Step 2 :
Repeat the process for n-1 times:
• search for the lowest weight in the list W' and W''and draw two trees T' and T''
• the trees are replaced with binary tree which contains the root value as W' + W''
• the subtree pointers are labeled as 0 and 1 respectively
Step 3 :
The character's code can be obtained by label in the path from root to the current node
Given:
Huffman code developed in "Exercise-7":
img Consider the Message: "feed a deaf aged hag":
The Huffman code for the value "f" is as follows:
img The Huffman code for the value "e" is as follows:
img The Huffman code for the value "e" is as follows:
img The Huffman code for the value "d" is as follows:
img The Huffman code for the value "a" is as follows:
img The Huffman code for the value "d" is as follows:
img The Huffman code for the value "e" is as follows:
img The Huffman code for the value "a" is as follows:
img The Huffman code for the value "f" is as follows:
img The Huffman code for the value "a" is as follows:
img The Huffman code for the value "g" is as follows:
img The Huffman code for the value "e" is as follows:
img The Huffman code for the value "d" is as follows:
img The Huffman code for the value "h" is as follows:
img The Huffman code for the value "a" is as follows:
img The Huffman code for the value "g" is as follows:
img Thus the encoded message is as follows:
img

Tags
Choose question tag
close menu
arrow
Repeat Exercise 6 for the following table of letters and weights: img
Free
Essay
Answer:

Answer:

Algorithm for Huffman:
Input:
Characters : [C 1 ,C 2 ,…………C n ]
Weight : [W 1 ,W 2 ,………W n ]
where W i is the weight of C i
Step 1 :
One-node binary tree list is initiated.
Step 2 :
Repeat the process for n-1 times:
• Search for the lowest weight in the list W' and W'' and draw two trees T' and T''
• The trees are replaced with binary tree which contains the root value as W' + W''
• The subtree pointers are labeled as 0 and 1 respectively
Step 3 :
The character's code can be obtained by label in the path from root to the current node
Given:
Use the given table to construct the Huffman code:
img As per the Huffman's algorithm, a list of one-node binary tree is constructed in order of increasing order of their weight.
img The two trees are selected that has the smallest weights; thus it results
img .
img From the list, select two of minimal weights "
img ".
img From the list of 3 binary trees, select two of minimal weights "
img ".
img From the list, select two of minimal weights "
img ":
img From the list, select two of minimal weights "
img ".
img Combine the two binary trees to get single resulting Huffman tree:
img Complete Huffman tree.
img Thus the Huffman code obtained from the tree:
img

Tags
Choose question tag
close menu
arrow
Write a function that reads a table of letters and their weights and constructs a Huffman code for these letters. Use the function in a program that encodes a message that the user enters.
Free
Essay
Answer:

Answer:

Problem plan:
• Include the required header files into the program.
• Use "struct" for tree node
• Allocate new tree to a node
• Define a function "encoding ()" to encode the string.
o check if the root node is null
o check if the leaf node is found
o call the function "encoding ()" to append 0
o call the function "encoding ()" to append 1
• Define a function "huff_tree ()" to generate huffman code
o Use map tp count the frequency
o store live nodes
o create leaf node and push the elements
o perform until more than 1 node in the tree
o pointer is stored to the root of the Huffman
o traverse and store the huffman codes
o print the huffman codes
• Define "main()" to demonstrate huffman technique
o Declare variables
o get input from user
o call the function "huff_tree()" to generate huffman code
Program:
/ ***********************************************************Run the code in c++ 11 compiler *
*Program to construct Huffman code and the encode a *
*message entered by the user *
********************************************************** /
/ / include header files
#include
#include
#include
#include
using namespace std;
/ / struct for tree node
struct Node
{
int f;
char ch;
Node *l, *r;
};
/ / allocation of new tree to a node
Node* g_N(char ch, int f, Node* l, Node* r)
{
Node* node = new Node();
/ / assign the node elements
node- ch = ch;
node- f = f;
node- l = l;
node- r = r;
/ / return after all the process has been done
return node;
}
/ / object for comparison
struct comp
{
bool operator()(Node* l, Node* r)
{
/ / the item with highest priority has lowest / / frequency
return l- f r- f;
}
};
/ / traverse and store in an huffman map
void encoding(Node* root, string tx, map huffmanCode)
{
/ / check if the root node is null
if (root == NULL)
return;
/ / if the leaf node is found
if (!root- l !root- r)
huffmanCode[root- ch] = tx;
/ / cal the function to append 0
encoding(root- l, tx + "0", huffmanCode);
/ / call the function to append 1
encoding(root- r, tx + "1", huffmanCode);
}
/ / / build tree and decode
void huff_tree(string inp)
{
/ / to count the frequency
map f;
for (char ch : inp)
f[ch]++;
/ / store live nodes
priority_queue , comp pq;
/ / create leaf node and push the elements
for (auto it : f)
pq.push(g_N(it.first, it.second, NULL, NULL));
/ / perform until more than 1 node in the tree
while (pq.size() != 1)
{
/ / remove nodes with highest priotity
Node *l = pq.top(); pq.pop();
Node *r = pq.top(); pq.pop();
/ / internal node is created and then a new node / / is added
int sum = l- f + r- f;
pq.push(g_N('\0', sum, l, r));
}
/ / pointer is stored to the root of the huffman tree
Node* root = pq.top();
/ / traverse and store the huffman codes
map huffmanCode;
encoding(root, "", huffmanCode);
/ / print the huffman codes
cout "Huffman Code :\n" endl;
for (auto it : huffmanCode)
cout it.first " " it.second endl;
/ / actual string
cout "\n actual string was :\n";
cout inp endl;
/ / print encoded string
string tx = "";
for (char ch : inp)
tx += huffmanCode[ch];
cout "\n encoded string is :\n" tx endl;
}
/ / main function to perform huffman encoding
int main()
{
/ / variable declaration
string inp;
cout "enter the string you want to decode:";
/ / get input from user
cin inp;
/ / call the fuction to generate huffman code
huff_tree(inp);
return 0;
}
Sample Output:
enter the string you want to decode:goodmorning
Huffman Code :
d 1100
g 00
i 1101
m 011
n 111
o 10
r 010
actual string was :
goodmorning
encoded string is :
001010110001110010111110111100

Tags
Choose question tag
close menu
arrow
(Project) Write a program to compress a file using a Huffman code and to decompress a file generated using this code. The program should first read through the file and determine the number of occurrences of each character in the file and the total number of characters in the file. The weight of each character will be the frequency count for that character. The program should then use these weights to construct the Huffman codes for the characters in the file. It should then read the file again and encode it using these Huffman codes and generate a file containing this encoded data. Compute the compression ratio, which is the number of bits in the compressed file divided by the total number of bits in the original file (eight times the number of characters in the file). The program should also provide the option of decompressing a file that was encoded using this Huffman code.
Essay
Answer:
Tags
Choose question tag
close menu
arrow
For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing. long, const, typedef, bool, public, break, else
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5. 000001001
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Construct the Huffman code for the C++ keywords and weights given in the following table: img
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Repeat Exercise 3 for the following table of C++ keywords and weights (frequencies): img
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5. 001101001
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Write a driver program to test your general-tree class template from Exercise 26.
Essay
Answer:
Tags
Choose question tag
close menu
arrow
For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing. unsigned, short, long, int, double, char
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Write a driver program to test your red-black tree class template from Exercise 24.
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5. 00001010011001
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Write a driver program to test your B-tree class template from Exercise 25.
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Use your B-tree class template from Exercise 26 in a program that reads words and constructs a B-tree to store these words. The program should then allow the user to enter a word and should search the B-tree for this word.
Essay
Answer:
Tags
Choose question tag
close menu
arrow
For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing. do, long, new, and, operator, int, namespace
Essay
Answer:
Tags
Choose question tag
close menu
arrow
For Exercises 1-5, trace the construction of the AVL tree that results from inserting the C++ keywords in the given order. Show the tree and balance factors for each node before and after each rebalancing. bool, new, return, struct, while, case, enum
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Using the first Huffman code given in this section (A = 01, B = 0000, C = 0001, D = 001, E = 1), decode the bit strings in Exercises 2-5. 000101001
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Demonstrate that Morse code is not immediately decodable by showing that the bit string 100001100 can be decoded in more than one way.
Essay
Answer:
Tags
Choose question tag
close menu
arrow
Write a driver program to test your AVLTree class template from Exercise 14.
Essay
Answer:
Tags
Choose question tag
close menu
Showing 1 - 20 of 55