ALGORITHM

              Order Statistics

The Kth order statics of n elements is the Kth smallest element of array.
Median is the n/2th order statics or say halfway point of the set.
When n is odd the median is unique,occuring at i=(n+1)/2.
When n is even there are two medians,lower median,occuring at i=n/2 and upper median,occuring at i=n/2+1.

Kth-selection:-

->Find an element x such that l<=cn elements are less than or equal to x and r<=cn elements are greater than x,for some c<1.
->Partition input into elements<=x and elements>x.
->if l=k-1 report x.

Find_pivot(A,p,r)

1) m<-ceiling(n/5)
2) for i=1 to m
3)   do sort array A[5i-4,min(5i,r)]
4) A1[i]<-median of A[5i-4,min(5i,r)]
5) return select(A1,1,m,m/2)

          HUFFMAN CODING TREES

Huffman coding is a greedy algorithm.It compresses data by using fewer bits to encode more frequently occuring characters so that not all characters are encoded with 8 bits.

Prefix Code

Codes such that no codeword is prefix of some other codeword,such codes are called prefix codes.

HUFFMAN CODING TREE

High frequency characters are placed at lower depth :- lower code.
Low frequency characters are placed at higher depth :-higher code.
For an alphabet containing n letters,Huffman algorithm starts with n vertices,one for each letter labeled with that letter and its frequency.This is a forest of n trees, each of one vertex.

We than determine the two vertices of lowest frequency and replace them with a tree whose root is labled with the sum of these two frequencies and whose two childern are the two vertices that are replaced.We repeatedly do this until single tree left.

Huffman coding tree always produce a variable length code with minimum description length for that string.

Algorithm to make Huffman tree:-

Huffman(c)
1)  n<-|c|
2)  q<-c
3)  for i<-1 to n-1
4)     do allocate a new node z
5)        left[z]<-x<-Extract-min(q)
6)        right[z]<-y<-Extract-min(q)
7)        f[z]<-f[x]+f[y]
8)        insert(q,z)
9)  return Extract-min(q)

Average case complexity for Kth smallest element partition method:-

    T(n)=T(m)+O(n)          m<-1 to n-1
->  E[T(n)]=E[T(m)]+O(n)
->  E[1/n (T(1)+T(2)+.......+T(n-1)]+O(n)
->  cn2/n+O(n)
->  cn+O(n)

For more details refer to the following link.
huffman coding