Category: data Structures Algorithms

Expression Parsing in Data Structure ”; Previous Next An expression is any word or group of words or symbols that generates a value on evaluation. Parsing expression means analyzing the expression for its words or symbols depending on a particular criterion. Expression parsing is a term used in a programming language to evaluate arithmetic and logical expressions. The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression. These notations are − Infix Notation Prefix (Polish) Notation Postfix (Reverse-Polish) Notation These notations are named as how they use operator in expression. We shall learn the same here in this chapter. Infix Notation We write expression in infix notation, e.g. a – b &plus; c, where operators are used in-between operands. It is easy for us humans to read, write, and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption. Prefix Notation In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For example, &plus;ab. This is equivalent to its infix notation a &plus; b. Prefix notation is also known as Polish Notation. Postfix Notation This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfixed to the operands i.e., the operator is written after the operands. For example, ab&plus;. This is equivalent to its infix notation a &plus; b. The following table briefly tries to show the difference in all three notations − Sr.No. Infix Notation Prefix Notation Postfix Notation 1 a &plus; b &plus; a b a b &plus; 2 (a &plus; b) ∗ c ∗ &plus; a b c a b &plus; c ∗ 3 a ∗ (b &plus; c) ∗ a &plus; b c a b c &plus; ∗ 4 a / b &plus; c / d &plus; / a b / c d a b / c d / &plus; 5 (a &plus; b) ∗ (c &plus; d) ∗ &plus; a b &plus; c d a b &plus; c d &plus; ∗ 6 ((a &plus; b) ∗ c) – d – ∗ &plus; a b c d a b &plus; c ∗ d – Parsing Expressions As we have discussed, it is not a very efficient way to design an algorithm or program to parse infix notations. Instead, these infix notations are first converted into either postfix or prefix notations and then computed. To parse any arithmetic expression, we need to take care of operator precedence and associativity also. Precedence When an operand is in between two different operators, which operator will take the operand first, is decided by the precedence of an operator over others. For example − As multiplication operation has precedence over addition, b * c will be evaluated first. A table of operator precedence is provided later. Associativity Associativity describes the rule where operators with the same precedence appear in an expression. For example, in expression a &plus; b − c, both &plus; and − have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both &plus; and − are left associative, so the expression will be evaluated as (a &plus; b) − c. Precedence and associativity determines the order of evaluation of an expression. Following is an operator precedence and associativity table (highest to lowest) − Sr.No. Operator Precedence Associativity 1 Exponentiation ^ Highest Right Associative 2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative 3 Addition ( &plus; ) & Subtraction ( − ) Lowest Left Associative The above table shows the default behavior of operators. At any point of time in expression evaluation, the order can be altered by using parenthesis. For example − In a &plus; b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. We here use parenthesis for a &plus; b to be evaluated first, like (a &plus; b)*c. Postfix Evaluation Algorithm We shall now look at the algorithm on how to evaluate postfix notation − Step 1. Scan the expression from left to right Step 2. If it is an operand push it to stack Step 3. If it is an operator pull operand from stack and perform operation Step 4. Store the output of step 3, back to stack Step 5. Scan the expression until all operands are consumed Step 6. Pop the stack and perform operation Expression Parsing – Complete implementation Following are the complete implementations of Expression Parsing (Conversion from infix notations to postfix notations) in various programming languages − C C++ Java Python #include<stdio.h> #include<string.h> #include<ctype.h> //char stack char stack[25]; int top = -1; void push(char item) { stack[++top] = item; } char pop() { return stack[top–]; } //returns precedence of operators int precedence(char symbol) { switch(symbol) { case ”+”: case ”-”: return 2; break; case ”*”: case ”/”: return 3; break; case ”^”: return 4; break; case ”(”: case ”)”: case ”#”: return 1; break; } } //check whether the symbol is operator? int isOperator(char symbol) { switch(symbol) { case ”+”: case ”-”: case ”*”: case ”/”: case ”^”: case ”(”: case ”)”: return 1; break; default: return 0; } } //converts infix expression to postfix void convert(char infix[],char postfix[]) { int i,symbol,j = 0; stack[++top] = ”#”; for(i = 0;i<strlen(infix);i++) { symbol = infix[i]; if(isOperator(symbol) == 0) { postfix[j] = symbol; j++; } else { if(symbol == ”(”) { push(symbol); } else { if(symbol == ”)”) { while(stack[top] != ”(”) { postfix[j] = pop(); j++; } pop(); //pop out (. } else { if(precedence(symbol)>precedence(stack[top])) { push(symbol); } else { while(precedence(symbol)<=precedence(stack[top])) { postfix[j] = pop(); j++; } push(symbol); } } } } } while(stack[top] != ”#”) { postfix[j] = pop(); j++; } postfix[j]=””; //null terminate string. }

Breadth First Search (BFS) Algorithm ”; Previous Next Breadth First Search (BFS) Algorithm Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion to search a graph data structure for a node that meets a set of criteria. It uses a queue to remember the next vertex to start a search, when a dead end occurs in any iteration. Breadth First Search (BFS) algorithm starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs the following rules. Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue. Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue. Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty. Step Traversal Description 1 Initialize the queue. 2 We start from visiting S (starting node), and mark it as visited. 3 We then see an unvisited adjacent node from S. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it. 4 Next, the unvisited adjacent node from S is B. We mark it as visited and enqueue it. 5 Next, the unvisited adjacent node from S is C. We mark it as visited and enqueue it. 6 Now, S is left with no unvisited adjacent nodes. So, we dequeue and find A. 7 From A we have D as unvisited adjacent node. We mark it as visited and enqueue it. At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the program is over. Example Following are the implementations of Breadth First Search (BFS) Algorithm in various programming languages − C C++ Java Python #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 struct Vertex { char label; bool visited; }; //queue variables int queue[MAX]; int rear = -1; int front = 0; int queueItemCount = 0; //graph variables //array of vertices struct Vertex* lstVertices[MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //queue functions void insert(int data) { queue[++rear] = data; queueItemCount++; } int removeData() { queueItemCount–; return queue[front++]; } bool isQueueEmpty() { return queueItemCount == 0; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void displayVertex(int vertexIndex) { printf(“%c “,lstVertices[vertexIndex]->label); } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; i<vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) return i; } return -1; } void breadthFirstSearch() { int i; //mark first node as visited lstVertices[0]->visited = true; //display the vertex displayVertex(0); //insert vertex index in queue insert(0); int unvisitedVertex; while(!isQueueEmpty()) { //get the unvisited vertex of vertex which is at front of the queue int tempVertex = removeData(); //no adjacent vertex found while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); insert(unvisitedVertex); } } //queue is empty, search is complete, reset the visited flag for(i = 0;i<vertexCount;i++) { lstVertices[i]->visited = false; } } int main() { int i, j; for(i = 0; i<MAX; i++) { // set adjacency for(j = 0; j<MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; } addVertex(”S”); // 0 addVertex(”A”); // 1 addVertex(”B”); // 2 addVertex(”C”); // 3 addVertex(”D”); // 4 addEdge(0, 1); // S – A addEdge(0, 2); // S – B addEdge(0, 3); // S – C addEdge(1, 4); // A – D addEdge(2, 4); // B – D addEdge(3, 4); // C – D printf(“nBreadth First Search: “); breadthFirstSearch(); return 0; } Output Breadth First Search: S A B C D //C++ code for Breadth First Traversal #include <iostream> #include <stdlib.h> #include <stdbool.h> #define MAX 5 struct Vertex { char label; bool visited; }; //queue variables int queue[MAX]; int rear = -1; int front = 0; int queueItemCount = 0; //graph variables //array of vertices struct Vertex* lstVertices[MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //queue functions void insert(int data) { queue[++rear] = data; queueItemCount++; } int removeData() { queueItemCount–; return queue[front++]; } bool isQueueEmpty() { return queueItemCount == 0; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void displayVertex(int vertexIndex) { std::cout << lstVertices[vertexIndex]->label << ” “; } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; i<vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) return i; } return -1; } void breadthFirstSearch() { int i; //mark first node as visited lstVertices[0]->visited = true; //display the vertex displayVertex(0); //insert vertex index in queue insert(0); int unvisitedVertex; while(!isQueueEmpty()) { //get the unvisited vertex of vertex which is at front of the queue int tempVertex = removeData(); //no adjacent vertex found while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); insert(unvisitedVertex); } } //queue is empty, search is complete, reset the visited flag for(i = 0;i<vertexCount;i++) { lstVertices[i]->visited = false; } } int main() { int i, j; for(i = 0; i<MAX; i++) { // set adjacency for(j = 0; j<MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; } addVertex(”S”); // 0 addVertex(”A”); // 1 addVertex(”B”); // 2 addVertex(”C”); // 3 addVertex(”D”); // 4 addEdge(0, 1); // S – A addEdge(0, 2); // S – B addEdge(0,

Optimal Merge Pattern Algorithm Table of content Pseudocode Example ”; Previous Next Merge a set of sorted files of different length into a single sorted file. We need to find an optimal solution, where the resultant file will be generated in minimum time. If the number of sorted files are given, there are many ways to merge them into a single sorted file. This merge can be performed pair wise. Hence, this type of merging is called as 2-way merge patterns. As, different pairings require different amounts of time, in this strategy we want to determine an optimal way of merging many files together. At each step, two shortest sequences are merged. To merge a p-record file and a q-record file requires possibly p + q record moves, the obvious choice being, merge the two smallest files together at each step. Two-way merge patterns can be represented by binary merge trees. Let us consider a set of n sorted files {f1, f2, f3, …, fn}. Initially, each element of this is considered as a single node binary tree. To find this optimal solution, the following algorithm is used. Pseudocode Following is the pseudocode of the Optimal Merge Pattern Algorithm − for i := 1 to n – 1 do declare new node node.leftchild := least (list) node.rightchild := least (list) node.weight) := ((node.leftchild).weight)+ ((node.rightchild).weight) insert (list, node); return least (list); At the end of this algorithm, the weight of the root node represents the optimal cost. Examples Let us consider the given files, f1, f2, f3, f4 and f5 with 20, 30, 10, 5 and 30 number of elements respectively. If merge operations are performed according to the provided sequence, then M1 = merge f1 and f2 => 20 + 30 = 50 M2 = merge M1 and f3 => 50 + 10 = 60 M3 = merge M2 and f4 => 60 + 5 = 65 M4 = merge M3 and f5 => 65 + 30 = 95 Hence, the total number of operations is 50 + 60 + 65 + 95 = 270 Now, the question arises is there any better solution? Sorting the numbers according to their size in an ascending order, we get the following sequence − f4, f3, f1, f2, f5 Hence, merge operations can be performed on this sequence M1 = merge f4 and f3 => 5 + 10 = 15 M2 = merge M1 and f1 => 15 + 20 = 35 M3 = merge M2 and f2 => 35 + 30 = 65 M4 = merge M3 and f5 => 65 + 30 = 95 Therefore, the total number of operations is 15 + 35 + 65 + 95 = 210 Obviously, this is better than the previous one. In this context, we are now going to solve the problem using this algorithm. Initial Set Step 1 Step 2 Step 3 Step 4 Hence, the solution takes 15 + 35 + 60 + 95 = 205 number of comparisons. Example Following are the implementations of the above approach in various programming languages − C C++ Java Python #include <stdio.h> #include <stdlib.h> int optimalMerge(int files[], int n) { // Sort the files in ascending order for (int i = 0; i < n – 1; i++) { for (int j = 0; j < n – i – 1; j++) { if (files[j] > files[j + 1]) { int temp = files[j]; files[j] = files[j + 1]; files[j + 1] = temp; } } } int cost = 0; while (n > 1) { // Merge the smallest two files int mergedFileSize = files[0] + files[1]; cost += mergedFileSize; // Replace the first file with the merged file size files[0] = mergedFileSize; // Shift the remaining files to the left for (int i = 1; i < n – 1; i++) { files[i] = files[i + 1]; } n–; // Reduce the number of files // Sort the files again for (int i = 0; i < n – 1; i++) { for (int j = 0; j < n – i – 1; j++) { if (files[j] > files[j + 1]) { int temp = files[j]; files[j] = files[j + 1]; files[j + 1] = temp; } } } } return cost; } int main() { int files[] = {5, 10, 20, 30, 30}; int n = sizeof(files) / sizeof(files[0]); int minCost = optimalMerge(files, n); printf(“Minimum cost of merging is: %d Comparisonsn”, minCost); return 0; } Output Minimum cost of merging is: 205 Comparisons #include <iostream> #include <algorithm> int optimalMerge(int files[], int n) { // Sort the files in ascending order for (int i = 0; i < n – 1; i++) { for (int j = 0; j < n – i – 1; j++) { if (files[j] > files[j + 1]) { std::swap(files[j], files[j + 1]); } } } int cost = 0; while (n > 1) { // Merge the smallest two files int mergedFileSize = files[0] + files[1]; cost += mergedFileSize; // Replace the first file with the merged file size files[0] = mergedFileSize; // Shift the remaining files to the left for (int i = 1; i < n – 1; i++) { files[i] = files[i + 1]; } n–; // Reduce the number of files // Sort the files again for (int i = 0; i < n – 1; i++) { for (int j = 0; j < n – i – 1; j++) { if (files[j] > files[j + 1]) { std::swap(files[j], files[j

Strassen’s Matrix Multiplication Table of content Naive Method Strassen’s Matrix Multiplication Algorithm Example ”; Previous Next Strassen”s Matrix Multiplication is the divide and conquer approach to solve the matrix multiplication problems. The usual matrix multiplication method multiplies each row with each column to achieve the product matrix. The time complexity taken by this approach is O(n3), since it takes two loops to multiply. Strassen’s method was introduced to reduce the time complexity from O(n3) to O(nlog 7). Naive Method First, we will discuss Naive method and its complexity. Here, we are calculating Z=𝑿X × Y. Using Naive method, two matrices (X and Y) can be multiplied if the order of these matrices are p × q and q × r and the resultant matrix will be of order p × r. The following pseudocode describes the Naive multiplication − Algorithm: Matrix-Multiplication (X, Y, Z) for i = 1 to p do for j = 1 to r do Z[i,j] := 0 for k = 1 to q do Z[i,j] := Z[i,j] + X[i,k] × Y[k,j] Complexity Here, we assume that integer operations take O(1) time. There are three for loops in this algorithm and one is nested in other. Hence, the algorithm takes O(n3) time to execute. Strassen’s Matrix Multiplication Algorithm In this context, using Strassen’s Matrix multiplication algorithm, the time consumption can be improved a little bit. Strassen’s Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices are n × n. Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below − $Z = begin{bmatrix}I & J \K & L end{bmatrix}$ $X = begin{bmatrix}A & B \C & D end{bmatrix}$ and $Y = begin{bmatrix}E & F \G & H end{bmatrix}$ Using Strassen’s Algorithm compute the following − $$M_{1} : colon= (A+C) times (E+F)$$ $$M_{2} : colon= (B+D) times (G+H)$$ $$M_{3} : colon= (A-D) times (E+H)$$ $$M_{4} : colon= A times (F-H)$$ $$M_{5} : colon= (C+D) times (E)$$ $$M_{6} : colon= (A+B) times (H)$$ $$M_{7} : colon= D times (G-E)$$ Then, $$I : colon= M_{2} + M_{3} – M_{6} – M_{7}$$ $$J : colon= M_{4} + M_{6}$$ $$K : colon= M_{5} + M_{7}$$ $$L : colon= M_{1} – M_{3} – M_{4} – M_{5}$$ Analysis $$T(n)=begin{cases}c & if:n= 1\7:x:T(frac{n}{2})+d:x:n^2 & otherwiseend{cases} :where: c: and :d:are: constants$$ Using this recurrence relation, we get $T(n) = O(n^{log7})$ Hence, the complexity of Strassen’s matrix multiplication algorithm is $O(n^{log7})$. Example Let us look at the implementation of Strassen”s Matrix Multiplication in various programming languages: C, C++, Java, Python. C C++ Java Python #include<stdio.h> int main(){ int z[2][2]; int i, j; int m1, m2, m3, m4 , m5, m6, m7; int x[2][2] = { {12, 34}, {22, 10} }; int y[2][2] = { {3, 4}, {2, 1} }; printf(“The first matrix is: “); for(i = 0; i < 2; i++) { printf(“n”); for(j = 0; j < 2; j++) printf(“%dt”, x[i][j]); } printf(“nThe second matrix is: “); for(i = 0; i < 2; i++) { printf(“n”); for(j = 0; j < 2; j++) printf(“%dt”, y[i][j]); } m1= (x[0][0] + x[1][1]) * (y[0][0] + y[1][1]); m2= (x[1][0] + x[1][1]) * y[0][0]; m3= x[0][0] * (y[0][1] – y[1][1]); m4= x[1][1] * (y[1][0] – y[0][0]); m5= (x[0][0] + x[0][1]) * y[1][1]; m6= (x[1][0] – x[0][0]) * (y[0][0]+y[0][1]); m7= (x[0][1] – x[1][1]) * (y[1][0]+y[1][1]); z[0][0] = m1 + m4- m5 + m7; z[0][1] = m3 + m5; z[1][0] = m2 + m4; z[1][1] = m1 – m2 + m3 + m6; printf(“nProduct achieved using Strassen”s algorithm: “); for(i = 0; i < 2 ; i++) { printf(“n”); for(j = 0; j < 2; j++) printf(“%dt”, z[i][j]); } return 0; } Output The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassen”s algorithm: 104 82 86 98 #include<iostream> using namespace std; int main() { int z[2][2]; int i, j; int m1, m2, m3, m4 , m5, m6, m7; int x[2][2] = { {12, 34}, {22, 10} }; int y[2][2] = { {3, 4}, {2, 1} }; cout<<“The first matrix is: “; for(i = 0; i < 2; i++) { cout<<endl; for(j = 0; j < 2; j++) cout<<x[i][j]<<” “; } cout<<“nThe second matrix is: “; for(i = 0;i < 2; i++){ cout<<endl; for(j = 0;j < 2; j++) cout<<y[i][j]<<” “; } m1 = (x[0][0] + x[1][1]) * (y[0][0] + y[1][1]); m2 = (x[1][0] + x[1][1]) * y[0][0]; m3 = x[0][0] * (y[0][1] – y[1][1]); m4 = x[1][1] * (y[1][0] – y[0][0]); m5 = (x[0][0] + x[0][1]) * y[1][1]; m6 = (x[1][0] – x[0][0]) * (y[0][0]+y[0][1]); m7 = (x[0][1] – x[1][1]) * (y[1][0]+y[1][1]); z[0][0] = m1 + m4- m5 + m7; z[0][1] = m3 + m5; z[1][0] = m2 + m4; z[1][1] = m1 – m2 + m3 + m6; cout<<“nProduct achieved using Strassen”s algorithm: “; for(i = 0; i < 2 ; i++) { cout<<endl; for(j = 0; j < 2; j++) cout<<z[i][j]<<” “; } return 0; } Output The first matrix is: 12 34 22 10 The second matrix is: 3 4 2 1 Product achieved using Strassen”s algorithm: 104 82 86 98 public class Strassens { public static void main(String[] args) { int[][] x = {{12, 34}, {22, 10}}; int[][] y = {{3, 4}, {2, 1}}; int z[][] = new int[2][2]; int m1, m2, m3, m4 , m5, m6, m7; System.out.print(“The first matrix is: “); for(int

Counting Sort Algorithm Table of content Counting Sort Algorithm Implementation ”; Previous Next Counting sort is an external sorting algorithm that assumes all the input values are integers that lie between the range 0 and k. Then mathematical computations on these input values to place them at the correct position in the output array. This algorithm makes use of a counter to count the frequency of occurrence of the numbers and arrange them accordingly. Suppose, if a number ‘m’ occurs 5 times in the input sequence, the counter value of the number will become 5 and it is repeated 5 times in the output array. Counting Sort Algorithm The counting sort algorithm assumes that the input is relatively smaller so the algorithm is as follows − Step 1 − Maintain two arrays, one with the size of input elements without repetition to store the count values and other with the size of the input array to store the output. Step 2 − Initialize the count array with all zeroes and keep the output array empty. Step 3 − Every time an element occurs in the input list, increment the corresponding counter value by 1, until it reaches the end of the input list. Step 4 − Now, in the output array, every time a counter is greater than 0, add the element at its respective index, i.e. if the counter of ‘0’ is 2, ‘0’ added at the 2nd position (i.e. 1st index) of the output array. Then decrement the counter value by 1. Step 5 − Repeat Step 4 until all the counter values become 0. The list obtained is the output list. COUNTING-SORT(A, B, k) let C[0 … k] be a new array for i = 0 to k C[i] = 0 for j = 1 to A.length C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i. for i = 1 to k C[i] = C[i] + C[i – 1] // C[i] now contains the number of elements less than or equal to i. for j = A.length downto 1 B[C[A[j]]] = A[j] C[A[j]] = C[A[j – 1] Analysis The average case time complexity for the counting sort algorithm is same as bucket sort. It runs in Θ(n) time. Example Consider an input list to be sorted, 0, 2, 1, 4, 6, 2, 1, 1, 0, 3, 7, 7, 9. For easier computations, let us start with single digit numbers. Step 1 Create two arrays: to store counters and the output. Initialize the counter array with zeroes. Step 2 After incrementing all the counter values until it reaches the end of the input list, we achieve − Step 3 Now, push the elements at the corresponding index in the output list. Step 4 Decrement the counter by 1 after adding the elements in the output array. Now, 1 is added at the 4th index. Step 5 Add the remaining values preceding the index in previous step. Step 6 After adding the last values, we get − The final sorted output is achieved as 0, 0, 1, 1, 1, 2, 2, 3, 4, 6, 7, 7, 9 Implementation The counting sort implementation works closely with the algorithm where we construct an array to store the frequency of each element of the input array. Based on these frequencies, the elements are placed in the output array. Repetitive elements are also sorted in the counting sort algorithm. Example In this chapter, we look into the counting sort program implemented in four different programming languages. C C++ Java Python #include<stdio.h> int countingsort(int a[], int n){ int i, j; int output[15], c[100]; for (i = 0; i < 100; i++) c[i] = 0; for (j = 0; j < n; j++) ++c[a[j]]; for (i = 1; i <= 99; i++) c[i] += c[i-1]; for (j = n-1; j >= 0; j–) { output[c[a[j]] – 1] = a[j]; –c[a[j]]; } printf(“nAfter sorting array elements are: “); for (i = 0; i<n; i++) printf(“%d “, output[i]); } void main(){ int n , i; int a[] = {12, 32, 44, 8, 16}; n = sizeof(a) / sizeof(a[0]); printf(“Before sorting array elements are: “); for(int i = 0; i<n; i++){ printf(“%d ” , a[i]); } countingsort(a, n); } Output Before sorting array elements are: 12 32 44 8 16 After sorting array elements are: 8 12 16 32 44 #include<iostream> using namespace std; void countingsort(int a[], int n){ int i, j; int output[15], c[100]; for (i = 0; i < 100; i++) c[i] = 0; for (j = 0; j < n; j++) ++c[a[j]]; for (i = 1; i <= 99; i++) c[i] += c[i-1]; for (j = n-1; j >= 0; j–) { output[c[a[j]] – 1] = a[j]; –c[a[j]]; } cout << “nAfter sorting array elements are: “; for (i = 0; i <n; i++) cout << output[i] << ” “; } int main(){ int n , i; int a[] = {12, 32, 44, 8, 16}; n = sizeof(a) / sizeof(a[0]); cout<<“Before sorting array elements are: “; for(int i = 0; i<n; i++){ cout<<a[i]<<” “; } countingsort(a, n); cout << “n”; return 0; } Output Before sorting array elements are: 12 32 44 8 16 After sorting array elements are: 8 12 16 32 44 import java.io.*; public class counting_sort { static void sort(int a[], int n) { int i, j; int output[] = new int[15]; int c[] = new int[100]; for (i = 0; i < 100; i++) c[i] = 0; for (j = 0; j < n;

Fibonacci Series Using Recursion Table of content Fibonacci Series Using Recursion Fibonacci Iterative Algorithm Fibonacci Recursive Algorithm Example ”; Previous Next Fibonacci Series Using Recursion Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively. Fibonacci series satisfies the following conditions − Fn = Fn-1 + Fn-2 Hence, a Fibonacci series can look like this − F8 = 0 1 1 2 3 5 8 13 or, this − F8 = 1 1 2 3 5 8 13 21 For illustration purpose, Fibonacci of F8 is displayed as − Fibonacci Iterative Algorithm First we try to draft the iterative algorithm for Fibonacci series. Procedure Fibonacci(n) declare f0, f1, fib, loop set f0 to 0 set f1 to 1 <b>display f0, f1</b> for loop ← 1 to n fib ← f0 &plus; f1 f0 ← f1 f1 ← fib <b>display fib</b> end for end procedure Fibonacci Recursive Algorithm Let us learn how to create a recursive algorithm Fibonacci series. The base criteria of recursion. START Procedure Fibonacci(n) declare f0, f1, fib, loop set f0 to 0 set f1 to 1 display f0, f1 for loop ← 1 to n fib ← f0 &plus; f1 f0 ← f1 f1 ← fib display fib end for END Example Following are the implementations of the above approach in various programming languages − C C++ Java Python #include <stdio.h> int fibbonacci(int n) { if(n == 0){ return 0; } else if(n == 1) { return 1; } else { return (fibbonacci(n-1) + fibbonacci(n-2)); } } int main() { int n = 5; printf(“Number is: %d”, n); printf(“nFibonacci series upto number %d are: “, n); for(int i = 0;i<n;i++) { printf(“%d “,fibbonacci(i)); } } Output Number is: 5 Fibonacci series upto number 5 are: 0 1 1 2 3 // C++ Code for Fibonacci series #include <iostream> using namespace std; int fibbonacci(int n) { if(n == 0){ return 0; } else if(n == 1) { return 1; } else { return (fibbonacci(n-1) + fibbonacci(n-2)); } } int main() { int n = 5; cout<<“Number is: “<<n; cout << “nFibbonacci series upto number “<<n<< ” are: “; for(int i = 0;i<n;i++) { cout << fibbonacci(i) << ” “; } } Output Number is: 5 Fibbonacci series upto number 5 are: 0 1 1 2 3 // Java Code for Fibonacci series public class Fibonacci { public static int fibonacci(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { return fibonacci(n – 1) + fibonacci(n – 2); } } public static void main(String[] args) { int n = 5; System.out.print(“Number is: ” + n); System.out.print(“nFibonacci series upto number ” + n + “: “); for (int i = 0; i < n; i++) { System.out.print(fibonacci(i) + ” “); } } } Output Number is: 5 Fibonacci series upto number 5: 0 1 1 2 3 #Python code for fibonacci Series def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) if __name__ == “__main__”: n = 5 print(“Number is “, n) print(“Fibonacci series upto number “,n, “are: “) for i in range(n): print(fibonacci(i) , end = ” “) Output Number is 5 Fibonacci series upto number 5 are: 0 1 1 2 3 Print Page Previous Next Advertisements ”;

Travelling Salesman Problem (Greedy Approach) Table of content Travelling Salesperson Algorithm Example ”; Previous Next The travelling salesman problem is a graph computational problem where the salesman needs to visit all cities (represented using nodes in a graph) in a list just once and the distances (represented using edges in the graph) between all these cities are known. The solution that is needed to be found for this problem is the shortest possible route in which the salesman visits all the cities and returns to the origin city. If you look at the graph below, considering that the salesman starts from the vertex ‘a’, they need to travel through all the remaining vertices b, c, d, e, f and get back to ‘a’ while making sure that the cost taken is minimum. There are various approaches to find the solution to the travelling salesman problem: naive approach, greedy approach, dynamic programming approach, etc. In this tutorial we will be learning about solving travelling salesman problem using greedy approach. Travelling Salesperson Algorithm As the definition for greedy approach states, we need to find the best optimal solution locally to figure out the global optimal solution. 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. The shortest path of graph G starting from one vertex returning to the same vertex is obtained as the output. Algorithm Travelling salesman problem takes a graph G {V, E} as an input and declare another graph as the output (say G’) which will record the path the salesman is going to take from one node to another. The algorithm begins by sorting all the edges in the input graph G from the least distance to the largest distance. The first edge selected is the edge with least distance, and one of the two vertices (say A and B) being the origin node (say A). Then among the adjacent edges of the node other than the origin node (B), find the least cost edge and add it onto the output graph. Continue the process with further nodes making sure there are no cycles in the output graph and the path reaches back to the origin node A. However, if the origin is mentioned in the given problem, then the solution must always start from that node only. Let us look at some example problems to understand this better. Examples Consider the following graph with six cities and the distances between them − From the given graph, since the origin is already mentioned, the solution must always start from that node. Among the edges leading from A, A → B has the shortest distance. Then, B → C has the shortest and only edge between, therefore it is included in the output graph. There’s only one edge between C → D, therefore it is added to the output graph. There’s two outward edges from D. Even though, D → B has lower distance than D → E, B is already visited once and it would form a cycle if added to the output graph. Therefore, D → E is added into the output graph. There’s only one edge from e, that is E → F. Therefore, it is added into the output graph. Again, even though F → C has lower distance than F → A, F → A is added into the output graph in order to avoid the cycle that would form and C is already visited once. The shortest path that originates and ends at A is A → B → C → D → E → F → A The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114. Even though, the cost of path could be decreased if it originates from other nodes but the question is not raised with respect to that. Example The complete implementation of Travelling Salesman Problem using Greedy Approach is given below − C C++ Java Python #include <stdio.h> int tsp_g[10][10] = { {12, 30, 33, 10, 45}, {56, 22, 9, 15, 18}, {29, 13, 8, 5, 12}, {33, 28, 16, 10, 3}, {1, 4, 30, 24, 20} }; int visited[10], n, cost = 0; /* creating a function to generate the shortest path */ void travellingsalesman(int c){ int k, adj_vertex = 999; int min = 999; /* marking the vertices visited in an assigned array */ visited[c] = 1; /* displaying the shortest path */ printf(“%d “, c + 1); /* checking the minimum cost edge in the graph */ for(k = 0; k < n; k++) { if((tsp_g[c][k] != 0) && (visited[k] == 0)) { if(tsp_g[c][k] < min) { min = tsp_g[c][k]; adj_vertex = k; } } } if(min != 999) { cost = cost + min; } if(adj_vertex == 999) { adj_vertex = 0; printf(“%d”, adj_vertex + 1); cost = cost + tsp_g[c][adj_vertex]; return; } travellingsalesman(adj_vertex); } /* main function */ int main(){ int i, j; n = 5; for(i = 0; i < n; i++) { visited[i] = 0; } printf(“Shortest Path: “); travellingsalesman(0); printf(“nMinimum Cost: “); printf(“%dn”, cost); return 0; } Output Shortest Path: 1 4 5 2 3 1 Minimum Cost: 55 #include <iostream> using namespace std; int tsp_g[10][10] = {{12, 30, 33, 10, 45}, {56, 22, 9, 15, 18}, {29, 13, 8, 5, 12}, {33, 28, 16, 10, 3}, {1, 4, 30, 24, 20} }; int visited[10], n, cost = 0; /* creating a function to generate the shortest path */ void travellingsalesman(int c){

Depth First Search (DFS) Algorithm ”; Previous Next Depth First Search (DFS) Algorithm Depth First Search (DFS) algorithm is a recursive algorithm for searching all the vertices of a graph or tree data structure. This algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration. As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F and lastly to C. It employs the following rules. Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack. Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.) Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty. Step Traversal Description 1 Initialize the stack. 2 Mark S as visited and put it onto the stack. Explore any unvisited adjacent node from S. We have three nodes and we can pick any of them. For this example, we shall take the node in an alphabetical order. 3 Mark A as visited and put it onto the stack. Explore any unvisited adjacent node from A. Both S and D are adjacent to A but we are concerned for unvisited nodes only. 4 Visit D and mark it as visited and put onto the stack. Here, we have B and C nodes, which are adjacent to D and both are unvisited. However, we shall again choose in an alphabetical order. 5 We choose B, mark it as visited and put onto the stack. Here B does not have any unvisited adjacent node. So, we pop B from the stack. 6 We check the stack top for return to the previous node and check if it has any unvisited nodes. Here, we find D to be on the top of the stack. 7 Only unvisited adjacent node is from D is C now. So we visit C, mark it as visited and put it onto the stack. As C does not have any unvisited adjacent node so we keep popping the stack until we find a node that has an unvisited adjacent node. In this case, there”s none and we keep popping until the stack is empty. Example Following are the implementations of Depth First Search (DFS) Algorithm in various programming languages − C C++ Java Python #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX 5 struct Vertex { char label; bool visited; }; //stack variables int stack[MAX]; int top = -1; //graph variables //array of vertices struct Vertex* lstVertices[MAX]; //adjacency matrix int adjMatrix[MAX][MAX]; //vertex count int vertexCount = 0; //stack functions void push(int item) { stack[++top] = item; } int pop() { return stack[top–]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //graph functions //add vertex to the vertex list void addVertex(char label) { struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex)); vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start,int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void displayVertex(int vertexIndex) { printf(“%c “,lstVertices[vertexIndex]->label); } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { int i; for(i = 0; i < vertexCount; i++) { if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) { return i; } } return -1; } void depthFirstSearch() { int i; //mark first node as visited lstVertices[0]->visited = true; //display the vertex displayVertex(0); //push vertex index in stack push(0); while(!isStackEmpty()) { //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(peek()); //no adjacent vertex found if(unvisitedVertex == -1) { pop(); } else { lstVertices[unvisitedVertex]->visited = true; displayVertex(unvisitedVertex); push(unvisitedVertex); } } //stack is empty, search is complete, reset the visited flag for(i = 0;i < vertexCount;i++) { lstVertices[i]->visited = false; } } int main() { int i, j; for(i = 0; i < MAX; i++) { // set adjacency for(j = 0; j < MAX; j++) // matrix to 0 adjMatrix[i][j] = 0; } addVertex(”S”); // 0 addVertex(”A”); // 1 addVertex(”B”); // 2 addVertex(”C”); // 3 addVertex(”D”); // 4 addEdge(0, 1); // S – A addEdge(0, 2); // S – B addEdge(0, 3); // S – C addEdge(1, 4); // A – D addEdge(2, 4); // B – D addEdge(3, 4); // C – D printf(“Depth First Search: “); depthFirstSearch(); return 0; } Output Depth First Search: S A D B C //C++ code for Depth First Traversal #include <iostream> #include <array> #include <vector> constexpr int MAX = 5; struct Vertex { char label; bool visited; }; //stack variables std::array<int, MAX> stack; int top = -1; //graph variables //array of vertices std::array<Vertex*, MAX> lstVertices; //adjacency matrix std::array<std::array<int, MAX>, MAX> adjMatrix; //vertex count int vertexCount = 0; //stack functions void push(int item) { stack[++top] = item; } int pop() { return stack[top–]; } int peek() { return stack[top]; } bool isStackEmpty() { return top == -1; } //graph functions //add vertex to the vertex list void addVertex(char label) { Vertex* vertex = new Vertex; vertex->label = label; vertex->visited = false; lstVertices[vertexCount++] = vertex; } //add edge to edge array void addEdge(int start, int end) { adjMatrix[start][end] = 1; adjMatrix[end][start] = 1; } //display the vertex void displayVertex(int vertexIndex) { std::cout << lstVertices[vertexIndex]->label << ” “; } //get the adjacent unvisited vertex int getAdjUnvisitedVertex(int vertexIndex) { for (int i = 0; i < vertexCount; i++) { if (adjMatrix[vertexIndex][i] == 1 && !lstVertices[i]->visited) { return i; } } return -1; } //mark first node as visited void depthFirstSearch() { lstVertices[0]->visited = true; //display the vertex displayVertex(0); //push vertex index in stack push(0); while (!isStackEmpty()) { //get the unvisited vertex of vertex which is at top of the stack int unvisitedVertex = getAdjUnvisitedVertex(peek()); //no adjacent

Dijkstra’s Shortest Path Algorithm Table of content Dijkstra’s Algorithm Example ”; Previous Next Dijkstra’s shortest path algorithm is similar to that of Prim’s algorithm as they both rely on finding the shortest path locally to achieve the global solution. However, unlike prim’s algorithm, the dijkstra’s algorithm does not find the minimum spanning tree; it is designed to find the shortest path in the graph from one vertex to other remaining vertices in the graph. Dijkstra’s algorithm can be performed on both directed and undirected graphs. Since the shortest path can be calculated from single source vertex to all the other vertices in the graph, Dijkstra’s algorithm is also called single-source shortest path algorithm. The output obtained is called shortest path spanning tree. In this chapter, we will learn about the greedy approach of the dijkstra’s algorithm. Dijkstra’s Algorithm The dijkstra’s algorithm is designed to find the shortest path between two vertices of a graph. These two vertices could either be adjacent or the farthest points in the graph. The algorithm starts from the source. 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. And the output is the shortest path spanning tree. Algorithm Declare two arrays − distance[] to store the distances from the source vertex to the other vertices in graph and visited[] to store the visited vertices. Set distance[S] to ‘0’ and distance[v] = ∞, where v represents all the other vertices in the graph. Add S to the visited[] array and find the adjacent vertices of S with the minimum distance. The adjacent vertex to S, say A, has the minimum distance and is not in the visited array yet. A is picked and added to the visited array and the distance of A is changed from ∞ to the assigned distance of A, say d1, where d1 < ∞. Repeat the process for the adjacent vertices of the visited vertices until the shortest path spanning tree is formed. Examples To understand the dijkstra’s concept better, let us analyze the algorithm with the help of an example graph − Step 1 Initialize the distances of all the vertices as ∞, except the source node S. Vertex S A B C D E Distance 0 ∞ ∞ ∞ ∞ ∞ Now that the source vertex S is visited, add it into the visited array. visited = {S} Step 2 The vertex S has three adjacent vertices with various distances and the vertex with minimum distance among them all is A. Hence, A is visited and the dist[A] is changed from ∞ to 6. S → A = 6 S → D = 8 S → E = 7 Vertex S A B C D E Distance 0 6 ∞ ∞ 8 7 Visited = {S, A} Step 3 There are two vertices visited in the visited array, therefore, the adjacent vertices must be checked for both the visited vertices. Vertex S has two more adjacent vertices to be visited yet: D and E. Vertex A has one adjacent vertex B. Calculate the distances from S to D, E, B and select the minimum distance − S → D = 8 and S → E = 7. S → B = S → A + A → B = 6 + 9 = 15 Vertex S A B C D E Distance 0 6 15 ∞ 8 7 Visited = {S, A, E} Step 4 Calculate the distances of the adjacent vertices – S, A, E – of all the visited arrays and select the vertex with minimum distance. S → D = 8 S → B = 15 S → C = S → E + E → C = 7 + 5 = 12 Vertex S A B C D E Distance 0 6 15 12 8 7 Visited = {S, A, E, D} Step 5 Recalculate the distances of unvisited vertices and if the distances minimum than existing distance is found, replace the value in the distance array. S → C = S → E + E → C = 7 + 5 = 12 S → C = S → D + D → C = 8 + 3 = 11 dist[C] = minimum (12, 11) = 11 S → B = S → A + A → B = 6 + 9 = 15 S → B = S → D + D → C + C → B = 8 + 3 + 12 = 23 dist[B] = minimum (15,23) = 15 Vertex S A B C D E Distance 0 6 15 11 8 7 Visited = { S, A, E, D, C} Step 6 The remaining unvisited vertex in the graph is B with the minimum distance 15, is added to the output spanning tree.

B Trees Table of content Basic Operations of B Trees Insertion operation Deletion operation ”; Previous Next B trees are extended binary search trees that are specialized in m-way searching, since the order of B trees is ”m”. Order of a tree is defined as the maximum number of children a node can accommodate. Therefore, the height of a b tree is relatively smaller than the height of AVL tree and RB tree. They are general form of a Binary Search Tree as it holds more than one key and two children. The various properties of B trees include − Every node in a B Tree will hold a maximum of m children and (m-1) keys, since the order of the tree is m. Every node in a B tree, except root and leaf, can hold at least m/2 children The root node must have no less than two children. 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. B trees are also widely used in disk access, minimizing the disk access time since the height of a b tree is low. Note − A disk access is the memory access to the computer disk where the information is stored and disk access time is the time taken by the system to access the disk memory. 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. Insertion operation The insertion operation for a B Tree is done similar to the Binary Search Tree but the elements are inserted into the same node until the maximum keys are reached. The insertion is done using the following procedure − Step 1 − Calculate the maximum $mathrm{left ( m-1 right )}$ and, minimum $mathrm{left ( left lceil frac{m}{2}right rceil-1 right )}$ number of keys a node can hold, where m is denoted by the order of the B Tree. Step 2 − The data is inserted into the tree using the binary search insertion and once the keys reach the maximum number, the node is split into half and the median key becomes the internal node while the left and right keys become its children. Step 3 − All the leaf nodes must be on the same level. The keys, 5, 3, 21, 9, 13 are all added into the node according to the binary search property but if we add the key 22, it will violate the maximum key property. Hence, the node is split in half, the median key is shifted to the parent node and the insertion is then continued. Another hiccup occurs during the insertion of 11, so the node is split and median is shifted to the parent. While inserting 16, even if the node is split in two parts, the parent node also overflows as it reached the maximum keys. Hence, the parent node is split first and the median key becomes the root. Then, the leaf node is split in half the median of leaf node is shifted to its parent. The final B tree after inserting all the elements is achieved. Example Following are the implementations of this operation in various programming languages − C C++ Java Python // C Program for B trees #include <stdio.h> #include <stdlib.h> struct BTree { //node declaration int *d; struct BTree **child_ptr; int l; int n; }; struct BTree *r = NULL; struct BTree *np = NULL; struct BTree *x = NULL; //creation of node struct BTree* init() { int i; np = (struct BTree*)malloc(sizeof(struct BTree)); //order 6 np->d = (int*)malloc(6 * sizeof(int)); np->child_ptr = (struct BTree**)malloc(7 * sizeof(struct BTree*)); np->l = 1; np->n = 0; for (i = 0; i < 7; i++) { np->child_ptr[i] = NULL; } return np; } //traverse the tree void traverse(struct BTree *p) { 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”); } //sort the tree 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 BTree *x, int i) { int j, mid; struct BTree *np1, *np3, *y; np3 = init(); //create new node np3->l = 1; if (i == -1) { mid = x->d[2]; //find mid 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