Test: Greedy - Computer Science Engineering (CSE) MCQ

Total number of characters in the message = 100.
Each character takes 1 byte. So total number of bits needed = 800.

After Huffman Coding, the characters can be represented with:
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

Total number of bits needed = 224
Hence, number of bits saved = 800 - 224 = 576
See here for complete explanation and algorithm.

O(nlogn) where n is the number of unique characters. If there are n nodes, extractMin() is called 2*(n – 1) times. extractMin() takes O(logn) time as it calles minHeapify(). So, overall complexity is O(nlogn). See here for more details of the algorithm.

The Huffman Tree generated is: 

The word dead can be represented as: 101 111 1100 101 However, the alternative codeword can also be found by assigning 1 to the left edge and 0 to the right edge of the tree, i.e. dead can also be represented as: 010 000 0011 010 See here for more details of the algorithm.

Huffman coding is a lossless data compression algorithm. The codes assigned to input characters are Prefix Codes, means the codes are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character. This is how Huffman Coding makes sure that there is no ambiguity when decoding.

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

A and B are False  : The idea behind Prim’s algorithm is to construct a spanning tree - means all vertices must be connected but here vertices are disconnected C. False. Prim's is a greedy algorithm and At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. In this option weight of AB<AD so must be picked up first. D.TRUE. It represents a possible order in which the edges would be added to construct the minimum spanning tree. Prim’s algorithm is also a Greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.