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 ”;

Approximation Algorithms Table of content Approximation Algorithms Performance Ratios Examples ”; Previous Next Approximation Algorithms Approximation algorithms are algorithms designed to solve problems that are not solvable in polynomial time for approximate solutions. These problems are known as NP complete problems. These problems are significantly effective to solve real world problems, therefore, it becomes important to solve them using a different approach. NP complete problems can still be solved in three cases: the input could be so small that the execution time is reduced, some problems can still be classified into problems that can be solved in polynomial time, or use approximation algorithms to find near-optima solutions for the problems. This leads to the concept of performance ratios of an approximation problem. Performance Ratios The main idea behind calculating the performance ratio of an approximation algorithm, which is also called as an approximation ratio, is to find how close the approximate solution is to the optimal solution. The approximate ratio is represented using ρ(n) where n is the input size of the algorithm, C is the near-optimal solution obtained by the algorithm, C* is the optimal solution for the problem. The algorithm has an approximate ratio of ρ(n) if and only if − $$maxleft{frac{C}{C^{ast} },frac{C^{ast }}{C} right}leq rho left ( n right )$$ The algorithm is then called a ρ(n)-approximation algorithm. Approximation Algorithms can be applied on two types of optimization problems: minimization problems and maximization problems. If the optimal solution of the problem is to find the maximum cost, the problem is known as the maximization problem; and if the optimal solution of the problem is to find the minimum cost, then the problem is known as a minimization problem. For maximization problems, the approximation ratio is calculated by C*/C since 0 ≤ C ≤ C*. For minimization problems, the approximation ratio is calculated by C/C* since 0 ≤ C* ≤ C. Assuming that the costs of approximation algorithms are all positive, the performance ratio is well defined and will not be less than 1. If the value is 1, that means the approximate algorithm generates the exact optimal solution. Examples Few popular examples of the approximation algorithms are − Vertex Cover Algorithm Set Cover Problem Travelling Salesman Problem (Approximation Approach) The Subset Sum Problem Print Page Previous Next Advertisements ”;

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

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