Posts

Rabin-Karp Algorithm

-
String Matching: A string (say txt) and a pattern( smaller string say pat) are given and ask for finding the position of pat in txt. Let the length of txt = n and length of pat is m. Method 1: Naive Approach     Traverse string txt from 0 to (n-m+1) and in every round check if part of txt match with pat character by character. The time complexity of this algorithm will be O(m*n) . Method 2: Rabin-Karp algorithm     In this method, we use a hash function to hash pat and hash part of txt of size m and apply the rolling hash method and is the hash function of part of txt match with pat then check pat and txt character by character.     Time Complexity: O(n-m+1) Average     Time Complexity: O(n-m+1) Worst           eg: txt : a a a a a b    and      pat: a a b     Let the hashing begin with 1 and end with 26 as:           hash(a): 1           hash(b): 2           -----------           -----------           hash(z): 26           hash(a a a): 1+1+1=3           hash(a a b): 1+1+2=4        
Post a Comment
Read more

Quick Sort

-
Image
Introduction:           It is an Algorithm of sorting taking O(nlog(n)) time to sort. This can be better understand by recursion like in merge sort. In this algorithm we take pivot and put it at its correct position after sorting its left and right side. A partition function return position of pivot in an array after placing all the smaller element left and all the larger right. Apply Quick sort to both side of pivot position.
Post a Comment
Read more

Heapify

-
Image
 After insertion we perform correction from last to first element and after deletion we perform correction from first to last element. Heapify is method to convert any array to correct head. We can apply heapify anytime in the array. This is the best way to correct the heap.
Post a Comment
Read more

Heap Sort

-
Image
It is similar to insertion and deletion. Insert the whole in a (Min or Max) heap. Delete the whole array by moving elements at last one by one. Example: Sort the given array                    arr[] = {9,4,8,2,5,6,7}     Apply Deletion:     Apply Deletion:     Apply Deletion:     Apply Deletion          Apply Deletion     Apply Deletion     Apply Deletion Sorted Array using Heap Sort After deletion Max Heap convert to Ascending order array After deletion Min Heap convert to Descending order array Time complexity of Inserting and Deleting an Element: O(log(n)+log(n)) Time complexity for performing above operation on n Element: O(n*2*log(n)) Therefore time complexity for Heap sort will be: O(nlog(n))
Post a Comment
Read more

Heap

-
Image
               Heap must be a complete(almost) binary tree. Types of Heap:      Max Heap -> For every node parent > child      Min Heap -> For every node parent < child Height ->                      log(n) Always
Post a Comment
Read more

2-3-4 Tree

-
Image
 Generally all the process is same as 2-3 Tree. So here we discuss the differences of 2-3-4 Tree from 2-3 Tree. Every Node must have at least ceil(n/2 here 4/2) children and maximum 4 children that's why is is called 2-3-4 tree b/c it will have 2 or 3 or 4 child of a node. Also called B-Tree of degree 4 Every node must be at same level Representation: Splitting:          When we insert element while node is full we will have even(4) number of elements so we can't divide element uniformly for splitting. So either we put more element to right, i.e. right biased or to left i.e. left biased.      Let we insert 40 in non-empty node: 
Post a Comment
Read more

Insertion/Deletion in Red-Black Tree

-
Image
 According the property of Red-Black tree, no two Red node come together (as Parent-Child relation). So if it happens then we have to reordering the tree either by recoloring or by rotation. Note: Here NULL will considered as Black node If the uncle of the conflicting child is red:          Apply Recoloring:                    If G is root node then change it to black, also check if parent of G is red, if yes apply reordering recursively If the uncle of the conflicting child is Black:          Apply Rotation:                 Zig-Zig Rotation: This is similar to LL/RR rotation:                    Zig-Zag Rotation: This is similar to LR/RL rotation: Let us create a tree by using the following nodes:               10, 20, 30, 50, 40, 60, 70, 80, 4, 8     Insert 10:          As every insertion will be red so 10 will be red but it is the root node so it will become black      Insert 20:         20 > 10 so it will be on right side of 10 and there is no conflict b/w Red so no reordering  
Post a Comment
Read more