Category: data Structures Algorithms

Randomized Algorithms Table of content Classification of Randomized Algorithms Need for Randomized Algorithms ”; Previous Next Randomized algorithm is a different design approach taken by the standard algorithms where few random bits are added to a part of their logic. They are different from deterministic algorithms; deterministic algorithms follow a definite procedure to get the same output every time an input is passed where randomized algorithms produce a different output every time they’re executed. It is important to note that it is not the input that is randomized, but the logic of the standard algorithm. Figure 1: Deterministic Algorithm Unlike deterministic algorithms, randomized algorithms consider randomized bits of the logic along with the input that in turn contribute towards obtaining the output. Figure 2: Randomized Algorithm However, the probability of randomized algorithms providing incorrect output cannot be ruled out either. Hence, the process called amplification is performed to reduce the likelihood of these erroneous outputs. Amplification is also an algorithm that is applied to execute some parts of the randomized algorithms multiple times to increase the probability of correctness. However, too much amplification can also exceed the time constraints making the algorithm ineffective. Classification of Randomized Algorithms Randomized algorithms are classified based on whether they have time constraints as the random variable or deterministic values. They are designed in their two common forms − Las Vegas and Monte Carlo. Las Vegas − The Las Vegas method of randomized algorithms never gives incorrect outputs, making the time constraint as the random variable. For example, in string matching algorithms, las vegas algorithms start from the beginning once they encounter an error. This increases the probability of correctness. Eg., Randomized Quick Sort Algorithm. Monte Carlo − The Monte Carlo method of randomized algorithms focuses on finishing the execution within the given time constraint. Therefore, the running time of this method is deterministic. For example, in string matching, if monte carlo encounters an error, it restarts the algorithm from the same point. Thus, saving time. Eg., Karger’s Minimum Cut Algorithm Need for Randomized Algorithms This approach is usually adopted to reduce the time complexity and space complexity. But there might be some ambiguity about how adding randomness will decrease the runtime and memory stored, instead of increasing; we will understand that using the game theory. The Game Theory and Randomized Algorithms The basic idea of game theory actually provides with few models that help understand how decision-makers in a game interact with each other. These game theoretical models use assumptions to figure out the decision-making structure of the players in a game. The popular assumptions made by these theoretical models are that the players are both rational and take into account what the opponent player would decide to do in a particular situation of a game. We will apply this theory on randomized algorithms. Zero-sum game The zero-sum game is a mathematical representation of the game theory. It has two players where the result is a gain for one player while it is an equivalent loss to the other player. So, the net improvement is the sum of both players’ status which sums up to zero. Randomized algorithms are based on the zero-sum game of designing an algorithm that gives lowest time complexity for all inputs. There are two players in the game; one designs the algorithm and the opponent provides with inputs for the algorithm. The player two needs to give the input in such a way that it will yield the worst time complexity for them to win the game. Whereas, the player one needs to design an algorithm that takes minimum time to execute any input given. For example, consider the quick sort algorithm where the main algorithm starts from selecting the pivot element. But, if the player in zero-sum game chooses the sorted list as an input, the standard algorithm provides the worst case time complexity. Therefore, randomizing the pivot selection would execute the algorithm faster than the worst time complexity. However, even if the algorithm chose the first element as pivot randomly and obtains the worst time complexity, executing it another time with the same input will solve the problem since it chooses another pivot this time. On the other hand, for algorithms like merge sort the time complexity does not depend on the input; even if the algorithm is randomized the time complexity will always remain the same. Hence, randomization is only applied on algorithms whose complexity depends on the input. Examples Few popular examples of the Randomized algorithms are − Randomized Quick Sort Algorithm Karger’s Minimum Cut Algorithm Fisher-Yates Shuffle Algorithm The Subset Sum Problem Print Page Previous Next Advertisements ”;

Heap Data Structure Table of content Max Heap Construction Algorithm Max Heap Deletion Algorithm ”; Previous Next Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then − key(α) ≥ key(β) As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types − For Input → 35 33 42 10 14 19 27 44 26 31 Min-Heap − Where the value of the root node is less than or equal to either of its children. Max-Heap − Where the value of the root node is greater than or equal to either of its children. Both trees are constructed using the same input and order of arrival. Max Heap Construction Algorithm We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is similar but we go for min values instead of max values. We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree. Step 1 − Create a new node at the end of heap. Step 2 − Assign new value to the node. Step 3 − Compare the value of this child node with its parent. Step 4 − If value of parent is less than child, then swap them. Step 5 − Repeat step 3 & 4 until Heap property holds. Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node. Let”s understand Max Heap construction by an animated illustration. We consider the same input sample that we used earlier. Example Following are the implementations of this operation in various programming languages − C C++ Java Python //C code for Max Heap construction Algorithm #include <stdio.h> #include <stdlib.h> // Structure to represent a heap typedef struct { int* array; // Array to store heap elements int capacity; // Maximum capacity of the heap int size; // Current size of the heap } Heap; // Function to create a new heap Heap* createHeap(int capacity) { Heap* heap = (Heap*)malloc(sizeof(Heap)); heap->array = (int*)malloc(capacity * sizeof(int)); heap->capacity = capacity; heap->size = 0; return heap; } // Function to swap two elements in the heap void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // Function to heapify a subtree rooted at index i void heapify(Heap* heap, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // Check if the left child is larger than the root if (left < heap->size && heap->array[left] > heap->array[largest]) largest = left; // Check if the right child is larger than the largest so far if (right < heap->size && heap->array[right] > heap->array[largest]) largest = right; // If the largest is not the root, swap the root with the largest if (largest != i) { swap(&heap->array[i], &heap->array[largest]); heapify(heap, largest); } } // Function to insert a new element into the heap void insert(Heap* heap, int value) { if (heap->size == heap->capacity) { printf(“Heap is full. Cannot insert more elements.n”); return; } // Insert the new element at the end int i = heap->size++; heap->array[i] = value; // Fix the heap property if it is violated while (i != 0 && heap->array[(i – 1) / 2] < heap->array[i]) { swap(&heap->array[i], &heap->array[(i – 1) / 2]); i = (i – 1) / 2; } } // Function to extract the maximum element from the heap int extractMax(Heap* heap) { if (heap->size == 0) { printf(“Heap is empty. Cannot extract maximum element.n”); return -1; } // Store the root element int max = heap->array[0]; // Replace the root with the last element heap->array[0] = heap->array[heap->size – 1]; heap->size–; // Heapify the root heapify(heap, 0); return max; } // Function to print the elements of the heap void printHeap(Heap* heap) { printf(“Heap elements: “); for (int i = 0; i < heap->size; i++) { printf(“%d “, heap->array[i]); } printf(“n”); } // Example usage of the heap int main() { Heap* heap = createHeap(10); insert(heap, 35); insert(heap, 33); insert(heap, 42); insert(heap, 10); insert(heap, 14); insert(heap, 19); insert(heap, 27); insert(heap, 44); insert(heap, 26); insert(heap, 31); printHeap(heap); int max = extractMax(heap); printf(“Maximum element: %dn”, max); return 0; } Output Heap elements: 44 42 35 33 31 19 27 10 26 14 Maximum element: 44 //C++ code for Max Heap construction Algorithm #include <iostream> // Structure to represent a heap struct Heap { int* array; // Array to store heap elements int capacity; // Maximum capacity of the heap int size; // Current size of the heap }; // Function to create a new heap Heap* createHeap(int capacity) { Heap* heap = new Heap; heap->array = new int[capacity]; heap->capacity = capacity; heap->size = 0; return heap; } // Function to swap two elements in the heap void swap(int& a, int& b) { int temp = a; a = b; b = temp; } // Function to heapify a subtree rooted at index i void heapify(Heap* heap, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // Check if the left child is larger than the root if (left <heap->size && heap->array[left] > heap->array[largest]) largest = left; // Check if the right child is larger than the largest so far if (right <heap->size && heap->array[right] > heap->array[largest]) largest = right; // If the largest is not the root, swap the root with the largest if (largest != i) { swap(heap->array[i], heap->array[largest]); heapify(heap, largest); } } // Function to insert a new element into

Travelling Salesman using Approximation Algorithm Table of content Travelling Salesman Approximation Algorithm Implementation ”; Previous Next We have already discussed the travelling salesperson problem using the greedy and dynamic programming approaches, and it is established that solving the travelling salesperson problems for the perfect optimal solutions is not possible in polynomial time. Therefore, the approximation solution is expected to find a near optimal solution for this NP-Hard problem. However, an approximate algorithm is devised only if the cost function (which is defined as the distance between two plotted points) in the problem satisfies triangle inequality. The triangle inequality is satisfied only if the cost function c, for all the vertices of a triangle u, v and w, satisfies the following equation c(u, w)≤ c(u, v)+c(v, w) It is usually automatically satisfied in many applications. Travelling Salesperson Approximation Algorithm The travelling salesperson approximation algorithm requires some prerequisite algorithms to be performed so we can achieve a near optimal solution. Let us look at those prerequisite algorithms briefly − Minimum Spanning Tree − The minimum spanning tree is a tree data structure that contains all the vertices of main graph with minimum number of edges connecting them. We apply prim’s algorithm for minimum spanning tree in this case. Pre-order Traversal − The pre-order traversal is done on tree data structures where a pointer is walked through all the nodes of the tree in a [root – left child – right child] order. Algorithm Step 1 − Choose any vertex of the given graph randomly as the starting and ending point. Step 2 − Construct a minimum spanning tree of the graph with the vertex chosen as the root using prim’s algorithm. Step 3 − Once the spanning tree is constructed, pre-order traversal is performed on the minimum spanning tree obtained in the previous step. Step 4 − The pre-order solution obtained is the Hamiltonian path of the travelling salesperson. Pseudocode APPROX_TSP(G, c) r <- root node of the minimum spanning tree T <- MST_Prim(G, c, r) visited = {ф} for i in range V: H <- Preorder_Traversal(G) visited = {H} Analysis The approximation algorithm of the travelling salesperson problem is a 2-approximation algorithm if the triangle inequality is satisfied. To prove this, we need to show that the approximate cost of the problem is double the optimal cost. Few observations that support this claim would be as follows − The cost of minimum spanning tree is never less than the cost of the optimal Hamiltonian path. That is, c(M) ≤ c(H*). The cost of full walk is also twice as the cost of minimum spanning tree. A full walk is defined as the path traced while traversing the minimum spanning tree preorderly. Full walk traverses every edge present in the graph exactly twice. Thereore, c(W) = 2c(T) Since the preorder walk path is less than the full walk path, the output of the algorithm is always lower than the cost of the full walk. Example Let us look at an example graph to visualize this approximation algorithm − Solution Consider vertex 1 from the above graph as the starting and ending point of the travelling salesperson and begin the algorithm from here. Step 1 Starting the algorithm from vertex 1, construct a minimum spanning tree from the graph. To learn more about constructing a minimum spanning tree, please click here. Step 2 Once, the minimum spanning tree is constructed, consider the starting vertex as the root node (i.e., vertex 1) and walk through the spanning tree preorderly. Rotating the spanning tree for easier interpretation, we get − The preorder traversal of the tree is found to be − 1 → 2 → 5 → 6 → 3 → 4 Step 3 Adding the root node at the end of the traced path, we get, 1 → 2 → 5 → 6 → 3 → 4 → 1 This is the output Hamiltonian path of the travelling salesman approximation problem. The cost of the path would be the sum of all the costs in the minimum spanning tree, i.e., 55. Implementation Following are the implementations of the above approach in various programming langauges − C C++ Java Python #include <stdio.h> #include <stdbool.h> #include <limits.h> #define V 6 // Number of vertices in the graph // Function to find the minimum key vertex from the set of vertices not yet included in MST int findMinKey(int key[], bool mstSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) { if (mstSet[v] == false && key[v] < min) { min = key[v]; min_index = v; } } return min_index; } // Function to perform Prim”s algorithm to find the Minimum Spanning Tree (MST) void primMST(int graph[V][V], int parent[]) { int key[V]; bool mstSet[V]; for (int i = 0; i < V; i++) { key[i] = INT_MAX; mstSet[i] = false; } key[0] = 0; parent[0] = -1; for (int count = 0; count < V – 1; count++) { int u = findMinKey(key, mstSet); mstSet[u] = true; for (int v = 0; v < V; v++) { if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) { parent[v] = u; key[v] = graph[u][v]; } } } } // Function to print the preorder traversal of the Minimum Spanning Tree void printPreorderTraversal(int parent[]) { printf(“The preorder traversal of the tree is found to be − “); for (int i = 1; i < V; i++) { printf(“%d → “, parent[i]); } printf(“n”); } // Main function for the Traveling Salesperson Approximation Algorithm void tspApproximation(int graph[V][V]) { int parent[V]; int root = 0; // Choosing

Splay Trees Table of content Basic Operations of Splay Trees Insertion operation Deletion operation Search operation ”; Previous Next Splay trees are the altered versions of the Binary Search Trees, since it contains all the operations of BSTs, like insertion, deletion and searching, followed by another extended operation called splaying. For instance, a value “A” is supposed to be inserted into the tree. If the tree is empty, add “A” to the root of the tree and exit; but if the tree is not empty, use binary search insertion operation to insert the element and then perform splaying on the new node. Similarly, after searching an element in the splay tree, the node consisting of the element must be splayed as well. But how do we perform splaying? Splaying, in simpler terms, is just a process to bring an operational node to the root. There are six types of rotations for it. Zig rotation Zag rotation Zig-Zig rotation Zag-Zag rotation Zig-Zag rotation Zag-Zig rotation Zig rotation The zig rotations are performed when the operational node is either the root node or the left child node of the root node. The node is rotated towards its right. After the shift, the tree will look like − Zag rotation The zag rotations are also performed when the operational node is either the root node or the right child nod of the root node. The node is rotated towards its left. The operational node becomes the root node after the shift − Zig-Zig rotation The zig-zig rotations are performed when the operational node has both parent and a grandparent. The node is rotated two places towards its right. The first rotation will shift the tree to one position right − The second right rotation will once again shift the node for one position. The final tree after the shift will look like this − Zag-Zag rotation The zag-zag rotations are also performed when the operational node has both parent and a grandparent. The node is rotated two places towards its left. After the first rotation, the tree will look like − Then the final tree after the second rotation is given as follows. However, the operational node is still not the root so the splaying is considered incomplete. Hence, other suitable rotations are again applied in this case until the node becomes the root. Zig-Zag rotation The zig-zag rotations are performed when the operational node has both a parent and a grandparent. But the difference is the grandparent, parent and child are in LRL format. The node is rotated first towards its right followed by left. After the first rotation, the tree is − The final tree after the second rotation − Zag-Zig rotation The zag-zig rotations are also performed when the operational node has both parent and grandparent. But the difference is the grandparent, parent and child are in RLR format. The node is rotated first towards its left followed by right. First rotation is performed, the tree is obtained as − After second rotation, the final tree is given as below. However, the operational node is not the root node yet so one more rotation needs to be performed to make the said node as the root. Basic Operations of Splay Trees A splay contains the same basic operations that a Binary Search Tree provides with: Insertion, Deletion, and Search. However, after every operation there is an additional operation that differs them from Binary Search tree operations: Splaying. We have learned about Splaying already so let us understand the procedures of the other operations. Insertion operation The insertion operation in a Splay tree is performed in the exact same way insertion in a binary search tree is performed. The procedure to perform the insertion in a splay tree is given as follows − Check whether the tree is empty; if yes, add the new node and exit If the tree is not empty, add the new node to the existing tree using the binary search insertion. Then, suitable splaying is chosen and applied on the newly added node. Zag (Left) Rotation is applied on the new node Example Following are the implementations of this operation in various programming languages − C C++ Java Python #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *leftChild, *rightChild; }; struct node* newNode(int data){ struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->data = data; Node->leftChild = Node->rightChild = NULL; return (Node); } struct node* rightRotate(struct node *x){ struct node *y = x->leftChild; x->leftChild = y->rightChild; y->rightChild = x; return y; } struct node* leftRotate(struct node *x){ struct node *y = x->rightChild; x->rightChild = y->leftChild; y->leftChild = x; return y; } struct node* splay(struct node *root, int data){ if (root == NULL || root->data == data) return root; if (root->data > data) { if (root->leftChild == NULL) return root; if (root->leftChild->data > data) { root->leftChild->leftChild = splay(root->leftChild->leftChild, data); root = rightRotate(root); } else if (root->leftChild->data < data) { root->leftChild->rightChild = splay(root->leftChild->rightChild, data); if (root->leftChild->rightChild != NULL) root->leftChild = leftRotate(root->leftChild); } return (root->leftChild == NULL)? root: rightRotate(root); } else { if (root->rightChild == NULL) return root; if (root->rightChild->data > data) { root->rightChild->leftChild = splay(root->rightChild->leftChild, data); if (root->rightChild->leftChild != NULL) root->rightChild = rightRotate(root->rightChild); } else if (root->rightChild->data < data) { root->rightChild->rightChild = splay(root->rightChild->rightChild, data); root = leftRotate(root); } return (root->rightChild == NULL)? root: leftRotate(root); } } struct node* insert(struct node *root, int k){ if (root == NULL) return newNode(k); root =

Prim’s Minimal Spanning Tree Table of content Prim”s Algorithm Example ”; Previous Next Previous Page Next Page   Prim’s minimal spanning tree algorithm is one of the efficient methods to find the minimum spanning tree of a graph. A minimum spanning tree is a sub graph that connects all the vertices present in the main graph with the least possible edges and minimum cost (sum of the weights assigned to each edge). The algorithm, similar to any shortest path algorithm, begins from a vertex that is set as a root and walks through all the vertices in the graph by determining the least cost adjacent edges. Prim’s Algorithm To execute the prim’s algorithm, the inputs taken by the algorithm are the graph G {V, E}, where V is the set of vertices and E is the set of edges, and the source vertex S. A minimum spanning tree of graph G is obtained as an output. Algorithm Declare an array visited[] to store the visited vertices and firstly, add the arbitrary root, say S, to the visited array. Check whether the adjacent vertices of the last visited vertex are present in the visited[] array or not. If the vertices are not in the visited[] array, compare the cost of edges and add the least cost edge to the output spanning tree. The adjacent unvisited vertex with the least cost edge is added into the visited[] array and the least cost edge is added to the minimum spanning tree output. Steps 2 and 4 are repeated for all the unvisited vertices in the graph to obtain the full minimum spanning tree output for the given graph. Calculate the cost of the minimum spanning tree obtained. Examples Find the minimum spanning tree using prim’s method (greedy approach) for the graph given below with S as the arbitrary root. Solution Step 1 Create a visited array to store all the visited vertices into it. V = { } The arbitrary root is mentioned to be S, so among all the edges that are connected to S we need to find the least cost edge. S → B = 8 V = {S, B} Step 2 Since B is the last visited, check for the least cost edge that is connected to the vertex B. B → A = 9 B → C = 16 B → E = 14 Hence, B → A is the edge added to the spanning tree. V = {S, B, A} Step 3 Since A is the last visited, check for the least cost edge that is connected to the vertex A. A → C = 22 A → B = 9 A → E = 11 But A → B is already in the spanning tree, check for the next least cost edge. Hence, A → E is added to the spanning tree. V = {S, B, A, E} Step 4 Since E is the last visited, check for the least cost edge that is connected to the vertex E. E → C = 18 E → D = 3 Therefore, E → D is added to the spanning tree. V = {S, B, A, E, D} Step 5 Since D is the last visited, check for the least cost edge that is connected to the vertex D. D → C = 15 E → D = 3 Therefore, D → C is added to the spanning tree. V = {S, B, A, E, D, C} The minimum spanning tree is obtained with the minimum cost = 46 Example The final program implements Prim’s minimum spanning tree problem that takes the cost adjacency matrix as the input and prints the spanning tree as the output along with the minimum cost. C C++ Java Python #include<stdio.h> #include<stdlib.h> #define inf 99999 #define MAX 10 int G[MAX][MAX] = { {0, 19, 8}, {21, 0, 13}, {15, 18, 0} }; int S[MAX][MAX], n; int prims(); int main(){ int i, j, cost; n = 3; cost=prims(); printf(“Spanning tree:”); for(i=0; i<n; i++) { printf(“n”); for(j=0; j<n; j++) printf(“%dt”,S[i][j]); } printf(“nMinimum cost = %d”, cost); return 0; } int prims(){ int C[MAX][MAX]; int u, v, min_dist, dist[MAX], from[MAX]; int visited[MAX],ne,i,min_cost,j; //create cost[][] matrix,spanning[][] for(i=0; i<n; i++) for(j=0; j<n; j++) { if(G[i][j]==0) C[i][j]=inf; else C[i][j]=G[i][j]; S[i][j]=0; } //initialise visited[],distance[] and from[] dist[0]=0; visited[0]=1; for(i=1; i<n; i++) { dist[i] = C[0][i]; from[i] = 0; visited[i] = 0; } min_cost = 0; //cost of spanning tree ne = n-1; //no. of edges to be added while(ne > 0) { //find the vertex at minimum distance from the tree min_dist = inf; for(i=1; i<n; i++) if(visited[i] == 0 && dist[i] < min_dist) { v = i; min_dist = dist[i]; } u = from[v]; //insert the edge in spanning tree S[u][v] = dist[v]; S[v][u] = dist[v]; ne–; visited[v]=1; //updated the distance[] array for(i=1; i<n; i++) if(visited[i] == 0 && C[i][v] < dist[i]) { dist[i] = C[i][v]; from[i] = v; } min_cost = min_cost + C[u][v]; } return(min_cost); } Output Spanning tree: 0 0 8 0 0 13 8 13 0 Minimum cost = 26 #include<iostream> #define inf 999999 #define MAX 10 using namespace std; int G[MAX][MAX] = { {0, 19, 8}, {21, 0, 13}, {15, 18, 0} }; int S[MAX][MAX], n; int prims(); int main(){ int i, j, cost; n = 3; cost=prims(); cout <<“Spanning tree:”; for(i=0; i<n; i++) { cout

Karatsuba Algorithm Table of content Karatsuba Algorithm Analysis Example ”; Previous Next The Karatsuba algorithm is used by the system to perform fast multiplication on two n-digit numbers, i.e. the system compiler takes lesser time to compute the product than the time-taken by a normal multiplication. The usual multiplication approach takes n2 computations to achieve the final product, since the multiplication has to be performed between all digit combinations in both the numbers and then the sub-products are added to obtain the final product. This approach of multiplication is known as Naive Multiplication. To understand this multiplication better, let us consider two 4-digit integers: 1456 and 6533, and find the product using Naive approach. So, 1456 × 6533 =? In this method of naive multiplication, given the number of digits in both numbers is 4, there are 16 single-digit × single-digit multiplications being performed. Thus, the time complexity of this approach is O(42) since it takes 42 steps to calculate the final product. But when the value of n keeps increasing, the time complexity of the problem also keeps increasing. Hence, Karatsuba algorithm is adopted to perform faster multiplications. Karatsuba Algorithm The main idea of the Karatsuba Algorithm is to reduce multiplication of multiple sub problems to multiplication of three sub problems. Arithmetic operations like additions and subtractions are performed for other computations. For this algorithm, two n-digit numbers are taken as the input and the product of the two number is obtained as the output. Step 1 − In this algorithm we assume that n is a power of 2. Step 2 − If n = 1 then we use multiplication tables to find P = XY. Step 3 − If n > 1, the n-digit numbers are split in half and represent the number using the formulae − X = 10n/2X1 + X2 Y = 10n/2Y1 + Y2 where, X1, X2, Y1, Y2 each have n/2 digits. Step 4 − Take a variable Z = W – (U + V), where, U = X1Y1, V = X2Y2 W = (X1 + X2) (Y1 + Y2), Z = X1Y2 + X2Y1. Step 5 − Then, the product P is obtained after substituting the values in the formula − P = 10n(U) + 10n/2(Z) + V P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2. Step 6 − Recursively call the algorithm by passing the sub problems (X1, Y1), (X2, Y2) and (X1 + X2, Y1 + Y2) separately. Store the returned values in variables U, V and W respectively. Example Let us solve the same problem given above using Karatsuba method, 1456 × 6533 − The Karatsuba method takes the divide and conquer approach by dividing the problem into multiple sub-problems and applies recursion to make the multiplication simpler. Step 1 Assuming that n is the power of 2, rewrite the n-digit numbers in the form of − X = 10n/2X1 + X2 Y = 10n/2Y1 + Y2 That gives us, 1456 = 102(14) + 56 6533 = 102(65) + 33 First let us try simplifying the mathematical expression, we get, (1400 × 6500) + (56 × 33) + (1400 × 33) + (6500 × 56) = 104 (14 × 65) + 102 [(14 × 33) + (56 × 65)] + (33 × 56) The above expression is the simplified version of the given multiplication problem, since multiplying two double-digit numbers can be easier to solve rather than multiplying two four-digit numbers. However, that holds true for the human mind. But for the system compiler, the above expression still takes the same time complexity as the normal naive multiplication. Since it has 4 double-digit × double-digit multiplications, the time complexity taken would be − 14 × 65 → O(4) 14 × 33 → O(4) 65 × 56 → O(4) 56 × 33 → O(4) = O (16) Thus, the calculation needs to be simplified further. Step 2 X = 1456 Y = 6533 Since n is not equal to 1, the algorithm jumps to step 3. X = 10n/2X1 + X2 Y = 10n/2Y1 + Y2 That gives us, 1456 = 102(14) + 56 6533 = 102(65) + 33 Calculate Z = W – (U + V) − Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2) Z = X1Y2 + X2Y1 Z = (14 × 33) + (65 × 56) The final product, P = 10n. U + 10n/2. Z + V = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2 = 104 (14 × 65) + 102 [(14 × 33) + (65 × 56)] + (56 × 33) The sub-problems can be further divided into smaller problems; therefore, the algorithm is again called recursively. Step 3 X1 and Y1 are passed as parameters X and Y. So now, X = 14, Y = 65 X = 10n/2X1 + X2 Y = 10n/2Y1 + Y2 14 = 10(1) + 4 65 = 10(6) + 5 Calculate Z = W – (U + V) − Z = (X1 + X2) (Y1 + Y2) – (X1Y1 + X2Y2) Z = X1Y2 + X2Y1 Z = (1 × 5) + (6 × 4) = 29 P = 10n (X1Y1) + 10n/2 (X1Y2 + X2Y1) + X2Y2 = 102 (1 × 6) + 101 (29) + (4 × 5) = 910 Step 4 X2 and Y2 are passed as parameters X and Y.

Heap Sort Algorithm Table of content Heap Sort Algorithm Implementation ”; Previous Next Heap Sort is an efficient sorting technique based on the heap data structure. The heap is a nearly-complete binary tree where the parent node could either be minimum or maximum. The heap with minimum root node is called min-heap and the root node with maximum root node is called max-heap. The elements in the input data of the heap sort algorithm are processed using these two methods. The heap sort algorithm follows two main operations in this procedure − Builds a heap H from the input data using the heapify (explained further into the chapter) method, based on the way of sorting – ascending order or descending order. Deletes the root element of the root element and repeats until all the input elements are processed. The heap sort algorithm heavily depends upon the heapify method of the binary tree. So what is this heapify method? Heapify Method The heapify method of a binary tree is to convert the tree into a heap data structure. This method uses recursion approach to heapify all the nodes of the binary tree. Note − The binary tree must always be a complete binary tree as it must have two children nodes always. The complete binary tree will be converted into either a max-heap or a min-heap by applying the heapify method. To know more about the heapify algorithm, please click here. Heap Sort Algorithm As described in the algorithm below, the sorting algorithm first constructs the heap ADT by calling the Build-Max-Heap algorithm and removes the root element to swap it with the minimum valued node at the leaf. Then the heapify method is applied to rearrange the elements accordingly. Algorithm: Heapsort(A) BUILD-MAX-HEAP(A) for i = A.length downto 2 exchange A[1] with A[i] A.heap-size = A.heap-size – 1 MAX-HEAPIFY(A, 1) Analysis The heap sort algorithm is the combination of two other sorting algorithms: insertion sort and merge sort. The similarities with insertion sort include that only a constant number of array elements are stored outside the input array at any time. The time complexity of the heap sort algorithm is O(nlogn), similar to merge sort. Example Let us look at an example array to understand the sort algorithm better − 12 3 9 14 10 18 8 23 Building a heap using the BUILD-MAX-HEAP algorithm from the input array − Rearrange the obtained binary tree by exchanging the nodes such that a heap data structure is formed. The Heapify Algorithm Applying the heapify method, remove the root node from the heap and replace it with the next immediate maximum valued child of the root. The root node is 23, so 23 is popped and 18 is made the next root because it is the next maximum node in the heap. Now, 18 is popped after 23 which is replaced by 14. The current root 14 is popped from the heap and is replaced by 12. 12 is popped and replaced with 10. Similarly all the other elements are popped using the same process. Here the current root element 9 is popped and the elements 8 and 3 are remained in the tree. Then, 8 will be popped leaving 3 in the tree. After completing the heap sort operation on the given heap, the sorted elements are displayed as shown below − Every time an element is popped, it is added at the beginning of the output array since the heap data structure formed is a max-heap. But if the heapify method converts the binary tree to the min-heap, add the popped elements are on the end of the output array. The final sorted list is, 3 8 9 10 12 14 18 23 Implementation The logic applied on the implementation of the heap sort is: firstly, the heap data structure is built based on the max-heap property where the parent nodes must have greater values than the child nodes. Then the root node is popped from the heap and the next maximum node on the heap is shifted to the root. The process is continued iteratively until the heap is empty. In this tutorial, we show the heap sort implementation in four different programming languages. C C++ Java Python #include <stdio.h> void heapify(int[], int); void build_maxheap(int heap[], int n){ int i, j, c, r, t; for (i = 1; i < n; i++) { c = i; do { r = (c – 1) / 2; if (heap[r] < heap[c]) { // to create MAX heap array t = heap[r]; heap[r] = heap[c]; heap[c] = t; } c = r; } while (c != 0); } printf(“Heap array: “); for (i = 0; i < n; i++) printf(“%d “, heap[i]); heapify(heap, n); } void heapify(int heap[], int n){ int i, j, c, root, temp; for (j = n – 1; j >= 0; j–) { temp = heap[0]; heap[0] = heap[j]; // swap max element with rightmost leaf element heap[j] = temp; root = 0; do { c = 2 * root + 1; // left node of root element if ((heap[c] < heap[c + 1]) && c < j-1) c++; if (heap[root]<heap[c] && c<j) { // again rearrange to max heap array temp = heap[root]; heap[root] = heap[c]; heap[c] = temp; } root = c; } while (c < j); } printf(“nThe sorted array is: “);

Discuss Data Structures & Algorithms ”; Previous Next Data Structures are the programmatic way of storing data so that data can be used efficiently. Almost every enterprise application uses various types of data structures in one or the other way. This tutorial will give you a great understanding on Data Structures needed to understand the complexity of enterprise level applications and need of algorithms, and data structures. Print Page Previous Next Advertisements ”;

Fisher-Yates Shuffle Algorithm Table of content Fisher-Yates Algorithm Example ”; Previous Next The Fisher-Yates Shuffle algorithm shuffles a finite sequence of elements by generating a random permutation. The possibility of every permutation occurring is equally likely. The algorithm is performed by storing the elements of the sequence in a sack and drawing each element randomly from the sack to form the shuffled sequence. Coined after Ronald Fisher and Frank Yates, for designing the original method of the shuffle, the algorithm is unbiased. It generates all permutations in same conditions so the output achieved is nowhere influenced. However, the modern version of the Fisher-Yates Algorithm is more efficient than that of the original one. Fisher-Yates Algorithm The Original Method The original method of Shuffle algorithm involved a pen and paper to generate a random permutation of a finite sequence. The algorithm to generate the random permutation is as follows − Step 1 − Write down all the elements in the finite sequence. Declare a separate list to store the output achieved. Step 2 − Choose an element i randomly in the input sequence and add it onto the output list. Mark the element i as visited. Step 3 − Repeat Step 2 until all the element in the finite sequence is visited and added onto the output list randomly. Step 4 − The output list generated after the process terminates is the random permutation generated. The Modern Algorithm The modern algorithm is a slightly modified version of the original fisher-yates shuffle algorithm. The main goal of the modification is to computerize the original algorithm by reducing the time complexity of the original method. The modern method is developed by Richard Durstenfeld and was popularized by Donald E. Knuth. Therefore, the modern method makes use of swapping instead of maintaining another output list to store the random permutation generated. The time complexity is reduced to O(n) rather than O(n2). The algorithm goes as follows − Step 1 − Write down the elements 1 to n in the finite sequence. Step 2 − Choose an element i randomly in the input sequence and swap it with the last unvisited element in the list. Step 3 − Repeat Step 2 until all the element in the finite sequence is visited and swapped. Step 4 − The list generated after the process terminates is the random permutation sequence. Pseudocode Shuffling is done from highest index to the lowest index of the array in the following modern method pseudocode. Fisher-Yates Shuffle (array of n elements): for i from n−1 downto 1 do j ← random integer such that 0 ≤ j ≤ i exchange a[j] and a[i] Shuffling is done from lowest index to the highest index of the array in the following modern method pseudocode. Fisher-Yates Shuffle (array of n elements): for i from 0 to n−2 do j ← random integer such that i ≤ j < n exchange a[i] and a[j] Original Method Example To describe the algorithm better, let us permute the the given finite sequence of the first six letters of the alphabet. Input sequence: A B C D E F. Step 1 This is called the pen and paper method. We consider an input array with the finite sequence stored and an output array to store the result. Step 2 Choose any element randomly and add it onto the output list after marking it checked. In this case, we choose element C. Step 3 The next element chosen randomly is E which is marked and added to the output list. Step 4 The random function then picks the next element A and adds it onto the output array after marking it visited. Step 5 Then F is selected from the remaining elements in the input sequence and added to the output after marking it visited. Step 6 The next element chosen to add onto the random permutation is D. It is marked and added to the output array. Step 7 The last element present in the input list would be B, so it is marked and added onto the output list finally. Modern Method Example In order to reduce time complexity of the original method, the modern algorithm is introduced. The modern method uses swapping to shuffle the sequences – for example, the algorithm works like shuffling a pack of cards by swapping their places in the original deck. Let us look at an example to understand how modern version of the Fisher-Yates algorithm works. Step 1 Consider first few letters of the alphabet as an input and shuffle them using the modern method. Step 2 Randomly choosing the element D and swapping it with the last unmarked element in the sequence, in this case F. Step 3 For the next step we choose element B to swap with the last unmarked element ‘E’ since F had been moved to D’s place after swapping in the previous step. Step 4 We next swap the element A with F, since it is the last unmarked element in the list. Step 5 Then the element F is swapped with the last unmarked element C. Step 6 The remaining elements in the sequence could be swapped finally, but since the random function chose E as the element it is left as it is. Step 7 The remaining element C is left as it is without swapping. The array obtained after swapping is the final output array. Example Following are

Randomized Quick Sort Algorithm Table of content Randomized Quick Sort Algorithm Implementation ”; Previous Next Quicksort is a popular sorting algorithm that chooses a pivot element and sorts the input list around that pivot element. To learn more about quick sort, please click here. Randomized quick sort is designed to decrease the chances of the algorithm being executed in the worst case time complexity of O(n2). The worst case time complexity of quick sort arises when the input given is an already sorted list, leading to n(n – 1) comparisons. There are two ways to randomize the quicksort − Randomly shuffling the inputs: Randomization is done on the input list so that the sorted input is jumbled again which reduces the time complexity. However, this is not usually performed in the randomized quick sort. Randomly choosing the pivot element: Making the pivot element a random variable is commonly used method in the randomized quick sort. Here, even if the input is sorted, the pivot is chosen randomly so the worst case time complexity is avoided. Randomized Quick Sort Algorithm The algorithm exactly follows the standard algorithm except it randomizes the pivot selection. Pseudocode partition-left(arr[], low, high) pivot = arr[high] i = low // place for swapping for j := low to high – 1 do if arr[j] <= pivot then swap arr[i] with arr[j] i = i + 1 swap arr[i] with arr[high] return i partition-right(arr[], low, high) r = Random Number from low to high Swap arr[r] and arr[high] return partition-left(arr, low, high) quicksort(arr[], low, high) if low < high p = partition-right(arr, low, high) quicksort(arr, low , p-1) quicksort(arr, p+1, high) Example Let us look at an example to understand how randomized quicksort works in avoiding the worst case time complexity. Since, we are designing randomized algorithms to decrease the occurrence of worst cases in time complexity lets take a sorted list as an input for this example. The sorted input list is 3, 5, 7, 8, 12, 15. We need to apply the quick sort algorithm to sort the list. Step 1 Considering the worst case possible, if the random pivot chosen is also the highest index number, it compares all the other numbers and another pivot is selected. Since 15 is greater than all the other numbers in the list, it won’t be swapped, and another pivot is chosen. Step 2 This time, if the random pivot function chooses 7 as the pivot number − Now the pivot divides the list into half so standard quick sort is carried out usually. However, the time complexity is decreased than the worst case. It is to be noted that the worst case time complexity of the quick sort will always remain O(n2) but with randomizations we are decreasing the occurrences of that worst case. Implementation Following are the implementations of the above approach in various programming langauges − C C++ Java Python #include <stdio.h> #include <stdlib.h> #include <time.h> // Function to swap two elements void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // Function to partition the array int partition_left(int arr[], int low, int high) { int pivot = arr[high]; int i = low; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { swap(&arr[i], &arr[j]); i++; } } swap(&arr[i], &arr[high]); return i; } // Function to perform random partition int partition_right(int arr[], int low, int high) { srand(time(NULL)); int r = low + rand() % (high – low); swap(&arr[r], &arr[high]); return partition_left(arr, low, high); } // Recursive function for quicksort void quicksort(int arr[], int low, int high) { if (low < high) { int p = partition_right(arr, low, high); quicksort(arr, low, p – 1); quicksort(arr, p + 1, high); } } // Function to print the array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf(“%d “, arr[i]); printf(“n”); } // Driver code int main() { int arr[] = { 6, 4, 12, 8, 15, 16}; int n = sizeof(arr) / sizeof(arr[0]); printf(“Original array: “); printArray(arr, n); quicksort(arr, 0, n – 1); printf(“Sorted array: “); printArray(arr, n); return 0; } Output Original array: 6 4 12 8 15 16 Sorted array: 4 6 8 12 15 16 #include <iostream> #include <cstdlib> #include <ctime> // Function to swap two elements void swap(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Function to partition the array int partitionLeft(int arr[], int low, int high) { int pivot = arr[high]; int i = low; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { swap(arr, i, j); i++; } } swap(arr, i, high); return i; } // Function to perform random partition int partitionRight(int arr[], int low, int high) { srand(time(NULL)); int r = low + rand() % (high – low); swap(arr, r, high); return partitionLeft(arr, low, high); } // Recursive function for quicksort void quicksort(int arr[], int low, int high) { if (low < high) { int p = partitionRight(arr, low, high); quicksort(arr, low, p – 1); quicksort(arr, p + 1, high); } } // Function to print the array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) std::cout << arr[i] << ” “; std::cout << std::endl; } // Driver code int main() { int arr[] = {6, 4, 12, 8, 15, 16}; int n = sizeof(arr) / sizeof(arr[0]); std::cout << “Original array: “; printArray(arr, n); quicksort(arr, 0, n – 1); std::cout << “Sorted array: “; printArray(arr, n); return 0; } Output Original array: 6