Category: data Structures Algorithms

Jump Search Algorithm Table of content Jump Search Algorithm Implementation ”; Previous Next Jump Search algorithm is a slightly modified version of the linear search algorithm. The main idea behind this algorithm is to reduce the time complexity by comparing lesser elements than the linear search algorithm. The input array is hence sorted and divided into blocks to perform searching while jumping through these blocks. For example, let us look at the given example below; the sorted input array is searched in the blocks of 3 elements each. The desired key is found only after 2 comparisons rather than the 6 comparisons of the linear search. Here, there arises a question about how to divide these blocks. To answer that, if the input array is of size ‘n’, the blocks are divided in the intervals of √n. First element of every block is compared with the key element until the key element’s value is less than the block element. Linear search is performed only on that previous block since the input is sorted. If the element is found, it is a successful search; otherwise, an unsuccessful search is returned. Jump search algorithm is discussed in detail further into this chapter. Jump Search Algorithm The jump search algorithm takes a sorted array as an input which is divided into smaller blocks to make the search simpler. The algorithm is as follows − Step 1 − If the size of the input array is ‘n’, then the size of the block is √n. Set i = 0. Step 2 − The key to be searched is compared with the ith element of the array. If it is a match, the position of the element is returned; otherwise i is incremented with the block size. Step 3 − The Step 2 is repeated until the ith element is greater than the key element. Step 4 − Now, the element is figured to be in the previous block, since the input array is sorted. Therefore, linear search is applied on that block to find the element. Step 5 − If the element is found, the position is returned. If the element is not found, unsuccessful search is prompted. Pseudocode Begin blockSize := √size start := 0 end := blockSize while array[end] <= key AND end < size do start := end end := end + blockSize if end > size – 1 then end := size done for i := start to end -1 do if array[i] = key then return i done return invalid location End Analysis The time complexity of the jump search technique is O(√n) and space complexity is O(1). Example Let us understand the jump search algorithm by searching for element 66 from the given sorted array, A, below − Step 1 Initialize i = 0, and size of the input array ‘n’ = 12 Suppose, block size is represented as ‘m’. Then, m = √n = √12 = 3 Step 2 Compare A[0] with the key element and check whether it matches, A[0] = 0 ≠ 66 Therefore, i is incremented by the block size = 3. Now the element compared with the key element is A[3]. Step 3 A[3] = 14 ≠ 66 Since it is not a match, i is again incremented by 3. Step 4 A[6] = 48 ≠ 66 i is incremented by 3 again. A[9] is compared with the key element. Step 5 A[9] = 88 ≠ 66 However, 88 is greater than 66, therefore linear search is applied on the current block. Step 6 After applying linear search, the pointer increments from 6th index to 7th. Therefore, A[7] is compared with the key element. We find that A[7] is the required element, hence the program returns 7th index as the output. Implementation The jump search algorithm is an extended variant of linear search. The algorithm divides the input array into multiple small blocks and performs the linear search on a single block that is assumed to contain the element. If the element is not found in the assumed blocked, it returns an unsuccessful search. The output prints the position of the element in the array instead of its index. Indexing refers to the index numbers of the array that start from 0 while position is the place where the element is stored. C C++ Java Python #include<stdio.h> #include<math.h> int jump_search(int[], int, int); int main(){ int i, n, key, index; int arr[12] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126}; int len = sizeof(arr)/sizeof(arr[0]); printf(“Array elements are:”); for(int j = 0; j<len; j++){ printf(” %d”, arr[j]); } n = 12; key = 66; printf(“nThe element to be searched: %dn”, key); index = jump_search(arr, n, key); if(index >= 0) printf(“The element is found at position %d”, index+1); else printf(“Unsuccessful Search”); return 0; } int jump_search(int arr[], int n, int key){ int i, j, m, k; i = 0; m = sqrt(n); k = m; while(arr[m] <= key && m < n) { i = m; m += k; if(m > n – 1) return -1; } // linear search on the block for(j = i; j<m; j++) { if(arr[j] == key) return j; } return -1; } Output Array elements are: 0 6 12 14 19 22 48 66 79 88 104 126 The element to be searched: 66 The element is found at position 8 #include<iostream> #include<cmath> using namespace std; int jump_search(int[], int, int); int main(){ int i, n, key, index; int arr[12] = {0, 6, 12,

Kruskal’s Minimal Spanning Tree Algorithm Table of content Kruskal”s Algorithm Example ”; Previous Next Kruskal”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 subgraph 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 first starts from the forest – which is defined as a subgraph containing only vertices of the main graph – of the graph, adding the least cost edges later until the minimum spanning tree is created without forming cycles in the graph. Kruskal”s algorithm has easier implementation than prim’s algorithm, but has higher complexity. Kruskal”s Algorithm The inputs taken by the kruskal’s 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 minimum spanning tree of graph G is obtained as an output. Algorithm Sort all the edges in the graph in an ascending order and store it in an array edge[]. Construct the forest of the graph on a plane with all the vertices in it. Select the least cost edge from the edge[] array and add it into the forest of the graph. Mark the vertices visited by adding them into the visited[] array. Repeat the steps 2 and 3 until all the vertices are visited without having any cycles forming in the graph When all the vertices are visited, the minimum spanning tree is formed. Calculate the minimum cost of the output spanning tree formed. Examples Construct a minimum spanning tree using kruskal’s algorithm for the graph given below − Solution As the first step, sort all the edges in the given graph in an ascending order and store the values in an array. Edge B→D A→B C→F F→E B→C G→F A→G C→D D→E C→G Cost 5 6 9 10 11 12 15 17 22 25 Then, construct a forest of the given graph on a single plane. From the list of sorted edge costs, select the least cost edge and add it onto the forest in output graph. B → D = 5 Minimum cost = 5 Visited array, v = {B, D} Similarly, the next least cost edge is B → A = 6; so we add it onto the output graph. Minimum cost = 5 + 6 = 11 Visited array, v = {B, D, A} The next least cost edge is C → F = 9; add it onto the output graph. Minimum Cost = 5 + 6 + 9 = 20 Visited array, v = {B, D, A, C, F} The next edge to be added onto the output graph is F → E = 10. Minimum Cost = 5 + 6 + 9 + 10 = 30 Visited array, v = {B, D, A, C, F, E} The next edge from the least cost array is B → C = 11, hence we add it in the output graph. Minimum cost = 5 + 6 + 9 + 10 + 11 = 41 Visited array, v = {B, D, A, C, F, E} The last edge from the least cost array to be added in the output graph is F → G = 12. Minimum cost = 5 + 6 + 9 + 10 + 11 + 12 = 53 Visited array, v = {B, D, A, C, F, E, G} The obtained result is the minimum spanning tree of the given graph with cost = 53. Example The final program implements the Kruskal’s minimum spanning tree problem that takes the cost adjacency matrix as the input and prints the shortest path as the output along with the minimum cost. C C++ Java Python #include <stdio.h> #include <stdlib.h> const int inf = 999999; int k, a, b, u, v, n, ne = 1; int mincost = 0; int cost[3][3] = {{0, 10, 20},{12, 0,15},{16, 18, 0}}; int p[9] = {0}; int applyfind(int i) { while(p[i] != 0) i=p[i]; return i; } int applyunion(int i,int j) { if(i!=j) { p[j]=i; return 1; } return 0; } int main() { n = 3; int i, j; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (cost[i][j] == 0) { cost[i][j] = inf; } } } printf(“Minimum Cost Spanning Tree: n”); while(ne < n) { int min_val = inf; for(i=0; i<n; i++) { for(j=0; j <n; j++) { if(cost[i][j] < min_val) { min_val = cost[i][j]; a = u = i; b = v = j; } } } u = applyfind(u); v = applyfind(v); if(applyunion(u, v) != 0) { printf(“%d -> %dn”, a, b); mincost +=min_val; } cost[a][b] = cost[b][a] = 999; ne++; } printf(“Minimum cost = %d”,mincost); return 0; } Output Minimum Cost Spanning Tree: 0 -> 1 1 -> 2 Minimum cost = 25 #include <iostream> using namespace std; const int inf = 999999; int k, a, b, u, v, n, ne = 1; int mincost = 0; int cost[3][3] = {{0, 10, 20}, {12, 0, 15}, {16, 18, 0}}; int p[9] = {0}; int applyfind(int i) { while (p[i] != 0) { i = p[i]; } return i; } int applyunion(int i, int j) { if

Data Structure Basics ”; Previous Next This tutorial explains the basic terms related to data structure. Data Definition Data Definition defines a particular data with the following characteristics. Atomic − Definition should define a single concept. Traceable − Definition should be able to be mapped to some data element. Accurate − Definition should be unambiguous. Clear and Concise − Definition should be understandable. Data Object Data Object represents an object having a data. Data Type Data type is a way to classify various types of data such as integer, string, etc. which determines the values that can be used with the corresponding type of data, the type of operations that can be performed on the corresponding type of data. There are two data types − Built-in Data Type Derived Data Type Built-in Data Type Those data types for which a language has built-in support are known as Built-in Data types. For example, most of the languages provide the following built-in data types. Integers Boolean (true, false) Floating (Decimal numbers) Character and Strings Derived Data Type Those data types which are implementation independent as they can be implemented in one or the other way are known as derived data types. These data types are normally built by the combination of primary or built-in data types and associated operations on them. For example − List Array Stack Queue Basic Operations The data in the data structures are processed by certain operations. The particular data structure chosen largely depends on the frequency of the operation that needs to be performed on the data structure. Traversing Searching Insertion Deletion Sorting Merging Print Page Previous Next Advertisements ”;

Recursion Algorithms Table of content Recursion Properties Implementation Analysis of Recursion Time Complexity Space Complexity Example ”; Previous Next Recursion Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function. Example − a function calling itself. int function(int value) { if(value < 1) return; function(value – 1); printf(“%d “,value); } Example − a function that calls another function which in turn calls it again. int function1(int value1) { if(value1 < 1) return; function2(value1 – 1); printf(“%d “,value1); } int function2(int value2) { function1(value2); } Properties A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have − Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively. Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria. Implementation Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee. This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function. This activation record keeps the information about local variables, formal parameters, return address and all information passed to the caller function. Analysis of Recursion One may argue why to use recursion, as the same task can be done with iteration. The first reason is, recursion makes a program more readable and because of latest enhanced CPU systems, recursion is more efficient than iterations. Time Complexity In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n). Space Complexity Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation record each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration. Example Following are the implementations of the recursion in various programming languages − C C++ Java Python // C program for Recursion Data Structure #include <stdio.h> int factorial(int n) { // Base case: factorial of 0 is 1 if (n == 0) return 1; // Recursive case: multiply n with factorial of (n-1) return n * factorial(n – 1); } int main() { // case 1 int number = 6; printf(“Number is: %dn” , 6); //case 2 if (number < 0) { printf(“Error: Factorial is undefined for negative numbers.n”); return 1; } int result = factorial(number); //print the output printf(“Factorial of %d is: %dn”, number, result); return 0; } Output Number is: 6 Factorial of 6 is: 720 // CPP program for Recursion Data Structure #include <iostream> int factorial(int n) { // Base case: factorial of 0 is 1 if (n == 0) return 1; // Recursive case: multiply n with factorial of (n-1) return n * factorial(n – 1); } int main() { // case 1 int number = 6; std::cout<<“Number is: “<<number<<“n”; //case 2 if (number < 0) { std::cout << “Error: Factorial is undefined for negative numbers.n”; return 1; } int result = factorial(number); //print the output std::cout << “Factorial of ” << number << ” is: ” << result << std::endl; return 0; } Output Number is: 6 Factorial of 6 is: 720 // Java program for Recursion Data Structure import java.util.Scanner; public class Main { public static int factorial(int n) { // Base case: factorial of 0 is 1 if (n == 0) return 1; // Recursive case: multiply n with factorial of (n-1) return n * factorial(n – 1); } public static void main(String[] args) { //Case 1 int number = 6; System.out.println(“Number is: ” + number); //Case 2 if (number < 0) { System.out.println(“Error: Factorial is undefined for negative numbers.”); System.exit(1); } int result = factorial(number); //print the output System.out.println(“Factorial of ” + number + ” is: ” + result); } } Output Number is: 6 Factorial of 6 is: 720 # Python program for Recursion Data Structure def factorial(n): #Base Case: factorial of 0 is 1 if n == 0: return 1 # Recursive case: multiply n with factorial of (n-1) return n * factorial(n – 1) #Case 1: number = 6; print(“Number is: “, number); #Case 2: if number < 0: print(“Error: Factorial is undefined for negative numbers.”) else: result = factorial(number) # print the output print(“Factorial of”, number, “is: “, result) Output Number is: 6 Factorial of 6 is: 720 Print Page Previous Next Advertisements ”;

Data Structures – Searching Algorithms Table of content Searching Algorithms in Data Structures Evaluating Searching Algorithms ”; Previous Next In the previous section, we have discussed various Sorting Techniques and cases in which they can be used. However, the main idea behind performing sorting is to arrange the data in an orderly way, making it easier to search for any element within the sorted data. Searching is a process of finding a particular record, which can be a single element or a small chunk, within a huge amount of data. The data can be in various forms: arrays, linked lists, trees, heaps, and graphs etc. With the increasing amount of data nowadays, there are multiple techniques to perform the searching operation. Searching Algorithms in Data Structures Various searching techniques can be applied on the data structures to retrieve certain data. A search operation is said to be successful only if it returns the desired element or data; otherwise, the searching method is unsuccessful. There are two categories these searching techniques fall into. They are − Sequential Searching Interval Searching Sequential Searching As the name suggests, the sequential searching operation traverses through each element of the data sequentially to look for the desired data. The data need not be in a sorted manner for this type of search. Example − Linear Search Fig. 1: Linear Search Operation Interval Searching Unlike sequential searching, the interval searching operation requires the data to be in a sorted manner. This method usually searches the data in intervals; it could be done by either dividing the data into multiple sub-parts or jumping through the indices to search for an element. Example − Binary Search, Jump Search etc. Fig. 2: Binary Search Operation Evaluating Searching Algorithms Usually, not all searching techniques are suitable for all types of data structures. In some cases, a sequential search is preferable while in other cases interval searching is preferable. Evaluation of these searching techniques is done by checking the running time taken by each searching method on a particular input. This is where asymptotic notations come into the picture. To learn more about Asymptotic Notations, please click here. To explain briefly, there are three different cases of time complexity in which a program can run. They are − Best Case Average Case Worst Case We mostly concentrate on the only best-case and worst-case time complexities, as the average case is difficult to compute. And since the running time is based on the amount of input given to the program, the worst-case time complexity best describes the performance of any algorithm. For instance, the best case time complexity of a linear search is O(1) where the desired element is found in the first iteration; whereas the worst case time complexity is O(n) when the program traverses through all the elements and still does not find an element. This is labelled as an unsuccessful search. Therefore, the actual time complexity of a linear search is seen as O(n), where n is the number of elements present in the input data structure. Many types of searching methods are used to search for data entries in various data structures. Some of them include − Linear Search Binary Search Interpolation Search Jump Search Hash Table Exponential Search Sublist search Fibonacci Search Ubiquitous Binary Search We will look at each of these searching methods elaborately in the following chapters. Print Page Previous Next Advertisements ”;

Tries Data Structure Table of content Basic Operations in Trie Insertion operation Deletion operation Search operation ”; Previous Next A trie is a type of a multi-way search tree, which is fundamentally used to retrieve specific keys from a string or a set of strings. It stores the data in an ordered efficient way since it uses pointers to every letter within the alphabet. The trie data structure works based on the common prefixes of strings. The root node can have any number of nodes considering the amount of strings present in the set. The root of a trie does not contain any value except the pointers to its child nodes. There are three types of trie data structures − Standard Tries Compressed Tries Suffix Tries The real-world applications of trie include − autocorrect, text prediction, sentiment analysis and data sciences. Basic Operations in Tries The trie data structures also perform the same operations that tree data structures perform. They are − Insertion Deletion Search Insertion operation The insertion operation in a trie is a simple approach. The root in a trie does not hold any value and the insertion starts from the immediate child nodes of the root, which act like a key to their child nodes. However, we observe that each node in a trie represents a singlecharacter in the input string. Hence the characters are added into the tries one by one while the links in the trie act as pointers to the next level nodes. Example Following are the implementations of this operation in various programming languages − C C++ Java Python #include <stdio.h> #include <stdlib.h> #include <string.h> #define ALPHABET_SIZE 26 struct TrieNode { struct TrieNode* children[ALPHABET_SIZE]; int isEndOfWord; }; struct Trie { struct TrieNode* root; }; struct TrieNode* createNode() { struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode)); node->isEndOfWord = 0; for (int i = 0; i < ALPHABET_SIZE; i++) { node->children[i] = NULL; } return node; } void insert(struct Trie* trie, const char* key) { struct TrieNode* curr = trie->root; for (int i = 0; i < strlen(key); i++) { int index = key[i] – ”a”; if (curr->children[index] == NULL) { curr->children[index] = createNode(); } curr = curr->children[index]; } curr->isEndOfWord = 1; } void printWords(struct TrieNode* node, char* prefix) { if (node->isEndOfWord) { printf(“%sn”, prefix); } for (int i = 0; i < ALPHABET_SIZE; i++) { if (node->children[i] != NULL) { char* newPrefix = (char*)malloc(strlen(prefix) + 2); strcpy(newPrefix, prefix); newPrefix[strlen(prefix)] = ”A” + i; newPrefix[strlen(prefix) + 1] = ””; printWords(node->children[i], newPrefix); free(newPrefix); } } } int main() { struct Trie car; car.root = createNode(); insert(&car, “lamborghini”); insert(&car, “mercedes-Benz”); insert(&car, “land Rover”); insert(&car, “maruti Suzuki”); printf(“Trie elements are:n”); printWords(car.root, “”); return 0; } Output Trie elements are: LAMBORGHINI LANDNOVER MARUTIOUZUKI MERCEZENZ #include <iostream> #include <unordered_map> #include <string> class TrieNode { public: std::unordered_map<char, TrieNode*> children; bool isEndOfWord; TrieNode() { isEndOfWord = false; } }; class Trie { private: TrieNode* root; public: Trie() { root = new TrieNode(); } void insert(std::string word) { TrieNode* curr = root; for (char ch : word) { if (curr->children.find(ch) == curr->children.end()) { curr->children[ch] = new TrieNode(); } curr = curr->children[ch]; } curr->isEndOfWord = true; } TrieNode* getRoot() { return root; } }; void printWords(TrieNode* node, std::string prefix) { if (node->isEndOfWord) { std::cout << prefix << std::endl; } for (auto entry : node->children) { printWords(entry.second, prefix + entry.first); } } int main() { Trie car; car.insert(“Lamborghini”); car.insert(“Mercedes-Benz”); car.insert(“Land Rover”); car.insert(“Maruti Suzuki”); std::cout << “Tries elements are: ” << std::endl; printWords(car.getRoot(), “”); return 0; } Output Tries elements are: Maruti Suzuki Mercedes-Benz Land Rover Lamborghini import java.util.HashMap; import java.util.Map; class TrieNode { Map<Character, TrieNode> children; boolean isEndOfWord; TrieNode() { children = new HashMap<>(); isEndOfWord = false; } } class Trie { private TrieNode root; Trie() { root = new TrieNode(); } void insert(String word) { TrieNode curr = root; for (char ch : word.toCharArray()) { curr.children.putIfAbsent(ch, new TrieNode()); curr = curr.children.get(ch); } curr.isEndOfWord = true; } TrieNode getRoot() { return root; } } public class Main { public static void printWords(TrieNode node, String prefix) { if (node.isEndOfWord) { System.out.println(prefix); } for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) { printWords(entry.getValue(), prefix + entry.getKey()); } } public static void main(String[] args) { Trie car = new Trie(); // Inserting the elements car.insert(“Lamborghini”); car.insert(“Mercedes-Benz”); car.insert(“Land Rover”); car.insert(“Maruti Suzuki”); // Print the inserted objects System.out.print(“Tries elements are: n”); printWords(car.getRoot(), “”); // Access root using the public method } } Output Tries elements are: Lamborghini Land Rover Maruti Suzuki Mercedes-Benz class TrieNode: def __init__(self): self.children = {} self.isEndOfWord = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): curr = self.root for ch in word: curr.children.setdefault(ch, TrieNode()) curr = curr.children[ch] curr.isEndOfWord = True def getRoot(self): return self.root def printWords(node, prefix): if node.isEndOfWord: print(prefix) for ch, child in node.children.items(): printWords(child, prefix + ch) if __name__ == ”__main__”: car = Trie() # Inserting the elements car.insert(“Lamborghini”) car.insert(“Mercedes-Benz”) car.insert(“Land Rover”) car.insert(“Maruti Suzuki”) # Print the inserted objects print(“Tries elements are: “) printWords(car.getRoot(), “”) Output Tries elements are: Lamborghini Land Rover Mercedes-Benz Maruti Suzuki Deletion operation The deletion operation in a trie is performed using the bottom-up approach. The element is searched for in a trie and deleted, if found. However, there are some special scenarios that need to be kept in mind while performing the deletion operation. Case 1 − The key is unique − in this case, the entire key path is deleted from the node. (Unique key suggests that there is no other path that branches out from one path). Case 2 − The

Divide & Conquer Algorithm Table of content Arrays as Input Linked Lists as Input Pros and cons of Divide and Conquer Approach Examples of Divide and Conquer Approach ”; Previous Next Using divide and conquer approach, the problem in hand, is divided into smaller sub-problems and then each problem is solved independently. When we keep dividing the sub-problems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those smallest possible sub-problems are solved using original solution because it takes lesser time to compute. The solution of all sub-problems is finally merged in order to obtain the solution of the original problem. Broadly, we can understand divide-and-conquer approach in a three-step process. Divide/Break This step involves breaking the problem into smaller sub-problems. Sub-problems should represent a part of the original problem. This step generally takes a recursive approach to divide the problem until no sub-problem is further divisible. At this stage, sub-problems become atomic in size but still represent some part of the actual problem. Conquer/Solve This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered ”solved” on their own. Merge/Combine When the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem. This algorithmic approach works recursively and conquer & merge steps works so close that they appear as one. Arrays as Input There are various ways in which various algorithms can take input such that they can be solved using the divide and conquer technique. Arrays are one of them. In algorithms that require input to be in the form of a list, like various sorting algorithms, array data structures are most commonly used. In the input for a sorting algorithm below, the array input is divided into subproblems until they cannot be divided further. Then, the subproblems are sorted (the conquer step) and are merged to form the solution of the original array back (the combine step). Since arrays are indexed and linear data structures, sorting algorithms most popularly use array data structures to receive input. Linked Lists as Input Another data structure that can be used to take input for divide and conquer algorithms is a linked list (for example, merge sort using linked lists). Like arrays, linked lists are also linear data structures that store data sequentially. Consider the merge sort algorithm on linked list; following the very popular tortoise and hare algorithm, the list is divided until it cannot be divided further. Then, the nodes in the list are sorted (conquered). These nodes are then combined (or merged) in recursively until the final solution is achieved. Various searching algorithms can also be performed on the linked list data structures with a slightly different technique as linked lists are not indexed linear data structures. They must be handled using the pointers available in the nodes of the list. Pros and cons of Divide and Conquer Approach Divide and conquer approach supports parallelism as sub-problems are independent. Hence, an algorithm, which is designed using this technique, can run on the multiprocessor system or in different machines simultaneously. In this approach, most of the algorithms are designed using recursion, hence memory management is very high. For recursive function stack is used, where function state needs to be stored. Examples of Divide and Conquer Approach The following computer algorithms are based on divide-and-conquer programming approach − Max-Min Problem Merge Sort Algorithm Quick Sort Algorithm Binary Search Algorithm Strassen”s Matrix Multiplication Karatsuba Algorithm Closest pair (points) There are various ways available to solve any computer problem, but the mentioned are a good example of divide and conquer approach. Print Page Previous Next Advertisements ”;

Data Structures & Algorithms – Environment Setup ”; Previous Next Online Editor & Compiler We have setup an online environment for you to compile and run your data Structure and Algorithms programs in four different programming languages: C, C++, Java, Python. C C++ Java Python #include <stdio.h> int main(){ int LA[3] = {}, i; for(i = 0; i < 3; i++) { LA[i] = i + 2; printf(“LA[%d] = %d n”, i, LA[i]); } return 0; } #include <iostream> using namespace std; int main(){ int LA[3] = {}, i; cout << “Array:” << endl; for(i = 0; i < 5; i++) { LA[i] = i + 2; cout << “LA[” << i <<“] = ” << LA[i] << endl; } return 0; } public class ArrayDemo { public static void main(String []args) { int LA[] = new int[3]; System.out.println(“Array:”); for(int i = 0; i < 3; i++) { LA[i] = i+3; System.out.println(“LA[” + i + “] = ” + LA[i]); } } } LA = [0, 0, 0] x = 0 print(“Array: “) for x in range(len(LA)): LA[x] = x+1; print(“LA”, [x], ” = ” , LA[x]) Local Environment Setup If you are still willing to set up your own environment for C programming language, you need the following two tools available on your computer, (a) Text Editor and (b) The C Compiler. Text Editor This will be used to type your program. Examples of few editors include Windows Notepad, OS Edit command, Brief, Epsilon, EMACS, and vim or vi. The name and the version of the text editor can vary on different operating systems. For example, Notepad will be used on Windows, and vim or vi can be used on Windows as well as Linux or UNIX. The files you create with your editor are called source files and contain program source code. The source files for C programs are typically named with the extension “.c“. Before starting your programming, make sure you have one text editor in place and you have enough experience to write a computer program, save it in a file, compile it, and finally execute it. The C Compiler The source code written in the source file is the human readable source for your program. It needs to be “compiled”, to turn into machine language so that your CPU can actually execute the program as per the given instructions. This C programming language compiler will be used to compile your source code into a final executable program. We assume you have the basic knowledge about a programming language compiler. Most frequently used and free available compiler is GNU C/C&plus;&plus; compiler. Otherwise, you can have compilers either from HP or Solaris if you have respective Operating Systems (OS). The following section guides you on how to install GNU C/C&plus;&plus; compiler on various OS. We are mentioning C/C&plus;&plus; together because GNU GCC compiler works for both C and C&plus;&plus; programming languages. Installation on UNIX/Linux If you are using Linux or UNIX, then check whether GCC is installed on your system by entering the following command from the command line − $ gcc -v If you have GNU compiler installed on your machine, then it should print a message such as the following − Using built-in specs. Target: i386-redhat-linux Configured with: ../configure –prefix = /usr ……. Thread model: posix gcc version 4.1.2 20080704 (Red Hat 4.1.2-46) If GCC is not installed, then you will have to install it yourself using the detailed instructions available at https://gcc.gnu.org/install/ This tutorial has been written based on Linux and all the given examples have been compiled on Cent OS flavor of Linux system. Installation on Mac OS If you use Mac OS X, the easiest way to obtain GCC is to download the Xcode development environment from Apple”s website and follow the simple installation instructions. Once you have Xcode setup, you will be able to use GNU compiler for C/C&plus;&plus;. Xcode is currently available at developer.apple.com/technologies/tools/ Installation on Windows To install GCC on Windows, you need to install MinGW. To install MinGW, go to the MinGW homepage, www.mingw.org, and follow the link to the MinGW download page. Download the latest version of the MinGW installation program, which should be named MinGW-<version>.exe. While installing MinWG, at a minimum, you must install gcc-core, gcc-g&plus;&plus;, binutils, and the MinGW runtime, but you may wish to install more. Add the bin subdirectory of your MinGW installation to your PATH environment variable, so that you can specify these tools on the command line by their simple names. When the installation is complete, you will be able to run gcc, g&plus;&plus;, ar, ranlib, dlltool, and several other GNU tools from the Windows command line. Print Page Previous Next Advertisements ”;

Stack Data Structure ”; Previous Next What is a Stack? A stack is a linear data structure where elements are stored in the LIFO (Last In First Out) principle where the last element inserted would be the first element to be deleted. A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages. It is named stack because it has the similar operations as the real-world stacks, for example − a pack of cards or a pile of plates, etc. Stack is considered a complex data structure because it uses other data structures for implementation, such as Arrays, Linked lists, etc. Stack Representation A stack allows all data operations at one end only. At any given time, we can only access the top element of a stack. The following diagram depicts a stack and its operations − A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation. Basic Operations on Stacks Stack operations are usually performed for initialization, usage and, de-initialization of the stack ADT. The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(), isEmpty(). These are all built-in operations to carry out data manipulation and to check the status of the stack. Stack uses pointers that always point to the topmost element within the stack, hence called as the top pointer. Stack Insertion: push() The push() is an operation that inserts elements into the stack. The following is an algorithm that describes the push() operation in a simpler way. Algorithm 1. Checks if the stack is full. 2. If the stack is full, produces an error and exit. 3. If the stack is not full, increments top to point next empty space. 4. Adds data element to the stack location, where top is pointing. 5. Returns success. Example Following are the implementations of this operation in various programming languages − C C++ Java Python #include <stdio.h> int MAXSIZE = 8; int stack[8]; int top = -1; /* Check if the stack is full*/ int isfull(){ if(top == MAXSIZE) return 1; else return 0; } /* Function to insert into the stack */ int push(int data){ if(!isfull()) { top = top + 1; stack[top] = data; } else { printf(“Could not insert data, Stack is full.n”); } } /* Main function */ int main(){ int i; push(44); push(10); push(62); push(123); push(15); printf(“Stack Elements: n”); // print stack data for(i = 0; i < 8; i++) { printf(“%d “, stack[i]); } return 0; } Output Stack Elements: 44 10 62 123 15 0 0 0 #include <iostream> int MAXSIZE = 8; int stack[8]; int top = -1; /* Check if the stack is full*/ int isfull(){ if(top == MAXSIZE) return 1; else return 0; } /* Function to insert into the stack */ int push(int data){ if(!isfull()) { top = top + 1; stack[top] = data; } else { printf(“Could not insert data, Stack is full.n”); } return data; } /* Main function */ int main(){ int i; push(44); push(10); push(62); push(123); push(15); printf(“Stack Elements: n”); // print stack data for(i = 0; i < 8; i++) { printf(“%d “, stack[i]); } return 0; } Output Stack Elements: 44 10 62 123 15 0 0 0 public class Demo{ final static int MAXSIZE = 8; static int stack[] = new int[MAXSIZE]; static int top = -1; public static int isfull(){ if(top == MAXSIZE) return 1; else return 0; } public static int push(int data){ if(isfull() != 1) { top = top + 1; stack[top] = data; } else { System.out.print(“Could not insert data, Stack is full.n”); } return data; } public static void main(String[] args){ int i; push(44); push(10); push(62); push(123); push(15); System.out.print(“nStack Elements: “); // print stack data for(i = 0; i < MAXSIZE; i++) { System.out.print(stack[i] + ” “); } } } Output Stack Elements: 44 10 62 123 15 0 0 0 MAXSIZE = 8 stack = [0] * MAXSIZE top = -1 def isfull(): if(top == MAXSIZE): return 1 else: return 0 def push(data): global top if(isfull() != 1): top = top + 1 stack[top] = data else: print(“Could not insert data, Stack is full.”) return data push(44) push(10) push(62) push(123) push(15) print(“Stack Elements: “) for i in range(MAXSIZE): print(stack[i], end = ” “) Output Stack Elements: 44 10 62 123 15 0 0 0 Note − In Java we have used to built-in method push() to perform this operation. Stack Deletion: pop() The pop() is a data manipulation operation which removes elements from the stack. The following pseudo code describes the pop() operation in a simpler way. Algorithm 1. Checks if the stack is empty. 2. If the stack is empty, produces an error and exit. 3. If the stack is not empty, accesses the data element at which top is pointing. 4. Decreases the value of top by 1. 5. Returns success. Example Following are the implementations of this operation in various programming languages − C C++ Java Python #include <stdio.h> int MAXSIZE = 8; int stack[8]; int top = -1; /* Check if the stack is empty */ int isempty(){ if(top == -1) return 1; else return 0; } /* Check if the stack is full*/ int isfull(){ if(top == MAXSIZE) return 1; else return 0;

Circular Linked List Data Structure ”; Previous Next What is Circular Linked List? Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list. Singly Linked List as Circular In singly linked list, the next pointer of the last node points to the first node. Doubly Linked List as Circular In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions. As per the above illustration, following are the important points to be considered. The last link”s next points to the first link of the list in both cases of singly as well as doubly linked list. The first link”s previous points to the last of the list in case of doubly linked list. Basic Operations in Circular Linked List Following are the important operations supported by a circular list. insert − Inserts an element at the start of the list. delete − Deletes an element from the start of the list. display − Displays the list. Circular Linked List – Insertion Operation The insertion operation of a circular linked list only inserts the element at the start of the list. This differs from the usual singly and doubly linked lists as there is no particular starting and ending points in this list. The insertion is done either at the start or after a particular node (or a given position) in the list. Algorithm 1. START 2. Check if the list is empty 3. If the list is empty, add the node and point the head to this node 4. If the list is not empty, link the existing head as the next node to the new node. 5. Make the new node as the new head. 6. END Example Following are the implementations of this operation in various programming languages − C C++ Java Python #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> struct node { int data; int key; struct node *next; }; struct node *head = NULL; struct node *current = NULL; bool isEmpty(){ return head == NULL; } //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if (isEmpty()) { head = link; head->next = head; } else { //point it to old first node link->next = head; //point first to new first node head = link; } } //display the list void printList(){ struct node *ptr = head; printf(“n[ “); //start from the beginning if(head != NULL) { while(ptr->next != ptr) { printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } } printf(” ]”); } void main(){ insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(“Circular Linked List: “); //print list printList(); } Output Circular Linked List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ] #include <iostream> #include <cstring> #include <cstdlib> #include <cstdbool> struct node { int data; int key; struct node *next; }; struct node *head = NULL; struct node *current = NULL; bool isEmpty(){ return head == NULL; } //insert link at the first location void insertFirst(int key, int data){ //create a link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if (isEmpty()) { head = link; head->next = head; } else { //point it to old first node link->next = head; //point first to new first node head = link; } } //display the list void printList(){ struct node *ptr = head; printf(“n[ “); //start from the beginning if(head != NULL) { while(ptr->next != ptr) { printf(“(%d,%d) “,ptr->key,ptr->data); ptr = ptr->next; } } printf(” ]”); } int main(){ insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf(“Circular Linked List: “); //print list printList(); return 0; } Output Circular Linked List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ] //Java program for circular link list import java.util.*; class Node { int data; int key; Node next; } public class Main { static Node head = null; static Node current = null; static boolean isEmpty() { return head == null; } //insert link at the first location static void insertFirst(int key, int data) { //create a link Node link = new Node(); link.key = key; link.data = data; if (isEmpty()) { head = link; head.next = head; } else { //point it to old first node link.next = head; //point first to new first node head = link; } } //display the list static void printList() { Node ptr = head; System.out.print(“n[ “); //start from the beginning if (head != null) { while (ptr.next != ptr) { System.out.print(“(” + ptr.key + “,” + ptr.data + “) “); ptr = ptr.next; } } System.out.print(” ]”); } public static void main(String[] args) { insertFirst(1, 10); insertFirst(2, 20); insertFirst(3, 30); insertFirst(4, 1); insertFirst(5, 40); insertFirst(6, 56); System.out.print(“Circular Linked List: “); //print list printList(); } } Output Circular Linked List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ] #python program for circular linked list class Node: def __init__(self, key, data): self.key = key self.data = data self.next = None head = None current = None def is_empty(): return head is None #insert link at the first location def insert_first(key, data): #create a link global head new_node = Node(key, data) if is_empty(): head = new_node head.next = head else: #point it to old first node new_node.next = head #point first