Quiz+ | Quiz 15: Graphs and Digraphs

Q 1

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

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

Q 2

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

Free

Essay

Problem plan: • Include the required header files into the program. • Declare the constant values • Declare "struct" for node • Define the class to compare the left and right side values o Use boolean function for operator o Return if left value is greater than right value • Type define for "priority queue" • Generate the "trie" code • Define a function "code()" to generate the code o Initialize the static string o Check if the right side of the node is not null o Fill the right substring with "1" o Again call the function o Fill until all the right sub tree values are full o Check if there is no string o Assign the values to the string • Define the function "cnt()" function to count values in the text file o Initilaise the required variables o Ifsteram to open the input file o Get the values from file one by one o Start counting the values o Use "while" loop to check if the input is text • If the count is greater or equal to "0" and less than size • Increment the count value o Close the input file • Define the function "bstrngstring()"to check the input file o Initialize the variable for input o Initialize a blank string o Get the input values for the file o Use while loop to check if the input is text. o Close the file • Define the "main()" function to demonstrate Huffman encoding o Initialize the required variables o Message for user to enter an option o Switch case to encode or decode o When user enters "a" • Request the user to enter the input file • Get the filename from the user • Print the input file name • Print the output filename • Open the output file and store the results • Print the results in the output file • Loop to print the left count value • Loop to push values using a temp variable o Call the function "code()"to go to the top of queue o Create a bit code string o Set the bit string value o Once the encoding is done find the compression ratio o Otherwise print stating that there is an error o When the user enters "b" • Request the user to enter the file name • Get input file from user • Open the input file • Obtain the input from the user one by one • Check for the magic number • Check for the match in the input file • For loop to read the letter count • Get the input from the user • Add the valid values to the priority queue o Create "trie" code o Create "bit" codes o Loop until input is not equal to "#" o Print to the output file the value of "j" o Assign the bit string value to be blank o Print when the input by user is not valid o Close the output file Program: / ***********************************************************Program to encode and decode a file using Huffman coding * ********************************************************** / / / include header files #include #include #include #include #include #include "bChar.h" / / declare the constant values const std::string m_num = "7771234777"; const int asze = 256; int l_Cnt[asze]; std::string st_cd[asze]; / / declare struct for node struct t_nd { char ch; int cnt; t_nd* l; t_nd* r; }; / / define the class to compare the left and right side / / values class cpre { public: / / boolean function for operator bool operator()(const t_nd* left_sde, const t_nd* right_sde) const { / / return if left value is greater than right / / value return left_sde- cnt right_sde- cnt; } }; / / make of the node t_nd* makeT_nd(char ch, int cnt) { / / temp value for node t_nd* tmp = new t_nd; / / assign the temp value to point to the character, / / count, left tmp- ch = ch; tmp- cnt = cnt; tmp- l = NULL; tmp- r = NULL; return tmp; }; / / typedef for priority queue typedef std::priority_queue , cpre p_q; / / to try fotr multiple values in the queue void tyr(p_q _h) { / / loop until the size is less than 1 while (_h.size() 1) { t_nd* holder = new t_nd; holder- l = _h.top(); _h.pop(); holder- r = _h.top(); _h.pop(); holder- cnt = holder- l- cnt + holder- r- cnt; holder- ch = -1; _h.push(holder); } } / / function to generate the code void code(t_nd* _h) { / / initialise the static swtring static std::string bstrng = ""; / / check if the right side of the node is not null if (_h- r != NULL) { / / fill the right substring with 1 bstrng += "1"; / / again call the function code(_h- r); / / fill until all the right sub stree values are / / filled with 1 bstrng = bstrng.substr(0, bstrng.size() - 1); } / / check if the left value is not null if (_h- l != NULL) { / / fill the right substring with 0 bstrng += "0"; / / again call the function for left node code(_h- l); / / fill until all the left sub stree values are / / filled with 0 bstrng = bstrng.substr(0, bstrng.size() - 1); } / / check if there is no string if (!_h- l !_h- r) { / / assign the values to the string st_cd[_h- ch] = bstrng; } } / / to count the values in the text file void cnt(std::string txt_fl, int _h) { / / initilaise the required variables char wrd; / / ifstram to open the input file std::ifstream inf(txt_fl.c_str()); / / get the values from file one by one inf std::noskipws; / / start counting the values for (int i = 0;i asze; ++i) l_Cnt[i] = 0; / / use while loop to check if the input is text while (inf wrd) { / / if the count is greater or equal to 0 and less / / than size if (wrd = 0 wrd asze) { / / increment the count value ++l_Cnt[wrd]; ++_h; } } / / close the file inf.close(); } / / function to check the input file std::string bstrngstring(std::string i_F) { / / initialise the variable for input char input; / / initialise a blank string std::string bstrng = ""; std::ifstream inf(i_F.c_str()); / / get the input values fro the file inf std::noskipws; / / use while loop to check if the input is text while (inf input) { bstrng += st_cd[input]; } / / close the file inf.close(); bstrng += st_cd[3]; return bstrng; } / / Function main int main(int argc, char** argv) { / / initialize the required variables int r_c; char ch; unsigned char ch_in; std::string i_F = "", o_Txt_fl = "", bstrng = "", bstrngsub = "", mn = ""; std::ofstream o_F; std::ifstream inf; p_q pq; bChar bchar; int o_sze = 0; / / message for user to enter an option std::cout "select (a / b)\n" std::endl "a. to encode a file" std::endl "b. to decode a file" std::endl; std::cin ch; / / switch case to encode or decode switch (ch) { / / when user enters 'a' case 'a': / / request the user to enter the input file std::cout "please enter file to be encoded: " std::endl; / / get the filename from the user std::cin i_F; / / the output file o o_Txt_fl = i_F + ".txt"; / / print the input file name std::cout std::left std::setw(17); std::cout "Input file: " i_F std::endl; / / print the output filename std::cout std::left std::setw(17); std::cout "Output file:" o_Txt_fl std::endl; std::cout std::endl; / / open the output file and store the results o_F.open(o_Txt_fl.c_str()); cnt(i_F, o_sze); if (l_Cnt[3] == 0) l_Cnt[3] = 1; / / print the results in the output file o_F m_num std::endl; o_F i_F std::endl; / / loop to print the left count value for (int i = 0; i asze; ++i) { o_F l_Cnt[i] " "; } o_F std::endl; / / loop to push values using a temp variable for (int i = 0; i asze; ++i) { if (l_Cnt[i] 0) { / / call the function "makeT_nd" t_nd* tmp = makeT_nd(i, l_Cnt[i]); pq.push(tmp); } } / / call the functiiion to go to the top of queue tyr(pq); code(pq.top()); / / to create a bit code string bstrng = bstrngstring(i_F); o_F '#'; / / set the bit string value bchar.setbstrng(bstrng); o_F std::noskipws; r_c = bchar.i_R(o_F); / / once the encoding is done if (r_c == bstrng.length()) { std::cout "Encoding is done successfully! :)" std::endl; / / find the compression ratio std::cout "The ration of compression: " (float)r_c / ((float)o_sze * 8.0) * 100.0 "%" std::endl; } else { / / otherwise print stating that there is an / / error std::cout "there is an error :(" std::endl; std::cout "Expected: " bstrng.length() * 8 " but got: " r_c std::endl; } break; / / when the user enters b case 'b': / / request the user to enter the file name std::cout "Please enter the file to be decoded: " std::endl; / / get input file from user std::cin i_F; / / open the input file inf.open(i_F.c_str()); / / obtain the input form the user one by one inf mn; / / check for the magic number if (mn != m_num) { std::cout "the numbers does not match" std::endl; return 1; } inf o_Txt_fl; / / check for the match in the input file if (o_Txt_fl != i_F.substr(0, i_F.length() - 4)) { std::cout o_Txt_fl " " std::cout "no match found but the decoding can be performed" std::endl; } o_F.open(o_Txt_fl.c_str()); / / for loop to read the letter count for (int i = 0; i asze; ++i) { / / get the input from the user inf l_Cnt[i]; if (l_Cnt[i] 0) { / / add the valid values to the the / / priority queue t_nd* tmp = makeT_nd(i, l_Cnt[i]); pq.push(tmp); } } / / to create trie code tyr(pq); / / to create bit codes code(pq.top()); / / loop until input is not equal to "#" while (ch_in != '#') { inf ch_in; } inf std::noskipws; while (inf ch_in) { bstrng += bchar.g_B(ch_in); } / / close the input dile inf.close(); for (int i = 0; i bstrng.length(); ++i) { / / increment the value of bit string variable bstrngsub += bstrng[i]; for (int j = 0; j asze; ++j) { / / check if the bit string is equal to / / string code if (bstrngsub == st_cd[j]) { / / if it is an end of file if (j == 3) { / / go to the newline o_F "\n"; i = bstrng.length(); / / then exit break; } / / print to the output file the / / value of j o_F (char)j; / / assign the bit string value to / / be blank bstrngsub = ""; break; } } } break; default: / / print when the input by user is not valid std::cout "your choice is invalid" std::endl; break; } / / close the output file o_F.close(); return 0; } bChar.h: / / include header files #include #include #include #include / / class definition for bChar class bChar { public: / / declare the variables in public unsigned char* c; int shift_cnt; std::string bstrng; / / function call for bchar() bChar(); void setbstrng(std::string _h); int i_R(std::ofstream outf); std::string g_B(unsigned char _h); void w_R(std::ofstream outf); ~bChar(); }; / / include the required files #include "bChar.h" / / include the ffunction from the header "bChar.h" bChar::bChar() { shift_cnt = 0; c = (unsigned char*)calloc(1, sizeof(char)); } / / this function will return how many bits are been inserted void bChar::setbstrng(std::string _h) { bstrng = _h; } int bChar::i_R(std::ofstream outf) { int tot = 0; / / check the length of the bit string while (bstrng.length()) { if (bstrng[0] == '1') *c |= 1; *c = 1; ++shift_cnt; ++tot; bstrng.erase(0, 1); / / check if the shift count is 7 if (shift_cnt == 7) { / / write the results to the output file w_R(outf); shift_cnt = 0; free(c); c = (unsigned char*)calloc(1, sizeof(char)); } } / / check for trailing bits if (shift_cnt 0) { / / if there is a trailing bit then push it *c = (8 - shift_cnt); w_R(outf); free(c); c = (unsigned char*)calloc(1, sizeof(char)); } return tot; } / / the output is given in binary format std::string bChar::g_B(unsigned char _h) { std::stringstream _itoa; int _size = sizeof(unsigned char) * 8; for (unsigned _s = 0; _s _size - 1; ++_s) { _itoa ((_h (_size - 1 - _s)) 1); } return _itoa.str(); } / / function to write the bits void bChar::w_R(std::ofstream outf) { outf *c; } / / destructor for the method "bChar()" bChar::~bChar() { if (c) free(c); } Sample Input file: Maria is studying to become an immigration lawyer. At her university alone there are more than a thousand undocumented students; so many, they have established a support centre. Cities like Los Angeles have vowed to fight to defend immigrant communities from Mr Trump's policies Sample Output: select (a / b) a. to encode a file b. to decode a file a please enter file to be encoded: f1.txt Input file: f1.txt Output file: f1.txt.txt Encoding is done successfully! :) The ration of compression: 55.3191% f1.txt.mpc : 7771234777 f1.txt 0 0 0 1 0 0 0 0 0 0 3 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 41 0 0 0 0 0 0 1 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 16 2 5 9 29 3 5 9 19 0 1 6 12 16 16 4 0 14 16 21 9 4 2 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Q 3

Write a driver program to test your AVLTree class template from Exercise 14.

Free

Essay

Problem plan: • Include the required header files into the program. • Declare the AVL node class template • Now define the template class for AVL node o Initialize the required variables o Assign values to all the node variables o Delete the nodes • Define the class template for AVL tree node. o Declare the required functions o Initialize the root node o Declare the function to rotate right o Declare the function to rotate left o Declare the function to rotate left then right o Declare the function to rotate right then left o Declare the other functions to re-balance a tree, find height, set balance, print balance and clear nodes • Define the functions • Define the "main()" function to demonstrate the AVL tree class template o Create an object for AVL tree class o Start inserting the values into the tree o Call the function "prnt_bal()" to print the results Program: / ***********************************************************Program to test AVL Tree class template * ********************************************************** / / / include the required header files #include #include using namespace std; / / AVL node class template template / / class definition class AVL_node { public: / / initialise the required variables T key; int balance; AVL_node *l, *r, *parent; / / assign values to all the node variables AVL_node(T k, AVL_node *p) : key(k), balance(0), parent(p), l(NULL), r(NULL) {} / / delete the nodes ~AVL_node() { delete l; delete r; } }; / / template for AVLTree class template / / class definition class AVLtree { public: / / declare the required functions AVLtree(void); ~AVLtree(void); / / to insert the values into the tree bool insert(T key); / / to delete the constant value k void del_K(const T key); / / to print the balance void prnt_bal(); private: / / initialize the root node AVL_node *root; / / initilaise to rotate left AVL_node * LL(AVL_node *a); / / initilaise to rotate right AVL_node * RR(AVL_node *a); / / initilaise to rotate left then right AVL_node * LR(AVL_node *n); / / initialize to rotate right then left AVL_node * RL(AVL_node *n); / / to re_bal the tree void re_bal(AVL_node *n); / / to find the ht of the tree int ht(AVL_node *n); / / to set the balance of the tree void st_bal(AVL_node *n); / / to print the balance of the tree void prnt_bal(AVL_node *n); / / to clear the nodes void clr_n(AVL_node *n); }; / / AVL tree class definition template / / function definition for rebalancing the nodes void AVLtree ::re_bal(AVL_node *n) { st_bal(n); / / if the balance is -2 if (n- balance == -2) { / / if the height of left is greater than height of / / right if (ht(n- l- l) = ht(n- l- r)) / / then perform RR rotation n = RR(n); else / / otherwise perform LR rotation n = LR(n); } / / if the balance is 2 else if (n- balance == 2) { / / if the height of the right tree is greater than / / height of left right if (ht(n- r- r) = ht(n- r- l)) / / perform LL rotation n = LL(n); else / / perform RL rotation n = RL(n); } / / if the parent node is null if (n- parent != NULL) { / / perform rebalancing the tree re_bal(n- parent); } else { / / assign the root to n root = n; } } / / template function for LL rotation template / / perform LL rotation AVL_node * AVLtree ::LL(AVL_node *a) { / / assign right of a to b AVL_node *b = a- r; / / a is assigned to parent of b b- parent = a- parent; / / left of b is assigned to right of b a- r = b- l; / / check if the right of a is not equal to null if (a- r != NULL) a- r- parent = a; / / a is assigned to left of b b- l = a; / / b is assigned to parent of b a- parent = b; / / if the parent of b is not NULL if (b- parent != NULL) { if (b- parent- r == a) { b- parent- r = b; } else { b- parent- l = b; } } / / set balance of a st_bal(a); / / set balance of b st_bal(b); return b; } template / / template function for RR rotation AVL_node * AVLtree ::RR(AVL_node *a) { AVL_node *b = a- l; / / parent of a is assigned to parent of b b- parent = a- parent; / / right of b is assigned to left of a a- l = b- r; / / check if left of a is NULL if (a- l != NULL) a- l- parent = a; / / a is assigned to right of b b- r = a; / / b is assigned to parent of a a- parent = b; / / check if parent of b is NULL if (b- parent != NULL) { if (b- parent- r == a) { b- parent- r = b; } else { b- parent- l = b; } } / / set balance of a st_bal(a); / / set balance of b st_bal(b); return b; } / / template LR rotation template / / perform LR rotation AVL_node * AVLtree ::LR(AVL_node *n) { n- l = LL(n- l); return RR(n); } / / template function for RL rotation template AVL_node * AVLtree ::RL(AVL_node *n) { n- r = RR(n- r); return LL(n); } template / / find the height of the tree int AVLtree ::ht(AVL_node *n) { if (n == NULL) return -1; return 1 + max(ht(n- l), ht(n- r)); } / / set the balance of the tree template void AVLtree ::st_bal(AVL_node *n) { n- balance = ht(n- r) - ht(n- l); } / / print the balance node template / / define the function to print the tree void AVLtree ::prnt_bal(AVL_node *n) { / / check if n is not NULL if (n != NULL) { / / cal the function to print the left tree prnt_bal(n- l); cout n- balance "\n"; / / call the function to print the right tree prnt_bal(n- r); } } template / / check if the AVL tree is NULL AVLtree ::AVLtree(void) : root(NULL) {} / / check if the AVL tree is void then delete the root node template AVLtree ::~AVLtree(void) { / / delete the root value delete root; } / / template class to insert element into the tree template / / define the function insert the node bool AVLtree ::insert(T key) { / / check if the root value is NULL if (root == NULL) { root = new AVL_node (key, NULL); } else { AVL_node *n = root, *parent; / / use while loop to insert the element into the / / tree while (true) { / / check if the n of key equals to key if (n- key == key) return false; / / n is assigned to the parrent parent = n; bool g_L = n- key key; / / if the control goes to left then n is / / right otherwise left n = g_L ? n- l : n- r; / / check if the n value is null if (n == NULL) { if (g_L) { / / left of the parent is set to new / / AVL node parent- l = new AVL_node (key, parent); } else { / / right of the parent node is set / / to new AVL node parent- r = new AVL_node (key, parent); } / / rebalance the parent node re_bal(parent); break; } } } return true; } / / template class for deletion template / / function to delete the values void AVLtree ::del_K(const T d_k) { if (root == NULL) return; / / assign nodes with the respective values AVL_node *n = root, *parent = root, *d_N = NULL, *child = root; / / use while loop to check the nodes one by one whether / / it is balanced and then delete the nodes while (child != NULL) { / / if the value is not null the assign n to parent / / node parent = n; / / assign child to n n = child; child = d_k = n- key ? n- r : n- l; / / check if the key to be deleted is equal the / / node if (d_k == n- key) d_N = n; } / / if the delete key value is not null if (d_N != NULL) { / / then the key is assigned to delete node d_N- key = n- key; / / now the left node is assigned to the child child = n- l != NULL ? n- l : n- r; / / if the root is assigned to the delete key node if (root- key == d_k) { / / childe is assigned to the root node root = child; } else { / / if the left of parent is n if (parent- l == n) { / / then assign the child to left parent- l = child; } else { / / otherwise assign right to the child parent- r = child; } / / call the function to rebalance the nodes / / again re_bal(parent); } } } / / template class to print the balance template void AVLtree ::prnt_bal() { prnt_bal(root); cout endl; } / / main function to demonstarte AVLTree class int main(void) { / / create an object for AVL tree class AVLtree t; / / start inserting the values into the tree cout "Inserting values into the tree one by one....." endl; / / insert values into the tree t.insert(11); t.insert(33); t.insert(22); t.insert(55); t.insert(44); t.insert(99); t.insert(77); t.insert(88); t.insert(66); / / print the values cout "Print the balance factor: "; / / call the function to print the results t.prnt_bal(); } Sample Output: Inserting values into the tree one by one..... Print the balance factor: 0 0 0 1 1 0 0 0 -1

Q 4

Write a driver program to test your red-black tree class template from Exercise 24.

Essay

Q 5

Write a driver program to test your B-tree class template from Exercise 25.

Essay

Q 6

Write a driver program to test your general-tree class template from Exercise 26.

Essay

Q 7

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

Q 8

Demonstrate that Morse code is not immediately decodable by showing that the bit string 100001100 can be decoded in more than one way.

Essay

Q 9

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

Q 10

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

Q 11

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

Q 12

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

Q 13

Construct the Huffman code for the C++ keywords and weights given in the following table:

Essay

Q 14

Repeat Exercise 6 for the following table of letters and weights:

Essay

Q 15

Using the Huffman code developed in Exercise 7, encode the message "feed a deaf aged hag".

Essay

Q 16

Repeat Exercise 3 for the following table of C++ keywords and weights (frequencies):

Essay

Q 17

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

Q 18

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

Q 19

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

Q 20

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

Q 21

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, enum, if, this, else, case, void, do, return, unsigned, false, true, double, while

Essay

Q 22

Proceed as in Exercises 1-5, but for the following collections of numbers: 22, 44, 88, 66, 55, 11, 99, 77, 33

Essay

Q 23

Proceed as in Exercises 1-5, but for the following collections of numbers: 11, 22, 33, 44, 55, 66, 77, 88, 99

Essay

Q 24

Proceed as in Exercises 1-5, but for the following collections of numbers: 99, 88, 77, 66, 55, 44, 33, 22, 11

Essay

Q 25

Proceed as in Exercises 1-5, but for the following collections of numbers: 55, 33, 77, 22, 11, 44, 88, 66, 99

Essay

Q 26

Proceed as in Exercises 1-5, but for the following collections of numbers: 50, 45, 75, 65, 70, 35, 25, 15, 60, 20, 41, 30, 55, 10, 80

Essay

Q 27

Proceed as in Exercises 1-5, but for the following collections of numbers: Draw diagrams for a simple left rotation similar to those in the text for the simple right rotation. Also describe what links must be reset to accomplish this rotation.

Essay

Q 28

Proceed as in Exercises 1-5, but for the following collections of numbers: Draw diagrams for a right-left rotation similar to those in the text for the left-right rotation. Also describe what links must be reset to accomplish this rotation.

Essay

Q 29

Proceed as in Exercises 1-5, but for the following collections of numbers: Design and test an AVLTree class template.

Essay

Q 30

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given: 55, 66, 44, 77, 33, 88, 22, 99, 11

Essay

Q 31

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given: 55, 66, 77, 88, 99, 11, 22, 33, 44

Essay

Q 32

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given: 11, 22, 33, 44, 55, 66, 77, 88, 99

Essay

Q 33

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given: 99, 88, 77, 66, 55, 44, 33, 22, 11

Essay

Q 34

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given: B, E, A, N, S

Essay

Q 35

For Exercises 1-6, draw the 2-3-4 tree that results when the values are inserted in the order given: C, O, R, N, F, L, A, K, E, S

Essay

Q 36