Consider the following string saved into a string type variable. We want to send it over the network to another computer. Use the given string and answer (solve) the questions given below. String: “Data Structures is one of the core courses of BS(CS) program.” Note: Double quotes are not the part of string. a. Build frequency table and Huffman encoding tree. [14 Marks] Use the following sample frequency table: Character Frequency Number of Bits used without any encoding Huffman code of each character Number of Bits used with Huffman encoding b. Calculate how many bits will be used for the above string: [6 Marks]  Without using any encoding technique  With Huffman encoding technique  What percentage of bits is saved by Huffman encoding scheme? in C++ language

a. Building frequency table and Huffman encoding tree:

First, we need to count the frequency of each character in the string. For simplicity, let's consider only a few characters from the string "Data Structures".

Character: D, a, t, , S, t, r, u, c, t, u, r, e, s Frequency: 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1

Without any encoding, each character is typically represented using 8 bits.

To build the Huffman encoding tree, we start by creating a node for each character and its frequency. We then combine the two nodes with the lowest frequency to create a new node with a frequency that is the sum of the two. We repeat this process until there is only one node left, which is the root of the Huffman tree.

The Huffman code for each character is the path from the root to the character in the tree, where going to the left child adds a 0 and going to the right child adds a 1.

For example, if we have the following Huffman tree:

    (14)
   /    \
(7)      (7)

/ \ /
(3) (4) (3) (4) / \ / \ / \ /
D a t S r u c e

The Huffman code for 'D' would be '00', for 'a' would be '01', for 't' would be '10', and so on.

b. Calculating the number of bits used:

Without using any encoding technique, each character uses 8 bits, so the total number of bits used would be 8 * length of the string.

With Huffman encoding, the number of bits used for each character depends on its frequency. For example, in the above tree, 'D' uses 2 bits, 'a' uses 2 bits, 't' uses 2 bits, and so on.

The percentage of bits saved by Huffman encoding can be calculated as (1 - (total bits with Huffman / total bits without Huffman)) * 100%.

In C++ language, you can use a priority queue to build the Huffman tree and a map to store the Huffman codes for each character. The calculation of the total bits used and the percentage saved would involve iterating over the string and the map.