Category: data Structures Algorithms

Max-Min Problem Table of content Max-Min Problem Naive Method Divide and Conquer Approach ”; Previous Next Let us consider a simple problem that can be solved by divide and conquer technique. Max-Min Problem The Max-Min Problem in algorithm analysis is finding the maximum and minimum value in an array. Solution To find the maximum and minimum numbers in a given array numbers[] of size n, the following algorithm can be used. First we are representing the naive method and then we will present divide and conquer approach. Naive Method Naive method is a basic method to solve any problem. In this method, the maximum and minimum number can be found separately. To find the maximum and minimum numbers, the following straightforward algorithm can be used. Algorithm: Max-Min-Element (numbers[]) max := numbers[1] min := numbers[1] for i = 2 to n do if numbers[i] > max then max := numbers[i] if numbers[i] < min then min := numbers[i] return (max, min) Example Following are the implementations of the above approach in various programming languages − C C++ Java Python #include <stdio.h> struct Pair { int max; int min; }; // Function to find maximum and minimum using the naive algorithm struct Pair maxMinNaive(int arr[], int n) { struct Pair result; result.max = arr[0]; result.min = arr[0]; // Loop through the array to find the maximum and minimum values for (int i = 1; i < n; i++) { if (arr[i] > result.max) { result.max = arr[i]; // Update the maximum value if a larger element is found } if (arr[i] < result.min) { result.min = arr[i]; // Update the minimum value if a smaller element is found } } return result; // Return the pair of maximum and minimum values } int main() { int arr[] = {6, 4, 26, 14, 33, 64, 46}; int n = sizeof(arr) / sizeof(arr[0]); struct Pair result = maxMinNaive(arr, n); printf(“Maximum element is: %dn”, result.max); printf(“Minimum element is: %dn”, result.min); return 0; } Output Maximum element is: 64 Minimum element is: 4 #include <iostream> using namespace std; struct Pair { int max; int min; }; // Function to find maximum and minimum using the naive algorithm Pair maxMinNaive(int arr[], int n) { Pair result; result.max = arr[0]; result.min = arr[0]; // Loop through the array to find the maximum and minimum values for (int i = 1; i < n; i++) { if (arr[i] > result.max) { result.max = arr[i]; // Update the maximum value if a larger element is found } if (arr[i] < result.min) { result.min = arr[i]; // Update the minimum value if a smaller element is found } } return result; // Return the pair of maximum and minimum values } int main() { int arr[] = {6, 4, 26, 14, 33, 64, 46}; int n = sizeof(arr) / sizeof(arr[0]); Pair result = maxMinNaive(arr, n); cout << “Maximum element is: ” << result.max << endl; cout << “Minimum element is: ” << result.min << endl; return 0; } Output Maximum element is: 64 Minimum element is: 4 public class MaxMinNaive { static class Pair { int max; int min; } // Function to find maximum and minimum using the naive algorithm static Pair maxMinNaive(int[] arr) { Pair result = new Pair(); result.max = arr[0]; result.min = arr[0]; // Loop through the array to find the maximum and minimum values for (int i = 1; i < arr.length; i++) { if (arr[i] > result.max) { result.max = arr[i]; // Update the maximum value if a larger element is found } if (arr[i] < result.min) { result.min = arr[i]; // Update the minimum value if a smaller element is found } } return result; // Return the pair of maximum and minimum values } public static void main(String[] args) { int[] arr = {6, 4, 26, 14, 33, 64, 46}; Pair result = maxMinNaive(arr); System.out.println(“Maximum element is: ” + result.max); System.out.println(“Minimum element is: ” + result.min); } } Output Maximum element is: 64 Minimum element is: 4 def max_min_naive(arr): max_val = arr[0] min_val = arr[0] # Loop through the array to find the maximum and minimum values for i in range(1, len(arr)): if arr[i] > max_val: max_val = arr[i] # Update the maximum value if a larger element is found if arr[i] < min_val: min_val = arr[i] # Update the minimum value if a smaller element is found return max_val, min_val # Return the pair of maximum and minimum values arr = [6, 4, 26, 14, 33, 64, 46] max_val, min_val = max_min_naive(arr) print(“Maximum element is:”, max_val) print(“Minimum element is:”, min_val) Output Maximum element is: 64 Minimum element is: 4 Analysis The number of comparison in Naive method is 2n – 2. The number of comparisons can be reduced using the divide and conquer approach. Following is the technique. Divide and Conquer Approach In this approach, the array is divided into two halves. Then using recursive approach maximum and minimum numbers in each halves are found. Later, return the maximum of two maxima of each half and the minimum of two minima of each half. In this given problem, the number of elements in an array is $y – x + 1$, where y is greater than or equal to x. $mathbf{mathit{Max – Min(x, y)}}$ will return the maximum and minimum values of an array $mathbf{mathit{numbers[x…y]}}$. Algorithm: Max – Min(x, y) if y – x ≤ 1 then return (max(numbers[x],numbers[y]),min((numbers[x],numbers[y])) else (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) return (max(max1, max2), min(min1, min2)) Example Following are implementations of the above approach in various programming languages − C C++ Java Python #include <stdio.h> // Structure to store both maximum and minimum elements struct Pair { int max; int min; }; struct Pair maxMinDivideConquer(int arr[], int low, int high) { struct Pair result; struct Pair left; struct Pair right; int mid; // If only one element in the array if (low == high) { result.max = arr[low]; result.min = arr[low]; return result; } // If

Doubly Linked List Data Structure ”; Previous Next What is Doubly Linked List? Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, forward as well as backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list. Link − Each link of a linked list can store a data called an element. Next − Each link of a linked list contains a link to the next link called Next. Prev − Each link of a linked list contains a link to the previous link called Prev. Linked List − A Linked List contains the connection link to the first link called First and to the last link called Last. Doubly Linked List Representation As per the above illustration, following are the important points to be considered. Doubly Linked List contains a link element called first and last. Each link carries a data field(s) and a link field called next. Each link is linked with its next link using its next link. Each link is linked with its previous link using its previous link. The last link carries a link as null to mark the end of the list. Basic Operations in Doubly Linked List Following are the basic operations supported by a list. Insertion − Adds an element at the beginning of the list. Insert Last − Adds an element at the end of the list. Insert After − Adds an element after an item of the list. Deletion − Deletes an element at the beginning of the list. Delete Last − Deletes an element from the end of the list. Delete − Deletes an element from the list using the key. Display forward − Displays the complete list in a forward manner. Display backward − Displays the complete list in a backward manner. Doubly Linked List – Insertion at the Beginning In this operation, we create a new node with three compartments, one containing the data, the others containing the address of its previous and next nodes in the list. This new node is inserted at the beginning of the list. Algorithm 1. START 2. Create a new node with three variables: prev, data, next. 3. Store the new data in the data variable 4. If the list is empty, make the new node as head. 5. Otherwise, link the address of the existing first node to the next variable of the new node, and assign null to the prev variable. 6. Point the head to the new node. 7. END Example Following are the implementations of this operation in various programming languages − C C++ Java Python #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> struct node { int data; int key; struct node *next; struct node *prev; }; //this link always point to first Link struct node *head = NULL; //this link always point to last Link struct node *last = NULL; struct node *current = NULL; //is list empty bool isEmpty(){ return head == NULL; } //display the doubly linked list void printList(){ struct node *ptr = head; while(ptr != NULL) { printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } } //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()) { //make it the last link last = link; } else { //update first prev link head->prev = link; } //point it to old first link link->next = head; //point first to new first link head = link; } void main(){ insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(“nDoubly Linked List: “); printList(); } Output Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) #include <iostream> #include <cstring> #include <cstdlib> #include <cstdbool> struct node { int data; int key; struct node *next; struct node *prev; }; //this link always point to first Link struct node *head = NULL; //this link always point to last Link struct node *last = NULL; struct node *current = NULL; //is list empty bool isEmpty(){ return head == NULL; } //display the doubly linked list void printList(){ struct node *ptr = head; while(ptr != NULL) { printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } } //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()) { //make it the last link last = link; } else { //update first prev link head->prev = link; } //point it to old first link link->next = head; //point first to new first link head = link; } int main(){ insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(“Doubly Linked List: “); printList(); return 0; } Output Doubly Linked List: (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) //Java code for doubly linked list import java.util.*; class Node { public int data; public int key; public Node next; public Node prev; public Node(int data, int key) { this.data = data; this.key = key; this.next = null; this.prev = null; } } public class Main { //this link always point to first Link static Node head = null; //this link always point to last Link static Node last = null; static Node current = null; // is list empty public static boolean is_empty() { return head == null; } //display the doubly linked list public static void print_list() { Node ptr = head; while (ptr != null) { System.out.println(“(” + ptr.key

Shell Sort Algorithm Table of content Shell Sort Algorithm Implementation ”; Previous Next Shell sort is a highly efficient sorting algorithm and is based on insertion sort algorithm. This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left. This algorithm uses insertion sort on a widely spread elements, first to sort them and then sorts the less widely spaced elements. This spacing is termed as interval. This interval is calculated based on Knuth”s formula as − h = h * 3 + 1 where − h is interval with initial value 1 This algorithm is quite efficient for medium-sized data sets as its average and worst case complexity are of O(n), where n is the number of items. Shell Sort Algorithm Following is the algorithm for shell sort. 1. Initialize the value of h. 2. Divide the list into smaller sub-list of equal interval h. 3. Sort these sub-lists using insertion sort. 4. Repeat until complete list is sorted. Pseudocode Following is the pseudocode for shell sort. procedure shellSort() A : array of items /* calculate interval*/ while interval < A.length /3 do: interval = interval * 3 + 1 end while while interval > 0 do: for outer = interval; outer < A.length; outer ++ do: /* select value to be inserted */ valueToInsert = A[outer] inner = outer; /*shift element towards right*/ while inner > interval -1 && A[inner – interval] >= valueToInsert do: A[inner] = A[inner – interval] inner = inner – interval end while /* insert the number at hole position */ A[inner] = valueToInsert end for /* calculate interval*/ interval = (interval -1) /3; end while end procedure Example Let us consider the following example to have an idea of how shell sort works. We take the same array we have used in our previous examples. For our example and ease of understanding, we take the interval of 4. Make a virtual sub-list of all values located at the interval of 4 positions. Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 14} We compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this − Then, we take interval of 2 and this gap generates two sub-lists – {14, 27, 35, 42}, {19, 10, 33, 44} We compare and swap the values, if required, in the original array. After this step, the array should look like this − Finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion sort to sort the array. Following is the step-by-step depiction − We see that it required only four swaps to sort the rest of the array. Implementation Shell sort is a highly efficient sorting algorithm and is based on insertion sort algorithm. This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left. C C++ Java Python #include <stdio.h> void shellSort(int arr[], int n){ int gap, j, k; for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2 for(j = gap; j<n; j++) { for(k = j-gap; k>=0; k -= gap) { if(arr[k+gap] >= arr[k]) break; else { int temp; temp = arr[k+gap]; arr[k+gap] = arr[k]; arr[k] = temp; } } } } } int main(){ int n; n = 5; int arr[5] = {33, 45, 62, 12, 98}; // initialize the array printf(“Array before Sorting: “); for(int i = 0; i<n; i++) printf(“%d “,arr[i]); printf(“n”); shellSort(arr, n); printf(“Array after Sorting: “); for(int i = 0; i<n; i++) printf(“%d “, arr[i]); printf(“n”); } Output Array before Sorting: 33 45 62 12 98 Array after Sorting: 12 33 45 62 98 #include<iostream> using namespace std; void shellSort(int *arr, int n){ int gap, j, k; for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2 for(j = gap; j<n; j++) { for(k = j-gap; k>=0; k -= gap) { if(arr[k+gap] >= arr[k]) break; else { int temp; temp = arr[k+gap]; arr[k+gap] = arr[k]; arr[k] = temp; } } } } } int main(){ int n; n = 5; int arr[5] = {33, 45, 62, 12, 98}; // initialize the array cout << “Array before Sorting: “; for(int i = 0; i<n; i++) cout << arr[i] << ” “; cout << endl; shellSort(arr, n); cout << “Array after Sorting: “; for(int i = 0; i<n; i++) cout << arr[i] << ” “; cout << endl; } Output Array before Sorting: 33 45 62 12 98 Array after Sorting: 12 33 45 62 98 import java.io.*; import java.util.*; public class ShellSort { public static void main(String args[]) { int n = 5; int[] arr = {33, 45, 62, 12, 98}; //initialize an array System.out.print(“Array before Sorting: “); for(int i = 0; i<n; i++) System.out.print(arr[i] + ” “); System.out.println(); int gap; for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2 for(int j = gap; j<n; j++) { for(int k = j-gap; k>=0; k -= gap) { if(arr[k+gap] >= arr[k]) break; else { int temp; temp = arr[k+gap]; arr[k+gap] = arr[k]; arr[k] = temp; } } } } System.out.print(“Array After Sorting: “); for(int i = 0; i<n; i++)

Quick Sort Algorithm Table of content Partition in Quick Sort Quick Sort Pivot Algorithm Quick Sort Algorithm Quick Sort Pseudocode Analysis Implementation ”; Previous Next Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O(n2), respectively. Partition in Quick Sort Following animated representation explains how to find the pivot value in an array. The pivot value divides the list into two parts. And recursively, we find the pivot for each sub-lists until all lists contains only one element. Quick Sort Pivot Algorithm Based on our understanding of partitioning in quick sort, we will now try to write an algorithm for it, which is as follows. 1. Choose the highest index value has pivot 2. Take two variables to point left and right of the list excluding pivot 3. Left points to the low index 4. Right points to the high 5. While value at left is less than pivot move right 6. While value at right is greater than pivot move left 7. If both step 5 and step 6 does not match swap left and right 8. If left ≥ right, the point where they met is new pivot Quick Sort Pivot Pseudocode The pseudocode for the above algorithm can be derived as − function partitionFunc(left, right, pivot) leftPointer = left rightPointer = right – 1 while True do while A[++leftPointer] < pivot do //do-nothing end while while rightPointer > 0 && A[–rightPointer] > pivot do //do-nothing end while if leftPointer >= rightPointer break else swap leftPointer,rightPointer end if end while swap leftPointer,right return leftPointer end function Quick Sort Algorithm Using pivot algorithm recursively, we end up with smaller possible partitions. Each partition is then processed for quick sort. We define recursive algorithm for quicksort as follows − 1. Make the right-most index value pivot 2. Partition the array using pivot value 3. Quicksort left partition recursively 4. Quicksort right partition recursively Quick Sort Pseudocode To get more into it, let see the pseudocode for quick sort algorithm − procedure quickSort(left, right) if right-left <= 0 return else pivot = A[right] partition = partitionFunc(left, right, pivot) quickSort(left,partition-1) quickSort(partition+1,right) end if end procedure Analysis The worst case complexity of Quick-Sort algorithm is O(n2). However, using this technique, in average cases generally we get the output in O (n log n) time. Implementation Following are the implementations of Quick Sort algorithm in various programming languages − C C++ Java Python #include <stdio.h> #include <stdbool.h> #define MAX 7 int intArray[MAX] = { 4,6,3,2,1,9,7 }; void printline(int count) { int i; for (i = 0; i < count – 1; i++) { printf(“=”); } printf(“=n”); } void display() { int i; printf(“[“); // navigate through all items for (i = 0; i < MAX; i++) { printf(“%d “, intArray[i]); } printf(“]n”); } void swap(int num1, int num2) { int temp = intArray[num1]; intArray[num1] = intArray[num2]; intArray[num2] = temp; } int partition(int left, int right, int pivot) { int leftPointer = left – 1; int rightPointer = right; while (true) { while (intArray[++leftPointer] < pivot) { //do nothing } while (rightPointer > 0 && intArray[–rightPointer] > pivot) { //do nothing } if (leftPointer >= rightPointer) { break; } else { printf(” item swapped :%d,%dn”, intArray[leftPointer], intArray[rightPointer]); swap(leftPointer, rightPointer); } } printf(” pivot swapped :%d,%dn”, intArray[leftPointer], intArray[right]); swap(leftPointer, right); printf(“Updated Array: “); display(); return leftPointer; } void quickSort(int left, int right) { if (right – left <= 0) { return; } else { int pivot = intArray[right]; int partitionPoint = partition(left, right, pivot); quickSort(left, partitionPoint – 1); quickSort(partitionPoint + 1, right); } } int main() { printf(“Input Array: “); display(); printline(50); quickSort(0, MAX – 1); printf(“Output Array: “); display(); printline(50); } Output Input Array: [4 6 3 2 1 9 7 ] ================================================== pivot swapped :9,7 Updated Array: [4 6 3 2 1 7 9 ] pivot swapped :4,1 Updated Array: [1 6 3 2 4 7 9 ] item swapped :6,2 pivot swapped :6,4 Updated Array: [1 2 3 4 6 7 9 ] pivot swapped :3,3 Updated Array: [1 2 3 4 6 7 9 ] Output Array: [1 2 3 4 6 7 9 ] ================================================== #include <iostream> using namespace std; #define MAX 7 int intArray[MAX] = {4,6,3,2,1,9,7}; void display() { int i; cout << “[“; // navigate through all items for(i = 0;i < MAX;i++) { cout << intArray[i] << ” “; } cout << “]n”; } void swap(int num1, int num2) { int temp = intArray[num1]; intArray[num1] = intArray[num2]; intArray[num2] = temp; } int partition(int left, int right, int pivot) { int leftPointer = left -1; int rightPointer = right; while(true) { while(intArray[++leftPointer] < pivot) { //do nothing } while(rightPointer > 0 && intArray[–rightPointer] > pivot) { //do nothing } if(leftPointer >= rightPointer) { break; } else { cout << “item swapped : ” << intArray[leftPointer] << “,” << intArray[rightPointer] << endl; swap(leftPointer, rightPointer); } } cout << “npivot swapped : ” << intArray[leftPointer] << “,” << intArray[right] << endl; swap(leftPointer,right); cout << “Updated Array: “; display(); return leftPointer; }

Red Black Trees Table of content Basic Operations of Red-Black Trees Insertion operation Deletion operation Search operation Complete implementation ”; Previous Next Red-Black Trees are another type of the Balanced Binary Search Trees with two coloured nodes: Red and Black. It is a self-balancing binary search tree that makes use of these colours to maintain the balance factor during the insertion and deletion operations. Hence, during the Red-Black Tree operations, the memory uses 1 bit of storage to accommodate the colour information of each node In Red-Black trees, also known as RB trees, there are different conditions to follow while assigning the colours to the nodes. The root node is always black in colour. No two adjacent nodes must be red in colour. Every path in the tree (from the root node to the leaf node) must have the same amount of black coloured nodes. Even though AVL trees are more balanced than RB trees, with the balancing algorithm in AVL trees being stricter than that of RB trees, multiple and faster insertion and deletion operations are made more efficient through RB trees. Fig: RB trees Basic Operations of Red-Black Trees The operations on Red-Black Trees include all the basic operations usually performed on a Binary Search Tree. Some of the basic operations of an RB Tree include − Insertion Deletion Search Insertion operation Insertion operation of a Red-Black tree follows the same insertion algorithm of a binary search tree. The elements are inserted following the binary search property and as an addition, the nodes are color coded as red and black to balance the tree according to the red-black tree properties. Follow the procedure given below to insert an element into a red-black tree by maintaining both binary search tree and red black tree properties. Case 1 − Check whether the tree is empty; make the current node as the root and color the node black if it is empty. Case 2 − But if the tree is not empty, we create a new node and color it red. Here we face two different cases − If the parent of the new node is a black colored node, we exit the operation and tree is left as it is. If the parent of this new node is red and the color of the parent”s sibling is either black or if it does not exist, we apply a suitable rotation and recolor accordingly. If the parent of this new node is red and color of the parent”s sibling is red, recolor the parent, the sibling and grandparent nodes to black. The grandparent is recolored only if it is not the root node; if it is the root node recolor only the parent and the sibling. Example Let us construct an RB Tree for the first 7 integer numbers to understand the insertion operation in detail − The tree is checked to be empty so the first node added is a root and is colored black. Now, the tree is not empty so we create a new node and add the next integer with color red, The nodes do not violate the binary search tree and RB tree properties, hence we move ahead to add another node. The tree is not empty; we create a new red node with the next integer to it. But the parent of the new node is not a black colored node, The tree right now violates both the binary search tree and RB tree properties; since parent”s sibling is NULL, we apply a suitable rotation and recolor the nodes. Now that the RB Tree property is restored, we add another node to the tree − The tree once again violates the RB Tree balance property, so we check for the parent”s sibling node color, red in this case, so we just recolor the parent and the sibling. We next insert the element 5, which makes the tree violate the RB Tree balance property once again. And since the sibling is NULL, we apply suitable rotation and recolor. Now, we insert element 6, but the RB Tree property is violated and one of the insertion cases need to be applied − The parent”s sibling is red, so we recolor the parent, parent”s sibling and the grandparent nodes since the grandparent is not the root node. Now, we add the last element, 7, but the parent node of this new node is red. Since the parent”s sibling is NULL, we apply suitable rotations (RR rotation) The final RB Tree is achieved. Deletion operation The deletion operation on red black tree must be performed in such a way that it must restore all the properties of a binary search tree and a red black tree. Follow the steps below to perform the deletion operation on the red black tree − Firstly, we perform deletion based on the binary search tree properties. Case 1 − If either the node to be deleted or the node”s parent is red, just delete it. Case 2 − If the node is a double black, just remove the double black (double black occurs when the node to be deleted is a black colored leaf node, as it adds up the NULL nodes which are considered black colored nodes too) Case 3 − If the double black”s sibling node is also a black node and its child nodes are also black in color, follow the steps below − Remove double black Recolor its parent to black (if the parent is a

Travelling Salesman Problem (Dynamic Approach) Table of content Travelling Salesman Dynamic Programming Algorithm Implementation ”; Previous Next Travelling salesman problem is the most notorious computational problem. We can use brute-force approach to evaluate every possible tour and select the best one. For n number of vertices in a graph, there are (n−1)! number of possibilities. Thus, maintaining a higher complexity. However, instead of using brute-force, using the dynamic programming approach will obtain the solution in lesser time, though there is no polynomial time algorithm. Travelling Salesman Dynamic Programming Algorithm Let us consider a graph G = (V,E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-negative. Suppose we have started at city 1 and after visiting some cities now we are in city j. Hence, this is a partial tour. We certainly need to know j, since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don”t repeat any of them. Hence, this is an appropriate sub-problem. For a subset of cities S $epsilon$ {1,2,3,…,n} that includes 1, and j $epsilon$ S, let C(S, j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j. When |S|> 1 , we define 𝑪C(S,1)= $propto$ since the path cannot start and end at 1. Now, let express C(S, j) in terms of smaller sub-problems. We need to start at 1 and end at j. We should select the next city in such a way that $$Cleft ( S,j right ), =, min, Cleft ( S, -, left{j right},i right ), +, dleft ( i,j right ): where: i: epsilon : S: and: ineq j$$ Algorithm: Traveling-Salesman-Problem C ({1}, 1) = 0 for s = 2 to n do for all subsets S є {1, 2, 3, … , n} of size s and containing 1 C (S, 1) = ∞ for all j є S and j ≠ 1 C (S, j) = min {C (S – {j}, i) + d(i, j) for i є S and i ≠ j} Return minj C ({1, 2, 3, …, n}, j) + d(j, i) Analysis There are at the most 2n.n sub-problems and each one takes linear time to solve. Therefore, the total running time is O(2n.n2). Example In the following example, we will illustrate the steps to solve the travelling salesman problem. From the above graph, the following table is prepared. 1 2 3 4 1 0 10 15 20 2 5 0 9 10 3 6 13 0 12 4 8 8 9 0 S = $Phi$ $$Costleft ( 2,Phi ,1 right ), =, dleft ( 2,1 right ),=,5$$ $$Costleft ( 3,Phi ,1 right ), =, dleft ( 3,1 right ), =, 6$$ $$Costleft ( 4,Phi ,1 right ), =, dleft ( 4,1 right ), =, 8$$ S = 1 $$Cost(i,s)=minleft{Cosleft ( j,s-(j) right ), +,dleft [ i,j right ] right}$$ $$Cost(2,left{3 right},1)=d[2,3], +, Costleft ( 3,Phi ,1 right ), =, 9, +, 6, =, 15$$ $$Cost(2,left{4 right},1)=d[2,4], +, Costleft ( 4,Phi ,1 right ), =, 10, +, 8, =, 18$$ $$Cost(3,left{2 right},1)=d[3,2], +, Costleft ( 2,Phi ,1 right ), =, 13, +, 5, =, 18$$ $$Cost(3,left{4 right},1)=d[3,4], +, Costleft ( 4,Phi ,1 right ), =, 12, +, 8, =, 20$$ $$Cost(4,left{3 right},1)=d[4,3], +, Costleft ( 3,Phi ,1 right ), =, 9, +, 6, =, 15$$ $$Cost(4,left{2 right},1)=d[4,2], +, Costleft ( 2,Phi ,1 right ), =, 8, +, 5, =, 13$$ S = 2 $$Cost(2,left{3,4 right},1)=minleft{begin{matrix} dleft [ 2,3 right ],+ ,Costleft ( 3,left{ 4right},1 right ), =, 9, +, 20, =, 29 \ dleft [ 2,4 right ],+ ,Costleft ( 4,left{ 3right},1 right ), =, 10, +, 15, =, 25 \ end{matrix}right., =,25$$ $$Cost(3,left{2,4 right},1)=minleft{begin{matrix} dleft [ 3,2 right ],+ ,Costleft ( 2,left{ 4right},1 right ), =, 13, +, 18, =, 31 \ dleft [ 3,4 right ],+ ,Costleft ( 4,left{ 2right},1 right ), =, 12, +, 13, =, 25 \ end{matrix}right., =,25$$ $$Cost(4,left{2,3 right},1)=minleft{begin{matrix} dleft [ 4,2 right ],+ ,Costleft ( 2,left{ 3right},1 right ), =, 8, +, 15, =, 23 \ dleft [ 4,3 right ],+ ,Costleft ( 3,left{ 2right},1 right ), =, 9, +, 18, =, 27 \ end{matrix}right., =,23$$ S = 3 $$Cost(1,left{2,3,4 right},1)=minleft{begin{matrix} dleft [ 1,2 right ],+ ,Costleft ( 2,left{ 3,4right},1 right ), =, 10, +, 25, =, 35 \ dleft [ 1,3 right ],+ ,Costleft ( 3,left{ 2,4right},1 right ), =, 15, +, 25, =, 40 \ dleft [ 1,4 right ],+ ,Costleft ( 4,left{ 2,3right},1 right ), =, 20, +, 23, =, 43 \ end{matrix}right., =, 35$$ The minimum cost path is 35. Start from cost {1, {2, 3, 4}, 1}, we get the minimum value for d [1, 2]. When s = 3, select the path from 1 to 2 (cost is 10) then go backwards. When s = 2, we get the minimum value for d [4, 2]. Select the path from 2 to 4 (cost is 10) then go backwards. When s = 1, we get the minimum value for d [4, 2] but 2 and 4 is already selected. Therefore, we select d [4, 3] (two possible values are 15 for d [2, 3] and d [4, 3], but

Data Structure – Useful Resources ”; Previous Next The following resources contain additional information on Data Structure. Please use them to get more in-depth knowledge on this. Useful Video Courses Data Structure Online Training Course 142 Lectures 13 hours Tutorialspoint More Detail Advanced Data Structures Course 47 Lectures 7.5 hours William Fiset More Detail Data Structures in JavaScript: Fundamentals Course Best Seller 89 Lectures 14 hours Eduonix Learning Solutions More Detail Data Structures and Algorithms Using Python Most Popular 180 Lectures 17 hours Chandramouli Jayendran More Detail Prerequisite Course for Data Structure 18 Lectures 3.5 hours EnggTutes More Detail Mastering Data Structures & Algorithms using C++ 100 Lectures 22 hours EnggTutes More Detail Print Page Previous Next Advertisements ”;

Fibonacci Search Algorithm Table of content Fibonacci Search Algorithm Implementation ”; Previous Next As the name suggests, the Fibonacci Search Algorithm uses Fibonacci numbers to search for an element in a sorted input array. But first, let us revise our knowledge on Fibonacci numbers − Fibonacci Series is a series of numbers that have two primitive numbers 0 and 1. The successive numbers are the sum of preceding two numbers in the series. This is an infinite constant series, therefore, the numbers in it are fixed. The first few numbers in this Fibonacci series include − 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89… The main idea behind the Fibonacci series is also to eliminate the least possible places where the element could be found. In a way, it acts like a divide & conquer algorithm (logic being the closest to binary search algorithm). This algorithm, like jump search and exponential search, also skips through the indices of the input array in order to perform searching. Fibonacci Search Algorithm The Fibonacci Search Algorithm makes use of the Fibonacci Series to diminish the range of an array on which the searching is set to be performed. With every iteration, the search range decreases making it easier to locate the element in the array. The detailed procedure of the searching is seen below − Step 1 − As the first step, find the immediate Fibonacci number that is greater than or equal to the size of the input array. Then, also hold the two preceding numbers of the selected Fibonacci number, that is, we hold Fm, Fm-1, Fm-2 numbers from the Fibonacci Series. Step 2 − Initialize the offset value as -1, as we are considering the entire array as the searching range in the beginning. Step 3 − Until Fm-2 is greater than 0, we perform the following steps − Compare the key element to be found with the element at index [min(offset+Fm-2,n-1)]. If a match is found, return the index. If the key element is found to be lesser value than this element, we reduce the range of the input from 0 to the index of this element. The Fibonacci numbers are also updated with Fm = Fm-2. But if the key element is greater than the element at this index, we remove the elements before this element from the search range. The Fibonacci numbers are updated as Fm = Fm-1. The offset value is set to the index of this element. Step 4 − As there are two 1s in the Fibonacci series, there arises a case where your two preceding numbers will become 1. So if Fm-1 becomes 1, there is only one element left in the array to be searched. We compare the key element with that element and return the 1st index. Otherwise, the algorithm returns an unsuccessful search. Pseudocode Begin Fibonacci Search n <- size of the input array offset = -1 Fm2 := 0 Fm1 := 1 Fm := Fm2 + Fm1 while Fm < n do: Fm2 = Fm1 Fm1 = Fm Fm = Fm2 + Fm1 done while fm > 1 do: i := minimum of (offset + fm2, n – 1) if (A[i] < x) then: Fm := Fm1 Fm1 := Fm2 Fm2 := Fm – Fm1 offset = i end else if (A[i] > x) then: Fm = Fm2 Fm1 = Fm1 – Fm2 Fm2 = Fm – Fm1 end else return i; end done if (Fm1 and Array[offset + 1] == x) then: return offset + 1 end return invalid location; end Analysis The Fibonacci Search algorithm takes logarithmic time complexity to search for an element. Since it is based on a divide on a conquer approach and is similar to idea of binary search, the time taken by this algorithm to be executed under the worst case consequences is O(log n). Example Suppose we have a sorted array of elements {12, 14, 16, 17, 20, 24, 31, 43, 50, 62} and need to identify the location of element 24 in it using Fibonacci Search. Step 1 The size of the input array is 10. The smallest Fibonacci number greater than 10 is 13. Therefore, Fm = 13, Fm-1 = 8, Fm-2 = 5. We initialize offset = -1 Step 2 In the first iteration, compare it with the element at index = minimum (offset + Fm-2, n – 1) = minimum (-1 + 5, 9) = minimum (4, 9) = 4. The fourth element in the array is 20, which is not a match and is less than the key element. Step 3 In the second iteration, update the offset value and the Fibonacci numbers. Since the key is greater, the offset value will become the index of the element, i.e. 4. Fibonacci numbers are updated as Fm = Fm-1 = 8. Fm-1 = 5, Fm-2 = 3. Now, compare it with the element at index = minimum (offset + Fm-2, n – 1) = minimum (4 + 3, 9) = minimum (7, 9) = 7. Element at the 7th index of the array is 43, which is not a match and is also lesser than the key. Step 4 We discard the elements after the 7th index, so n = 7 and offset value remains 4. Fibonacci numbers are pushed two steps backward, i.e. Fm = Fm-2 = 3. Fm-1 = 2, Fm-2 = 1. Now, compare it with the element at index = minimum (offset + Fm-2, n – 1) = minimum (4 + 1, 6) = minimum (5, 7) = 5. The element at index 5 in the

B+ Trees Table of content Basic Operations of B+ Trees Insertion operation ”; Previous Next The B+ trees are extensions of B trees designed to make the insertion, deletion and searching operations more efficient. The properties of B+ trees are similar to the properties of B trees, except that the B trees can store keys and records in all internal nodes and leaf nodes while B+ trees store records in leaf nodes and keys in internal nodes. One profound property of the B+ tree is that all the leaf nodes are connected to each other in a single linked list format and a data pointer is available to point to the data present in disk file. This helps fetch the records in equal numbers of disk access. Since the size of main memory is limited, B+ trees act as the data storage for the records that couldn’t be stored in the main memory. For this, the internal nodes are stored in the main memory and the leaf nodes are stored in the secondary memory storage. Properties of B+ trees Every node in a B+ Tree, except root, will hold a maximum of m children and (m-1) keys, and a minimum of $mathrm{left lceil frac{m}{2}right rceil}$ children and $mathrm{left lceil frac{m-1}{2}right rceil}$ keys, since the order of the tree is m. The root node must have no less than two children and at least one search key. All the paths in a B tree must end at the same level, i.e. the leaf nodes must be at the same level. A B+ tree always maintains sorted data. Basic Operations of B+ Trees The operations supported in B+ trees are Insertion, deletion and searching with the time complexity of O(log n) for every operation. They are almost similar to the B tree operations as the base idea to store data in both data structures is same. However, the difference occurs as the data is stored only in the leaf nodes of a B+ trees, unlike B trees. Insertion operation The insertion to a B+ tree starts at a leaf node. Step 1 − Calculate the maximum and minimum number of keys to be added onto the B+ tree node. Step 2 − Insert the elements one by one accordingly into a leaf node until it exceeds the maximum key number. Step 3 − The node is split into half where the left child consists of minimum number of keys and the remaining keys are stored in the right child. Step 4 − But if the internal node also exceeds the maximum key property, the node is split in half where the left child consists of the minimum keys and remaining keys are stored in the right child. However, the smallest number in the right child is made the parent. Step 5 − If both the leaf node and internal node have the maximum keys, both of them are split in the similar manner and the smallest key in the right child is added to the parent node. Example Following are the implementations of this operation in various programming languages − C C++ Java Python // C program for Bplus tree #include <stdio.h> #include <stdlib.h> struct BplusTree { int *d; struct BplusTree **child_ptr; int l; int n; }; struct BplusTree *r = NULL, *np = NULL, *x = NULL; struct BplusTree* init() { //to create nodes int i; np = (struct BplusTree*)malloc(sizeof(struct BplusTree)); np->d = (int*)malloc(6 * sizeof(int)); // order 6 np->child_ptr = (struct BplusTree**)malloc(7 * sizeof(struct BplusTree*)); np->l = 1; np->n = 0; for (i = 0; i < 7; i++) { np->child_ptr[i] = NULL; } return np; } void traverse(struct BplusTree *p) { //traverse tree printf(“n”); int i; for (i = 0; i < p->n; i++) { if (p->l == 0) { traverse(p->child_ptr[i]); } printf(” %d”, p->d[i]); } if (p->l == 0) { traverse(p->child_ptr[i]); } printf(“n”); } void sort(int *p, int n) { int i, j, t; for (i = 0; i < n; i++) { for (j = i; j <= n; j++) { if (p[i] > p[j]) { t = p[i]; p[i] = p[j]; p[j] = t; } } } } int split_child(struct BplusTree *x, int i) { int j, mid; struct BplusTree *np1, *np3, *y; np3 = init(); np3->l = 1; if (i == -1) { mid = x->d[2]; x->d[2] = 0; x->n–; np1 = init(); np1->l = 0; x->l = 1; for (j = 3; j < 6; j++) { np3->d[j – 3] = x->d[j]; np3->child_ptr[j – 3] = x->child_ptr[j]; np3->n++; x->d[j] = 0; x->n–; } for (j = 0; j < 6; j++) { x->child_ptr[j] = NULL; } np1->d[0] = mid; np1->child_ptr[np1->n] = x; np1->child_ptr[np1->n + 1] = np3; np1->n++; r = np1; } else { y = x->child_ptr[i]; mid = y->d[2]; y->d[2] = 0; y->n–; for (j = 3; j < 6; j++) { np3->d[j – 3] = y->d[j]; np3->n++; y->d[j] = 0; y->n–; } x->child_ptr[i + 1] = y; x->child_ptr[i + 1] = np3; } return mid; } void insert(int a) { int i, t; x = r; if (x == NULL) { r = init(); x = r; } else { if (x->l == 1 && x->n == 6) { t = split_child(x, -1); x = r; for (i = 0; i < x->n; i++) { if (a > x->d[i] && a < x->d[i + 1]) { i++; break; } else if (a < x->d[0]) { break; } else { continue; } } x = x->child_ptr[i]; } else { while (x->l == 0) { for (i = 0; i < x->n; i++) { if (a > x->d[i] && a < x->d[i + 1]) { i++; break; } else if

Tower of Hanoi Using Recursion Table of content Tower of Hanoi Rules Algorithm Example ”; Previous Next Tower of Hanoi Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted − These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same. Rules The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are − Only one disk can be moved among the towers at any given time. Only the “top” disk can be removed. No large disk can sit over a small disk. Following is an animated representation of solving a Tower of Hanoi puzzle with three disks. Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 – 1 = 7 steps. Algorithm To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg. If we have 2 disks − First, we move the smaller (top) disk to aux peg. Then, we move the larger (bottom) disk to destination peg. And finally, we move the smaller disk from aux to destination peg. So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part. Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks. The steps to follow are − Step 1 − Move n-1 disks from source to aux Step 2 − Move nth disk from source to dest Step 3 − Move n-1 disks from aux to dest A recursive algorithm for Tower of Hanoi can be driven as follows − START Procedure Hanoi(disk, source, dest, aux) IF disk == 1, THEN move disk from source to dest ELSE Hanoi(disk – 1, source, aux, dest) // Step 1 move disk from source to dest // Step 2 Hanoi(disk – 1, aux, dest, source) // Step 3 END IF END Procedure STOP Example Following are the implementations of this approach in various programming languages − C C++ Java Python #include <stdio.h> void hanoi(int n, char from, char to, char via) { if(n == 1){ printf(“Move disk 1 from %c to %cn”, from, to); } else{ hanoi(n-1, from, via, to); printf(“Move disk %d from %c to %cn”, n, from, to); hanoi(n-1, via, to, from); } } int main() { int n = 3; char from = ”A”; char to = ”B”; char via = ”C”; //calling hanoi() method hanoi(n, from, via, to); } #include <iostream> using namespace std; void hanoi(int n, char from, char to, char via) { if(n == 1){ cout<<“Move disk 1 from “<<from<<” to “<<to<<endl; } else{ hanoi(n-1, from, via, to); cout<<“Move disk “<<n<<” from “<<from<<” to “<<to<<endl; hanoi(n-1, via, to, from); } } int main() { int n = 3; char from = ”A”; char to = ”B”; char via = ”C”; //calling hanoi() method hanoi(n, from , via, to); } import java.util.*; public class Demo { public static void hanoi(int n, String from, String to, String via) { if(n == 1){ System.out.println(“Move disk 1 from ” + from + ” to ” + to); } else{ hanoi(n-1, from, via, to); System.out.println(“Move disk ” + n + ” from ” + from + ” to ” + to); hanoi(n-1, via, to, from); } } public static void main(String[] args) { int n = 3; String from = “A”; String to = “B”; String via = “C”; //calling hanoi() metod hanoi(n, from, via, to); } } def hanoi(n, f, to, via): if n == 1: print(“Move disk 1 from”,f,”to”,to); else: hanoi(n-1, f, via, to) print(“Move disk”,n,”from”,f,”to”,to); hanoi(n-1, via, to, f) n = 3 f = ”A” to = ”B” via = ”C” hanoi(n, f, via, to) Output Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C Print Page Previous Next Advertisements ”;