Write short notes on: i) Minimum Cost Spanning Tree ii) Sparse Huffman Coding and its implementation iii) Define Huffman codes.

i) Minimum Cost Spanning Tree:

In a weighted connected graph, a minimum cost spanning tree (MCST) is a subset of the edges that connects all vertices without any cycles and has the minimum possible total edge weight. Finding an MCST is a classical problem in computer science with applications in network optimization, clustering, and VLSI design.

Prim's Algorithm:

Prim's algorithm starts with an empty spanning tree. It iteratively adds the cheapest edge that connects a vertex in the tree to a vertex not yet in the tree. The algorithm stops when all vertices are added to the tree.

Kruskal's Algorithm:

Kruskal's algorithm starts with a forest of all the vertices as separate trees. It iteratively merges the two trees with the smallest edge weight until all vertices are in the same tree.

Applications:

• Network optimization: MCSTs can be used to design networks with minimal cost, such as telecommunication networks or electrical grids.
• Clustering: MCSTs can be used to cluster data points into disjoint groups such that the sum of the distances between points in the same group is minimized.
• VLSI design: MCSTs can be used to design the layout of integrated circuits to minimize the total wire length.

ii) Sparse Huffman Coding:

Sparse Huffman coding is a data compression algorithm that assigns shorter codes to more frequent symbols and longer codes to less frequent symbols. It is a variant of Huffman coding, which is an optimal prefix code.

Implementation:

Sparse Huffman coding can be implemented using a priority queue, which is a data structure that maintains a list of elements in order of their priority. In this case, the priority of an element is its frequency.

The algorithm starts by inserting all symbols into the priority queue. Then, it repeatedly merges the two elements with the lowest priorities into a new element, which is the parent of the two elements. The priority of the new element is the sum of the priorities of its children.

This process continues until there is only one element left in the priority queue. The code for each symbol is then the path from the root of the tree to the symbol's leaf node.

Applications:

• Data compression: Sparse Huffman coding can be used to compress data by reducing the number of bits required to represent each symbol.
• Error correction: Sparse Huffman coding can be used to correct errors in data transmission by adding redundant bits to the code.

iii) Huffman Codes:

A Huffman code is a prefix code that assigns shorter codes to more frequent symbols and longer codes to less frequent symbols. This allows for more efficient data compression because the more frequent symbols are represented by fewer bits.

Properties:

• Prefix code: No codeword is a prefix of any other codeword.
• Optimal: Huffman codes are optimal in the sense that they minimize the average codeword length.

Applications:

• Data compression: Huffman codes are used in a variety of data compression algorithms, including ZIP, GZIP, and PNG.
• Error correction: Huffman codes can also be used for error correction, as they can be used to detect and correct errors in data transmission.