What is a minimum spanning tree ? Describe Huffman’s Algorithm.
A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees; for instance the complete graph on four vertices
Huffman Algorithm
Huffman’s algorithm is a method for building an extended binary tree with a minimum weighted path length from a set of given weights.
Huffman coding is based on the frequency of occurance of a data item (pixel in images). The principle is to use a lower number of bits to encode the data that occurs more frequently. Codes are stored in a Code Book which may be constructed for each image or a set of images. In all cases the code book plus encoded data must be transmitted to enable decoding.
The Huffman algorithm is now briefly summarised:
· A bottom-up approach
1. Initialization: Put all nodes in an OPEN list, keep it sorted at all times (e.g., ABCDE).
2. Repeat until the OPEN list has only one node left:
(a) From OPEN pick two nodes having the lowest frequencies/probabilities, create a parent node of them.
(b) Assign the sum of the children's frequencies/probabilities to the parent node and insert it into OPEN.
(c) Assign code 0, 1 to the two branches of the tree, and delete the children from OPEN.
Symbol Count Code Subtotal (# of bits)
---------- ----- --------- --------------------
A 11 0 11
B 5 100 15
C 6 101 18
D 5 110 15
E 6 111 18
TOTAL (# of bits): 77
The following points are worth noting about the above algorithm:
Decoding for the above two algorithms is trivial as long as the coding table (the statistics) is sent before the data. (There is a bit overhead for sending this, negligible if the data file is big.)
Unique Prefix Property: no code is a prefix to any other code (all symbols are at the leaf nodes) -> great for decoder, unambiguous.
If prior statistics are available and accurate, then Huffman coding is very good.
In the above example:
Number of bits needed for Huffman Coding is: 77 / 33 = 2.3
Construct an AVL tree using the below list. Show all the steps 12, 11, 13, 10, 09, 15, 14, 18, 7, 6, 5.
What is the benefit of using arrays of pointers instead of several pointer variables?
Difference between Statement coverage and Branch coverage.
Distinguish Testing vs. Quality Control & Assurance and Audit
Briefly discuss about Critical Path Method (CPM)
Write a C program to convert binary to decimal using function.