Data Structures and Algorithms 2069

A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).

Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.

Huffman Coding is a technique of compressing data to reduce its size without losing any of the details. It is generally useful to compress the data in which there are frequently occurring characters.

Using the Huffman tree, we can compress the string to a smaller size.

Procedure for construction of Huffman tree

1. Calculate the frequency of each character in the string.

2. Sort the characters in increasing order of the frequency. These are stored in a priority queue Q.

3. Make each unique character as a leaf node.

4. Create an empty node z. Assign the minimum frequency to the left child of z and assign the second minimum frequency to the right child of z. Set the value of the z as the sum of the above two minimum frequencies.

5. Remove these two minimum frequencies from Q and add the sum into the list of frequencies.

6. Insert node z into the tree.

7. Repeat steps 3 to 5 for all the characters.

8. For each non-leaf node, assign 0 to the left edge and 1 to the right edge.

Example:

Let us take any four characters and their frequencies:

Now sort these characters according to their frequencies in non-decreasing order.

Here before using Huffman algorithm the total number of bits required is

= 2*(6+3+2+1) = 24 bits.

The tree constructed for the above example is shown below:

Now from variable length code we get following code sequence.

Thus after using Huffman algorithm the total number of bits required is

=1*3+2*3+3*2+6*1=21 bits

Applications of Binary trees

1. Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries.

2. Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered.

3. Binary Tries - Used in almost every high-bandwidth router for storing router-tables.

4. Hash Trees - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.

5. Heaps - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort.

6. Huffman Coding Tree - Used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats. GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers.

7. Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions.

8. Treap - Randomized data structure used in wireless networking and memory allocation.

9. T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5. If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

Algorithm for evaluation of postfix expression

1. Create a stack to store operands.

2.  Scan the given expression from left to right.

3. a) If the scanned character is an operand, push it into the stack.

      b) If the scanned character is an operator, POP 2 operands from stack and perform operation and PUSH the result back to the stack.

4. Repeat step 3 till all the characters are scanned.

5. When the expression is ended, the number in the stack is the final result.

Example:

Let the given expression be “456*+“. We scan all elements one by one.

Tower of Hanoi (TOH) is a mathematical puzzle which consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.

In this problem we transfer all disks from origin peg to destination peg using intermediate peg for temporary storage and move only one disk at a time.

Algorithm for TOH problem:

Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.

1. Assign three pegs A, B & C

2. If n==1

Move the single disk from A to C and stop.

3. If n>1

a) Move the top (n-1) disks from A to B.

b) Move the remaining disks from A to C

c) Move the (n-1) disks from B to C

4. Terminate

Recursion Tree for TOH

1. Move Tower(N-1, BEG, END,AUX)

2. Move Tower(1, BEG, AUX, END) à(BEG à END)

3. Move Tower (N-1, AUX, BEG, END)

Recursion Tree when no. of disks are 4 as:

A binary tree is a finite set of elements that are either empty or is partitioned into three disjoint subsets.

• The first subset contains a single element called the root of the tree.
• The other two subsets are themselves binary trees called the left and right sub-trees of the original tree.

Each element of a binary tree is called a node of the tree.                         

The following figure shows a binary tree with 9 nodes where A is the root.

Applications of Binary Trees

Quick Sort

In quick sort one of the array element is chosen as a pivot element. Then large array is partitioned into two sub arrays one on left side of pivot which holds values smaller than the pivot element and another array on right side of pivot which holds values greater than pivot the pivot value. This procedure of choosing pivot and partition the list is applied recursively until sub-arrays consisting of only one element.

Algorithm:

QuickSort(A, l, r)

{

    if(l<r)

    {

        p = Partition(A,l,r);

        QuickSort(A,l,p-1);

        QuickSort(A,p+1,r);

    }

}

Partition(A, l, r)

{

    x =l; y =r ; p = A[l];

    while(x<y)

    {

       do {

                x++;

         }while(A[x] <= p);

    do {

                y--;

         } while(A[y] >=p);

    if(x<y)

        swap(A[x],A[y]);

}

A[l] = A[y];

A[y] = p;

return y;     //return position of pivot

}

Merge Sort

The basic concept of merge sort is divides the list into two smaller sub-lists of approximately equal size. Recursively repeat this procedure till only one element is left in the sub-list. After this, various sorted sub-lists are merged to form sorted parent list. This process goes on recursively till the original sorted list arrived.

Algorithm:

MergeSort(A, l, r)

{

    If ( l < r)

    { 

         m = (l + r)/2

        MergeSort(A, l, m) 

        MergeSort(A, m + 1, r)

        Merge(A, l, m+1, r)

}

}

Merge(A, B, l, m, r)

{

    x=l, y=m;

    k=l;

    while(x<m && y<r)

    {

        if(A[x] < A[y])

        {

            B[k]= A[x];

            k++;

            x++;

        }

        else

        {

            B[k] = A[y];

            k++;

            y++;

        }

Bubble sort algorithm arranges values by iterating over the list several times and in each iteration the larger value gets bubble up to the end of the list. This algorithm uses multiple passes and in each pass the first and second data items are compared. if the first data item is bigger than the second, then the two items are swapped. Next the items in second and third position are compared and if the first one is larger than the second, then they are swapped, otherwise no change in their order. This process continues for each successive pair of data items until all items are sorted.

Algorithm for Bubble Sort
Let a[n] be an array list of size n.

void bubbleSort(int a[], int n)

{

    int i, j, temp;

    for(i = 0; i < n; i++)

    {

        for(j = 0; j < n-i-1; j++)

        {

            if( a[j] > a[j+1])

            {

                // swap the elements

                temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            } 

        }

    }

Example:

Consider the array list:

                                                                               Source: w3resource.com

Doubly linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.

In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field. Every node in a double linked list contains three fields and they are shown in the following figure...

Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is used to store the address of the next node in the sequence and 'data' field is used to store the actual value of that node.

Steps to insert a nodes at last in doubly linked list

1. Allocate memory for the new node as,

        newnode=(NodeType*)malloc(sizeof(NodeType))

2. Assign value to info field of a new node

        set newnode->info=item

3. set newnode->next=NULL

4. if head==NULL

        set newnode->prev=NULL;

        set head=newnode;

5. if head!=NULL

        set temp=head

        while(temp->next!=NULL)

            temp=temp->next;

        end while

        set temp->next=newnode;

        set newnode->prev=temp

6. End

Binary search is an extremely efficient search technique that searches the given item in minimum possible comparisons in the already sorted list of given elements. The logic behind the technique is:

1. First find the middle element of the list

2. Compare the mid-element with searched item.

    There are three cases:

      a. If it is a desired element then search is successful.

      b. If it is less than desired item then search only in the first half of the list.

      c. If it is greater than desired item then search in the second half of the list.

Recursive Algorithm:

BinarySearch(A,l,r, key)

{

    if(l= = r)

    {

        if(key = = A[l])

            return l+1;         //index starts from 0

        else

            return 0;

    }

     else

    {

        m = (l + r) /2 ;

        if(key = = A[m])

                return m+1;

        else if (key < A[m])

                return BinarySearch(l, m-1, key) ;

        else

                return BinarySearch(m+1, r, key) ;

    }

}

Example:

Consider an array of data:

 21, 36, 56, 79, 101, 123, 142, 203

Now,

Tracing binary search for above data;

Set L=0, R=7, key=123 (search for 123)

Therefore, search successful and key(123) is at position (Mid+1)=5+1=6.

Efficiency:

From the above algorithm we can say that the running time of the algorithm is

T(n) = T(n/2) + O(1)

        = O(logn)

In the best case output is obtained at one run i.e. O(1) time if the key is at middle.

In the worst case the output is at the end of the array so running time is O(logn) time. In the average case also running time is O(logn).

Hashing is a well-known technique to search any particular element among several elements. It minimizes the number of comparisons while performing the search. 

In hashing, an array data structure called as Hash table is used to store the data items. Hash table is a data structure used for storing and retrieving data very quickly. Insertion of data in the hash table is based on the key value. Hence every entry in the hash table is associated with some key. Using the hash key the required piece of data can be searched in the hash table by few or more key comparisons.

    Fig: Hashing Mechanism

Hash function is a function which is used to put the data in the hash table. Hence one can use the same hash function to retrieve the data from the hash table. Thus hash function is used to implement the hash table. The integer returned by the hash function is called hash key.

Collision

The situation in which the hash function returns the same hash key for more than one record is called collision. For e.g.

Consider a hash function:

H(key) = recordkey%10 having the hash table size of 10

The record keys to be placed are: 131, 44, 43, 78, 19, 36, 57 and 77

131%10= 1

44%10=4

43%10=3

78%10=8

19%10=9

36%10=6

57%10=7

77%10=7

Now if we try to place 77 in the hash table then we get the hash key to be 7 and at index 7 already the record key 57 is placed. This situation is called collision. 

Hashing algorithms/ Functions

1. Division Hash Function:

The division hash function depends upon the remainder of division. Typically the divisor is table length. For e.g. If the record 54, 72, 89, 37 is placed in the hash table and if the table size is 10 then the hash function is:

h(key) = record % table size

and key obtained by hash function is called hash key.

54%10=4 

72%10=2 

89%10=9 

37%10=7

2. Mid Square Hash Function:

In the mid square method, the key is squared and the middle or mid part of the result is used as the index. If the key is a string, it has to be preprocessed to produce a number.

Consider that if we want to place a record 3111 then

3111² = 9678321

for the hash table of size 1000

H(3111) = 783  (the middle 3 digits)

3. Multiplicative Hash Function:

The given record is multiplied by some constant value. The formula for computing the hash key is

H(key) = floor(p *(fractional part of key*A))   where p is integer constant and A is constant real number.

Donald Knuth suggested to use constant A = 0.61803398987

If key 107 and p=50 then

H(key) = floor(50*(107*0.61803398987))

     = floor(3306.4818458045)

     = 3306

At 3306 location in the hash table the record 107 will be placed

Big-O notation is a metrics used to find algorithm complexity. Basically, Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

__________________________________________

Analysis of Selection Sort

Time Complexity:

The selection sort makes first pass in n-1 comparison, the second pass in n-2 comparisons and so on.

Time complexity = (n-1) + (n-2) + (n-3) + …………………………. +2 +1

= O(n2)

Space Complexity:

Since no extra space besides 5 variables is needed for sorting

Space complexity = O(n)

A graph is said to be strongly connected if every pair of vertices(u, v) in the graph contains a path between each other. In an unweighted directed graph G, every pair of vertices u and v should have a path in each direction between them i.e., bidirectional path. The elements of the path matrix of such a graph will contain all 1’s. For e.g.

A graph is said to be weakly connected if there doesn’t exist any path between any two pairs of vertices. Hence, if a graph G doesn’t contain a directed path (from u to v or from v to u for every pair of vertices u, v) then it is weakly connected. The elements of such a path matrix of this graph would be random. For e.g.

Weighted Graph

A weighted graph is a graph G, in which each edge, e, is assigned a non-negative real number, w(e), called the weight of e. For e.g.

Merits of Contiguous List / array

• It is used to represent multiple data items of same type by using only single name.

• It can be used to implement other data structures like linked lists, stacks, queues, trees, graphs etc.

• 2D arrays are used to represent matrices.

• Implementation of list using array is easier as compared other implementation.

Demerits of Contiguous List / array

• The size of the array is fixed. Most often this size is specified at compile time. This makes the programmers to allocate arrays, which seems "large enough" than required.

• Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.

• Deleting an element from an array is not possible. Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are weak.

• Generally array's allocates the memory for all its elements in one block whereas linked lists use an entirely different strategy. Linked lists allocate memory for each element separately and only when necessary.

Merits of Linked List

1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program.

2. Linked lists have efficient memory utilization. Here, memory is not preallocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.

3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.

4. Many complex applications can be easily carried out with linked lists.

5. There is no need to define an initial size for a Linked list.

6. Linked List reduces the access time.

Demerits of Linked List

1. They use more memory than arrays because of the storage used by their pointers.

2. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.

3. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.

4. Nodes are stored in-contiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.