Question

In all algorithm, always explain how and why they work. ALWAYS, analyze the complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. In all data structures, try to minimize as much as possible the running time of any operation.

1.Show that if a binary tree has a vertex with a single child, then this can not be an optimal Huffman tree.

2. Question 2: Say that the input for an Huffman coding contains 256 letters. Each appearing the the same number of times. (a) If we choose to code all letters by codes of the same length, what is the number of bits required? (b) Is the Huffman code better than the code of the first item?

3. Question 3: Say that we code 256 different letters. Let num(X) be the number of times an arbitrary letter appears in the text . Assume that for every X and Y both num(Y ) > num(X)/2 and num(X) > num(Y)/2 hold. Is the ASCII (8 bits) code worse than the Huffman code in this case?

Answer 1

Answer;

Below is the recursive algorithm which performs the desired task. In this algorithm name "find(root,height,number_of_nodes, h)", root is the pointer to root of present subtree, variable height and number_of_nodes are passed by reference such that we are updating the value of vairable height and variable number_of_nodes as per the result returned in recursive call and this value change in recursive call will be reflected in original call.

Also in below algorithm, we are checking if height of a particular subtree is equal to h or not. If height is equal to h, then we are updating the vairable maximum_nodes accordingly.*********THE END********** Please vote