Category: design And Analysis Of Algorithms

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;

Binary Search Algorithm Table of content Binary Search Algorithm Implementation ”; Previous Next Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer, since it divides the array into half before searching. For this algorithm to work properly, the data collection should be in the sorted form. Binary search looks for a particular key value by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. But if the middle item has a value greater than the key value, the right sub-array of the middle item is searched. Otherwise, the left sub-array is searched. This process continues recursively until the size of a subarray reduces to zero. Binary Search Algorithm Binary Search algorithm is an interval searching method that performs the searching in intervals only. The input taken by the binary search algorithm must always be in a sorted array since it divides the array into subarrays based on the greater or lower values. The algorithm follows the procedure below − Step 1 − Select the middle item in the array and compare it with the key value to be searched. If it is matched, return the position of the median. Step 2 − If it does not match the key value, check if the key value is either greater than or less than the median value. Step 3 − If the key is greater, perform the search in the right sub-array; but if the key is lower than the median value, perform the search in the left sub-array. Step 4 − Repeat Steps 1, 2 and 3 iteratively, until the size of sub-array becomes 1. Step 5 − If the key value does not exist in the array, then the algorithm returns an unsuccessful search. Pseudocode The pseudocode of binary search algorithms should look like this − Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound – lowerBound ) / 2 if A[midPoint] < x set lowerBound = midPoint + 1 if A[midPoint] > x set upperBound = midPoint – 1 if A[midPoint] = x EXIT: x found at location midPoint end while end procedure Analysis Since the binary search algorithm performs searching iteratively, calculating the time complexity is not as easy as the linear search algorithm. The input array is searched iteratively by dividing into multiple sub-arrays after every unsuccessful iteration. Therefore, the recurrence relation formed would be of a dividing function. To explain it in simpler terms, During the first iteration, the element is searched in the entire array. Therefore, length of the array = n. In the second iteration, only half of the original array is searched. Hence, length of the array = n/2. In the third iteration, half of the previous sub-array is searched. Here, length of the array will be = n/4. Similarly, in the ith iteration, the length of the array will become n/2i To achieve a successful search, after the last iteration the length of array must be 1. Hence, n/2i = 1 That gives us − n = 2i Applying log on both sides, log n = log 2i log n = i. log 2 i = log n The time complexity of the binary search algorithm is O(log n) Example For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example. The following is our sorted array and let us assume that we need to search the location of value 31 using binary search. First, we shall determine half of the array by using this formula − mid = low + (high – low) / 2 Here it is, 0 + (9 – 0) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array. Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find that the value at location 4 is 27, which is not a match. As the value is greater than 27 and we have a sorted array, so we also know that the target value must be in the upper portion of the array. We change our low to mid + 1 and find the new mid value again. low = mid + 1 mid = low + (high – low) / 2 Our new mid is 7 now. We compare the value stored at location 7 with our target value 31. The value stored at location 7 is not a match, rather it is less than what we are looking for. So, the value must be in the lower part from this location. Hence, we calculate the mid again. This time it is 5. We compare the value stored at location 5 with our target value. We find that it is a match. We conclude that the target value 31 is stored at location 5. Binary search halves the searchable items and thus reduces the count of comparisons to be made to very less numbers. Implementation Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work

Hash Table Data structure Table of content Hashing Linear Probing Basic Operations Search Operation Insert Operation Delete Operation Complete implementation ”; Previous Next Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data. Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from. Hashing Hashing is a technique to convert a range of key values into a range of indexes of an array. We”re going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key,value) format. (1,20) (2,70) (42,80) (4,25) (12,44) (14,32) (17,11) (13,78) (37,98) Sr.No. Key Hash Array Index 1 1 1 % 20 = 1 1 2 2 2 % 20 = 2 2 3 42 42 % 20 = 2 2 4 4 4 % 20 = 4 4 5 12 12 % 20 = 12 12 6 14 14 % 20 = 14 14 7 17 17 % 20 = 17 17 8 13 13 % 20 = 13 13 9 37 37 % 20 = 17 17 Linear Probing As we can see, it may happen that the hashing technique is used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear probing. Sr.No. Key Hash Array Index After Linear Probing, Array Index 1 1 1 % 20 = 1 1 1 2 2 2 % 20 = 2 2 2 3 42 42 % 20 = 2 2 3 4 4 4 % 20 = 4 4 4 5 12 12 % 20 = 12 12 12 6 14 14 % 20 = 14 14 14 7 17 17 % 20 = 17 17 17 8 13 13 % 20 = 13 13 13 9 37 37 % 20 = 17 17 18 Basic Operations Following are the basic primary operations of a hash table. Search − Searches an element in a hash table. Insert − Inserts an element in a hash table. Delete − Deletes an element from a hash table. DataItem Define a data item having some data and key, based on which the search is to be conducted in a hash table. struct DataItem { int data; int key; }; Hash Method Define a hashing method to compute the hash code of the key of the data item. int hashCode(int key){ return key % SIZE; } Search Operation Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code. struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray[hashIndex] != NULL) { if(hashArray[hashIndex]->key == key) return hashArray[hashIndex]; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; } Example Following are the implementations of this operation in various programming language − C C++ Java Python #include <stdio.h> #define SIZE 10 // Define the size of the hash table struct DataItem { int key; }; struct DataItem *hashArray[SIZE]; // Define the hash table as an array of DataItem pointers int hashCode(int key) { // Return a hash value based on the key return key % SIZE; } struct DataItem *search(int key) { // get the hash int hashIndex = hashCode(key); // move in array until an empty slot is found or the key is found while (hashArray[hashIndex] != NULL) { // If the key is found, return the corresponding DataItem pointer if (hashArray[hashIndex]->key == key) return hashArray[hashIndex]; // go to the next cell ++hashIndex; // wrap around the table hashIndex %= SIZE; } // If the key is not found, return NULL return NULL; } int main() { // Initializing the hash table with some sample DataItems struct DataItem item2 = {25}; // Assuming the key is 25 struct DataItem item3 = {64}; // Assuming the key is 64 struct DataItem item4 = {22}; // Assuming the key is 22 // Calculate the hash index for each item and place them in the hash table int hashIndex2 = hashCode(item2.key); hashArray[hashIndex2] = &item2; int hashIndex3 = hashCode(item3.key); hashArray[hashIndex3] = &item3; int hashIndex4 = hashCode(item4.key); hashArray[hashIndex4] = &item4; // Call the search function to test it int keyToSearch = 64; // The key to search for in the hash table struct DataItem *result = search(keyToSearch); printf(“The element to be searched: %d”, keyToSearch); if (result != NULL) { printf(“nElement found”); } else { printf(“nElement not found”); } return 0; } Output The element to be searched: 64 Element found #include <iostream> #include <unordered_map> using namespace std; #define SIZE 10 // Define the size of the hash table struct DataItem { int key; }; unordered_map<int, DataItem*> hashMap; // Define the hash table as an unordered_map int hashCode(int key) { // Return a hash value based on the key return key % SIZE; } DataItem* search(int key) { // get the hash int hashIndex = hashCode(key); // move in the map until an empty slot is found or the key is found while (hashMap[hashIndex] != nullptr) { // If the key is found, return the corresponding DataItem pointer if (hashMap[hashIndex]->key == key) return hashMap[hashIndex]; // go to the next

Vertex Cover Table of content Vertex Cover Example Analysis Implementation ”; Previous Next Vertex Cover A vertex-cover of an undirected graph G = (V, E) is a subset of vertices V” ⊆ V such that if edge (u, v) is an edge of G, then either u in V or v in V” or both. Find a vertex-cover of maximum size in a given undirected graph. This optimal vertexcover is the optimization version of an NP-complete problem. However, it is not too hard to find a vertex-cover that is near optimal. APPROX-VERTEX_COVER (G: Graph) c ← { } E” ← E[G] while E” is not empty do Let (u, v) be an arbitrary edge of E” c ← c U {u, v} Remove from E” every edge incident on either u or v return c Example The set of edges of the given graph is − {(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)} Now, we start by selecting an arbitrary edge (1,6). We eliminate all the edges, which are either incident to vertex 1 or 6 and we add edge (1,6) to cover. In the next step, we have chosen another edge (2,3) at random Now we select another edge (4,7). We select another edge (8,5). Hence, the vertex cover of this graph is {1,2,4,5}. Analysis It is easy to see that the running time of this algorithm is O(V + E), using adjacency list to represent E”. Implementation Following are the implementations of the above approach in various programming languages − C C++ Java Python #include <stdio.h> #include <stdbool.h> #define MAX_VERTICES 100 int graph[MAX_VERTICES][MAX_VERTICES]; bool included[MAX_VERTICES]; // Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm void approxVertexCover(int vertices, int edges) { bool edgesRemaining[MAX_VERTICES][MAX_VERTICES]; for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { edgesRemaining[i][j] = graph[i][j]; } } while (edges > 0) { int u, v; for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { if (edgesRemaining[i][j]) { u = i; v = j; break; } } } included[u] = included[v] = true; for (int i = 0; i < vertices; i++) { edgesRemaining[u][i] = edgesRemaining[i][u] = false; edgesRemaining[v][i] = edgesRemaining[i][v] = false; } edges–; } } int main() { int vertices = 8; int edges = 10; int edgesData[10][2] = {{1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}}; for (int i = 0; i < edges; i++) { int u = edgesData[i][0]; int v = edgesData[i][1]; graph[u][v] = graph[v][u] = 1; } approxVertexCover(vertices, edges); printf(“Vertex Cover: “); for (int i = 1; i <= vertices; i++) { if (included[i]) { printf(“%d “, i); } } printf(“n”); return 0; } Output Vertex Cover: 1 3 4 5 6 7 #include <iostream> #include <vector> using namespace std; const int MAX_VERTICES = 100; vector<vector<int>> graph(MAX_VERTICES, vector<int>(MAX_VERTICES, 0)); vector<bool> included(MAX_VERTICES, false); // Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm void approxVertexCover(int vertices, int edges) { vector<vector<bool>> edgesRemaining(vertices, vector<bool>(vertices, false)); for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { edgesRemaining[i][j] = graph[i][j]; } } while (edges > 0) { int u, v; for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { if (edgesRemaining[i][j]) { u = i; v = j; break; } } } included[u] = included[v] = true; for (int i = 0; i < vertices; i++) { edgesRemaining[u][i] = edgesRemaining[i][u] = false; edgesRemaining[v][i] = edgesRemaining[i][v] = false; } edges–; } } int main() { int vertices = 8; int edges = 10; int edgesData[10][2] = {{1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}}; for (int i = 0; i < edges; i++) { int u = edgesData[i][0]; int v = edgesData[i][1]; graph[u][v] = graph[v][u] = 1; } approxVertexCover(vertices, edges); cout << “Vertex Cover: “; for (int i = 1; i <= vertices; i++) { if (included[i]) { cout << i << ” “; } } cout << endl; return 0; } Output Vertex Cover: 1 3 4 5 6 7 import java.util.Arrays; public class VertexCoverProblem { static final int MAX_VERTICES = 100; static int[][] graph = new int[MAX_VERTICES][MAX_VERTICES]; static boolean[] included = new boolean[MAX_VERTICES]; // Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm static void approxVertexCover(int vertices, int edges) { int[][] edgesRemaining = new int[vertices][vertices]; for (int i = 0; i < vertices; i++) { edgesRemaining[i] = Arrays.copyOf(graph[i], vertices); } while (edges > 0) { int u = -1, v = -1; for (int i = 0; i < vertices; i++) { for (int j = 0; j < vertices; j++) { if (edgesRemaining[i][j] == 1) { u = i; v = j; break; } } } // Check if there are no more edges remaining if (u == -1 || v == -1) { break; } included[u] = included[v] = true; for (int i = 0; i < vertices; i++) { edgesRemaining[u][i] = edgesRemaining[i][u] = 0; edgesRemaining[v][i] = edgesRemaining[i][v] = 0; } edges–; } } public static void main(String[] args) { int vertices = 8; int edges = 10; int[][] edgesData ={{1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}}; for (int i = 0; i < edges; i++) { int u = edgesData[i][0]; int v = edgesData[i][1]; graph[u][v] = graph[v][u] = 1; } approxVertexCover(vertices, edges); System.out.print(“Vertex Cover: “); for (int i = 1; i <= vertices; i++)

Interpolation Search Algorithm Table of content Positioning in Binary Search Position Probing in Interpolation Search Interpolation Search Algorithm Implementation ”; Previous Next Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed. Binary search has a huge advantage of time complexity over linear search. Linear search has worst-case complexity of Ο(n) whereas binary search has Ο(log n). There are cases where the location of target data may be known in advance. For example, in case of a telephone directory, if we want to search the telephone number of “Morpheus”. Here, linear search and even binary search will seem slow as we can directly jump to memory space where the names start from ”M” are stored. Positioning in Binary Search In binary search, if the desired data is not found then the rest of the list is divided in two parts, lower and higher. The search is carried out in either of them. Even when the data is sorted, binary search does not take advantage to probe the position of the desired data. Position Probing in Interpolation Search Interpolation search finds a particular item by computing the probe position. Initially, the probe position is the position of the middle most item of the collection. If a match occurs, then the index of the item is returned. To split the list into two parts, we use the following method − $$mid, =, Lo, +, frac{left ( Hi, -, Lo right )ast left ( X, -, Aleft [ Lo right ] right )}{Aleft [ Hi right ], -, Aleft [ Lo right ]}$$ where − A = list Lo = Lowest index of the list Hi = Highest index of the list A[n] = Value stored at index n in the list If the middle item is greater than the item, then the probe position is again calculated in the sub-array to the right of the middle item. Otherwise, the item is searched in the sub-array to the left of the middle item. This process continues on the sub-array as well until the size of subarray reduces to zero. Interpolation Search Algorithm As it is an improvisation of the existing BST algorithm, we are mentioning the steps to search the ”target” data value index, using position probing − 1. Start searching data from middle of the list. 2. If it is a match, return the index of the item, and exit. 3. If it is not a match, probe position. 4. Divide the list using probing formula and find the new middle. 5. If data is greater than middle, search in higher sub-list. 6. If data is smaller than middle, search in lower sub-list. 7. Repeat until match. Pseudocode A → Array list N → Size of A X → Target Value Procedure Interpolation_Search() Set Lo → 0 Set Mid → -1 Set Hi → N-1 While X does not match if Lo equals to Hi OR A[Lo] equals to A[Hi] EXIT: Failure, Target not found end if Set Mid = Lo + ((Hi – Lo) / (A[Hi] – A[Lo])) * (X – A[Lo]) if A[Mid] = X EXIT: Success, Target found at Mid else if A[Mid] < X Set Lo to Mid+1 else if A[Mid] > X Set Hi to Mid-1 end if end if End While End Procedure Analysis Runtime complexity of interpolation search algorithm is Ο(log (log n)) as compared to Ο(log n) of BST in favorable situations. Example To understand the step-by-step process involved in the interpolation search, let us look at an example and work around it. Consider an array of sorted elements given below − Let us search for the element 19. Solution Unlike binary search, the middle point in this approach is chosen using the formula − $$mid, =, Lo, +, frac{left ( Hi, -, Lo right )ast left ( X, -, Aleft [ Lo right ] right )}{Aleft [ Hi right ], -, Aleft [ Lo right ]}$$ So in this given array input, Lo = 0, A[Lo] = 10 Hi = 9, A[Hi] = 44 X = 19 Applying the formula to find the middle point in the list, we get $$mid, =, 0, +, frac{left ( 9, -, 0 right )ast left ( 19, -, 10 right )}{44, -, 10}$$ $$mid, =, frac{9ast 9}{34}$$ $$mid, =, frac{81}{34},=,2.38$$ Since, mid is an index value, we only consider the integer part of the decimal. That is, mid = 2. Comparing the key element given, that is 19, to the element present in the mid index, it is found that both the elements match. Therefore, the element is found at index 2. Implementation Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in sorted and equally distributed form. C C++ Java Python #include<stdio.h> #define MAX 10 // array of items on which linear search will be conducted. int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 }; int interpolation_search(int data){ int lo = 0; int hi = MAX – 1; int mid = -1; int comparisons = 1; int index = -1; while(lo <= hi) { printf(“Comparison %d n” , comparisons ) ; printf(“lo : %d, list[%d] = %dn”, lo, lo, list[lo]);

Radix Sort Algorithm Table of content Radix Sort Algorithm Implementation ”; Previous Next Radix sort is a step-wise sorting algorithm that starts the sorting from the least significant digit of the input elements. Like Counting Sort and Bucket Sort, Radix sort also assumes something about the input elements, that they are all k-digit numbers. The sorting starts with the least significant digit of each element. These least significant digits are all considered individual elements and sorted first; followed by the second least significant digits. This process is continued until all the digits of the input elements are sorted. Note − If the elements do not have same number of digits, find the maximum number of digits in an input element and add leading zeroes to the elements having less digits. It does not change the values of the elements but still makes them k-digit numbers. Radix Sort Algorithm The radix sort algorithm makes use of the counting sort algorithm while sorting in every phase. The detailed steps are as follows − Step 1 − Check whether all the input elements have same number of digits. If not, check for numbers that have maximum number of digits in the list and add leading zeroes to the ones that do not. Step 2 − Take the least significant digit of each element. Step 3 − Sort these digits using counting sort logic and change the order of elements based on the output achieved. For example, if the input elements are decimal numbers, the possible values each digit can take would be 0-9, so index the digits based on these values. Step 4 − Repeat the Step 2 for the next least significant digits until all the digits in the elements are sorted. Step 5 − The final list of elements achieved after kth loop is the sorted output. Pseudocode Algorithm: RadixSort(a[], n): // Find the maximum element of the list max = a[0] for (i=1 to n-1): if (a[i]>max): max=a[i] // applying counting sort for each digit in each number of //the input list For (pos=1 to max/pos>0): countSort(a, n, pos) pos=pos*10 The countSort algorithm called would be − Algorithm: countSort(a, n, pos) Initialize count[0…9] with zeroes for i = 0 to n: count[(a[i]/pos) % 10]++ for i = 1 to 10: count[i] = count[i] + count[i-1] for i = n-1 to 0: output[count[(a[i]/pos) % 10]-1] = a[i] i– for i to n: a[i] = output[i] Analysis Given that there are k-digits in the input elements, the running time taken by the radix sort algorithm would be Θ(k(n + b). Here, n is the number of elements in the input list while b is the number of possible values each digit of a number can take. Example For the given unsorted list of elements, 236, 143, 26, 42, 1, 99, 765, 482, 3, 56, we need to perform the radix sort and obtain the sorted output list − Step 1 Check for elements with maximum number of digits, which is 3. So we add leading zeroes to the numbers that do not have 3 digits. The list we achieved would be − 236, 143, 026, 042, 001, 099, 765, 482, 003, 056 Step 2 Construct a table to store the values based on their indexing. Since the inputs given are decimal numbers, the indexing is done based on the possible values of these digits, i.e., 0-9. Step 3 Based on the least significant digit of all the numbers, place the numbers on their respective indices. The elements sorted after this step would be 001, 042, 482, 143, 003, 765, 236, 026, 056, 099. Step 4 The order of input for this step would be the order of the output in the previous step. Now, we perform sorting using the second least significant digit. The order of the output achieved is 001, 003, 026, 236, 042, 143, 056, 765, 482, 099. Step 5 The input list after the previous step is rearranged as − 001, 003, 026, 236, 042, 143, 056, 765, 482, 099 Now, we need to sort the last digits of the input elements. Since there are no further digits in the input elements, the output achieved in this step is considered as the final output. The final sorted output is − 1, 3, 26, 42, 56, 99, 143, 236, 482, 765 Implementation The counting sort algorithm assists the radix sort to perform sorting on multiple d-digit numbers iteratively for ‘d’ loops. Radix sort is implemented in four programming languages in this tutorial: C, C++, Java, Python. C C++ Java Python #include <stdio.h> void countsort(int a[], int n, int pos){ int output[n + 1]; int max = (a[0] / pos) % 10; for (int i = 1; i < n; i++) { if (((a[i] / pos) % 10) > max) max = a[i]; } int count[max + 1]; for (int i = 0; i < max; ++i) count[i] = 0; for (int i = 0; i < n; i++) count[(a[i] / pos) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i – 1]; for (int i = n – 1; i >= 0; i–) { output[count[(a[i] / pos) % 10] – 1] = a[i]; count[(a[i] / pos) % 10]–; } for (int i = 0; i < n; i++) a[i] = output[i]; } void radixsort(int a[], int n){ int max = a[0]; for (int i = 1; i < n; i++) if (a[i] > max) max = a[i]; for (int pos = 1; max / pos > 0; pos *= 10) countsort(a, n,

NP Hard & NP-Complete Classes Table of content Definition of NP-Completeness NP-Complete Problems NP-Hard Problems TSP is NP-Complete Proof ”; Previous Next A problem is in the class NPC if it is in NP and is as hard as any problem in NP. A problem is NP-hard if all problems in NP are polynomial time reducible to it, even though it may not be in NP itself. If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable. These problems are called NP-complete. The phenomenon of NP-completeness is important for both theoretical and practical reasons. Definition of NP-Completeness A language B is NP-complete if it satisfies two conditions B is in NP Every A in NP is polynomial time reducible to B. If a language satisfies the second property, but not necessarily the first one, the language B is known as NP-Hard. Informally, a search problem B is NP-Hard if there exists some NP-Complete problem A that Turing reduces to B. The problem in NP-Hard cannot be solved in polynomial time, until P = NP. If a problem is proved to be NPC, there is no need to waste time on trying to find an efficient algorithm for it. Instead, we can focus on design approximation algorithm. NP-Complete Problems Following are some NP-Complete problems, for which no polynomial time algorithm is known. Determining whether a graph has a Hamiltonian cycle Determining whether a Boolean formula is satisfiable, etc. NP-Hard Problems The following problems are NP-Hard The circuit-satisfiability problem Set Cover Vertex Cover Travelling Salesman Problem In this context, now we will discuss TSP is NP-Complete TSP is NP-Complete The traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip Proof To prove TSP is NP-Complete, first we have to prove that TSP belongs to NP. In TSP, we find a tour and check that the tour contains each vertex once. Then the total cost of the edges of the tour is calculated. Finally, we check if the cost is minimum. This can be completed in polynomial time. Thus TSP belongs to NP. Secondly, we have to prove that TSP is NP-hard. To prove this, one way is to show that Hamiltonian cycle ≤p TSP (as we know that the Hamiltonian cycle problem is NPcomplete). Assume G = (V, E) to be an instance of Hamiltonian cycle. Hence, an instance of TSP is constructed. We create the complete graph G” = (V, E”), where $$E^{”}=lbrace(i, j)colon i, j in V ::and:ineq j$$ Thus, the cost function is defined as follows − $$t(i,j)=begin{cases}0 & if: (i, j): in E\1 & otherwiseend{cases}$$ Now, suppose that a Hamiltonian cycle h exists in G. It is clear that the cost of each edge in h is 0 in G” as each edge belongs to E. Therefore, h has a cost of 0 in G”. Thus, if graph G has a Hamiltonian cycle, then graph G” has a tour of 0 cost. Conversely, we assume that G” has a tour h” of cost at most 0. The cost of edges in E” are 0 and 1 by definition. Hence, each edge must have a cost of 0 as the cost of h” is 0. We therefore conclude that h” contains only edges in E. We have thus proven that G has a Hamiltonian cycle, if and only if G” has a tour of cost at most 0. TSP is NP-complete. Print Page Previous Next Advertisements ”;

Selection Sort Algorithm Table of content Selection Sort Algorithm Implementation ”; Previous Next Selection sort is a simple sorting algorithm. This sorting algorithm, like insertion sort, is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundaries by one element to the right. This algorithm is not suitable for large data sets as its average and worst case complexities are of O(n2), where n is the number of items. Selection Sort Algorithm This type of sorting is called Selection Sort as it works by repeatedly sorting elements. That is: we first find the smallest value in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and we continue the process in this way until the entire array is sorted. 1. Set MIN to location 0. 2. Search the minimum element in the list. 3. Swap with value at location MIN. 4. Increment MIN to point to next element. 5. Repeat until the list is sorted. Pseudocode Algorithm: Selection-Sort (A) fori← 1 to n-1 do min j ←i; min x ← A[i] for j ←i + 1 to n do if A[j] < min x then min j ← j min x ← A[j] A[min j] ← A [i] A[i] ← min x Analysis Selection sort is among the simplest of sorting techniques and it works very well for small files. It has a quite important application as each item is actually moved at the most once. Section sort is a method of choice for sorting files with very large objects (records) and small keys. The worst case occurs if the array is already sorted in a descending order and we want to sort them in an ascending order. Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test if 𝑨[𝒋] < A[j] < min x is executed exactly the same number of times in every case. Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It clearly shows the similarity between Selection sort and Bubble sort. Bubble sort selects the maximum remaining elements at each stage, but wastes some effort imparting some order to an unsorted part of the array. Selection sort is quadratic in both the worst and the average case, and requires no extra memory. For each i from 1 to n – 1, there is one exchange and n – i comparisons, so there is a total of n – 1 exchanges and (n − 1) + (n − 2) + …+2 + 1 = n(n − 1)/2 comparisons. These observations hold, no matter what the input data is. In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input. Example Consider the following depicted array as an example. For the first position in the sorted list, the whole list is scanned sequentially. The first position where 14 is stored presently, we search the whole list and find that 10 is the lowest value. So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list, appears in the first position of the sorted list. For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner. We find that 14 is the second lowest value in the list and it should appear at the second place. We swap these values. After two iterations, two least values are positioned at the beginning in a sorted manner. The same process is applied to the rest of the items in the array − Implementation The selection sort algorithm is implemented in four different programming languages below. The given program selects the minimum number of the array and swaps it with the element in the first index. The second minimum number is swapped with the element present in the second index. The process goes on until the end of the array is reached. C C++ Java Python #include <stdio.h> void selectionSort(int array[], int size){ int i, j, imin; for(i = 0; i<size-1; i++) { imin = i; //get index of minimum data for(j = i+1; j<size; j++) if(array[j] < array[imin]) imin = j; //placing in correct position int temp; temp = array[i]; array[i] = array[imin]; array[imin] = temp; } } int main(){ int n; n = 5; int arr[5] = {12, 19, 55, 2, 16}; // initialize the array printf(“Array before Sorting: “); for(int i = 0; i<n; i++) printf(“%d “,arr[i]); printf(“n”); selectionSort(arr, n); printf(“Array after Sorting: “); for(int i = 0; i<n; i++) printf(“%d “, arr[i]); printf(“n”); } Output Array before Sorting: 12 19 55 2 16 Array after Sorting: 2 12 16 19 55 #include<iostream> using namespace std; void swapping(int &a, int &b) { //swap the content of a and b int temp; temp = a; a = b;

Exponential Search Algorithm Table of content Exponential Search Algorithm Implementation ”; Previous Next Exponential search algorithm targets a range of an input array in which it assumes that the required element must be present in and performs a binary search on that particular small range. This algorithm is also known as doubling search or finger search. It is similar to jump search in dividing the sorted input into multiple blocks and conducting a smaller scale search. However, the difference occurs while performing computations to divide the blocks and the type of smaller scale search applied (jump search applies linear search and exponential search applies binary search). Hence, this algorithm jumps exponentially in the powers of 2. In simpler words, the search is performed on the blocks divided using pow(2, k) where k is an integer greater than or equal to 0. Once the element at position pow(2, n) is greater than the key element, binary search is performed on the current block. Exponential Search Algorithm In the exponential search algorithm, the jump starts from the 1st index of the array. So we manually compare the first element as the first step in the algorithm. Step 1 − Compare the first element in the array with the key, if a match is found return the 0th index. Step 2 − Initialize i = 1 and compare the ith element of the array with the key to be search. If it matches return the index. Step 3 − If the element does not match, jump through the array exponentially in the powers of 2. Therefore, now the algorithm compares the element present in the incremental position. Step 4 − If the match is found, the index is returned. Otherwise Step 2 is repeated iteratively until the element at the incremental position becomes greater than the key to be searched. Step 5 − Since the next increment has the higher element than the key and the input is sorted, the algorithm applies binary search algorithm on the current block. Step 6 − The index at which the key is present is returned if the match is found; otherwise it is determined as an unsuccessful search. Pseudocode Begin m := pow(2, k) // m is the block size start := 1 low := 0 high := size – 1 // size is the size of input if array[0] == key return 0 while array[m] <= key AND m < size do start := start + 1 m := pow(2, start) while low <= high do: mid = low + (high – low) / 2 if array[mid] == x return mid if array[mid] < x low = mid + 1 else high = mid – 1 done return invalid location End Analysis Even though it is called Exponential search it does not perform searching in exponential time complexity. But as we know, in this search algorithm, the basic search being performed is binary search. Therefore, the time complexity of the exponential search algorithm will be the same as the binary search algorithm’s, O(log n). Example To understand the exponential search algorithm better and in a simpler way, let us search for an element in an example input array using the exponential search algorithm − The sorted input array given to the search algorithm is − Let us search for the position of element 81 in the given array. Step 1 Compare the first element of the array with the key element 81. The first element of the array is 6, but the key element to be searched is 81; hence, the jump starts from the 1st index as there is no match found. Step 2 After initializing i = 1, the key element is compared with the element in the first index. Here, the element in the 1st index does not match with the key element. So it is again incremented exponentially in the powers of 2. The index is incremented to 2m = 21 = the element in 2nd index is compared with the key element. It is still not a match so it is once again incremented. Step 3 The index is incremented in the powers of 2 again. 22 = 4 = the element in 4th index is compared with the key element and a match is not found yet. Step 4 The index is incremented exponentially once again. This time the element in the 8th index is compared with the key element and a match is not found. However, the element in the 8th index is greater than the key element. Hence, the binary search algorithm is applied on the current block of elements. Step 5 The current block of elements includes the elements in the indices [4, 5, 6, 7]. Small scale binary search is applied on this block of elements, where the mid is calculated to be the 5th element. Step 6 The match is not found at the mid element and figures that the desired element is greater than the mid element. Hence, the search takes place is the right half of the block. The mid now is set as 6th element − Step 7 The element is still not found at the 6th element so it now searches in the right half of the mid element. The next mid is set as 7th element. Here, the element is found at the 7th index. Implementation In the implementation of the exponential search algorithm, the program checks for the matches at every exponential jump in the powers of 2. If the match is found the location of the

Optimal Cost Binary Search Trees Table of content Analysis Example ”; Previous Next A Binary Search Tree (BST) is a tree where the key values are stored in the internal nodes. The external nodes are null nodes. The keys are ordered lexicographically, i.e. for each internal node all the keys in the left sub-tree are less than the keys in the node, and all the keys in the right sub-tree are greater. When we know the frequency of searching each one of the keys, it is quite easy to compute the expected cost of accessing each node in the tree. An optimal binary search tree is a BST, which has minimal expected cost of locating each node Search time of an element in a BST is O(n), whereas in a Balanced-BST search time is O(log n). Again the search time can be improved in Optimal Cost Binary Search Tree, placing the most frequently used data in the root and closer to the root element, while placing the least frequently used data near leaves and in leaves. Here, the Optimal Binary Search Tree Algorithm is presented. First, we build a BST from a set of provided n number of distinct keys < k1, k2, k3, … kn >. Here we assume, the probability of accessing a key Ki is pi. Some dummy keys (d0, d1, d2, … dn) are added as some searches may be performed for the values which are not present in the Key set K. We assume, for each dummy key di probability of access is qi. Optimal-Binary-Search-Tree(p, q, n) e[1…n + 1, 0…n], w[1…n + 1, 0…n], root[1…n + 1, 0…n] for i = 1 to n + 1 do e[i, i – 1] := qi – 1 w[i, i – 1] := qi – 1 for l = 1 to n do for i = 1 to n – l + 1 do j = i + l – 1 e[i, j] := ∞ w[i, i] := w[i, i -1] + pj + qj for r = i to j do t := e[i, r – 1] + e[r + 1, j] + w[i, j] if t < e[i, j] e[i, j] := t root[i, j] := r return e and root Analysis The algorithm requires O (n3) time, since three nested for loops are used. Each of these loops takes on at most n values. Example Considering the following tree, the cost is 2.80, though this is not an optimal result. Node Depth Probability Contribution k1 1 0.15 0.30 k2 0 0.10 0.10 k3 2 0.05 0.15 k4 1 0.10 0.20 k5 2 0.20 0.60 d0 2 0.05 0.15 d1 2 0.10 0.30 d2 3 0.05 0.20 d3 3 0.05 0.20 d4 3 0.05 0.20 d5 3 0.10 0.40 Total 2.80 To get an optimal solution, using the algorithm discussed in this chapter, the following tables are generated. In the following tables, column index is i and row index is j. e 1 2 3 4 5 6 5 2.75 2.00 1.30 0.90 0.50 0.10 4 1.75 1.20 0.60 0.30 0.05 3 1.25 0.70 0.25 0.05 2 0.90 0.40 0.05 1 0.45 0.10 0 0.05 w 1 2 3 4 5 6 5 1.00 0.80 0.60 0.50 0.35 0.10 4 0.70 0.50 0.30 0.20 0.05 3 0.55 0.35 0.15 0.05 2 0.45 0.25 0.05 1 0.30 0.10 0 0.05 root 1 2 3 4 5 5 2 4 5 5 5 4 2 2 4 4 3 2 2 3 2 1 2 1 1 From these tables, the optimal tree can be formed. Print Page Previous Next Advertisements ”;