Huffman Coding

It is a Greedy Approach.It is an compression technique used to encode compress data. It is used for reducing the size of data of message. If we store the data on the file than we need compression to reduce the size of file. When the the data is send over a network than the data is compress and send to reduce the cost of transmission.

This approach is very simple. In this approach we simply merge those set of files / elements which have smaller values.it follow optimal search pattern.

For understanding Optimal Merge Problem, Let we understand simple merging.

Suppose if we have two shorted list. Marge these two list and create a third list.

Let we first understand , what is spanning tree ?

A sub graph suppose S of graph G having V vertices and E edges is said to be spanning tree if following properties must be satisfied.

1. S must contain all vertices of G.

2. S must contain (|V|-1) edges.

3. There is no close loop inside S.

Let we discuss about Job sequencing problem. This is a maximisation problem means If we have so many jobs with their respective profit and timeline. We try to arrange jobs in such a way that we will get more profit and here we must careful about timeline because timeline is like a constraint that we must follow the given time line for respective job.

Knapsack Problem is an application of Greedy Strategy / Method. By Knapsack problem we will find maximum profit. There are so many solution to solve any problem but we will select those solution which generate maximum profit.

Let here we see what the knapsack problem says by the help of an example.

Suppose we have some objects and every object is associated to some profit(p) and weight (w).