1.Write a C Program to implement counting sort algorithm?
Step 1: Start Step 2: Enter the size of the array Step 3: Enter array elements Step 4: Find out the maximum element (let it be max) from the given array. Step 5: Initialize an array of length max+1 with all elements 0. This array is used for storing the count of the elements in the array. Step 6; Store the count of each element at their respective index in count array Step 7: Store cumulative sum of the elements of the count array. Step 8: Find the index of each element of the original array in count array. This gives the cumulative count. Place the element at the index calculated. Step 9: After placing each element at its correct position, decrease the its count by one.
Enter the size of array : 7 4 2 2 8 3 3 1 The resultant sorted array using count sort is : 1 2 2 3 3 4 8
2.Write a C Program to implement bucket sort algorithm ?
Step 1: Start Step 2: Enter the size of the array Step 3: Enter array elements Step 4: Create an array of size 10. Each slot of this array is used as a bucket for storing elements. Step 5: The elements of each bucket are sorted using any of the stable sorting algorithms. Here, we have used quicksort (inbuilt function). Step 6; The elements from each bucket are gathered.It is done by iterating through the bucket and inserting an individual element into the original array in each cycle. The element from the bucket is erased once it is copied into the original array. Step 7: Stop
Enter the size of array : 7 0.42 0.32 0.23 0.52 0.25 0.47 0.51 The resultant sorted array using bucket sort is : 0.23 0.25 0.32 0.42 o.47 0.51 0.52Code Here
3.Write a C Program to implement Dijkstra's algorithm?
Step 1: Start Step 2: Enter the weighted graph Step 3: Choose the starting vertex and assign infinity path values to all other vertices Step 4: Go to each vertex adjacent to this vertex and update its path length Step 5: If the path length of adjacent vertex is lesser than new path length,don't update it Step 6: Avoid updating path lengths of already visted vertices Step 7: After each iteration,we pick the unvisited vertex with least path length. Step 8: Notice how the right most vertex has its path length updated twice Step 9: Repeat until all the vertices have been visited Step 10: Stop
Enter no.of vertices:5 Enter the adjacency matrix: 0 10 0 30 100 10 0 50 0 0 0 50 0 20 10 30 0 20 0 60 100 0 10 60 0 Enter the starting node:0 Distance of node 1=10 path=1<-0 Distance of node 2=50 path=1<-3<-0 Distance of node 3=10 path=3<-0 Distance of node 1=10 path=4<-2<-3<-0Code Here
4.Write a C Program to find Minimum number of edges that need to be added to form a triangle?
Step 1: Start Step 2: Give an undirected graph with N vertices and N edges. Step 3: No two edges connect the same pair of vertices. Step 4: There are four cases that appear are: Case 1: If there exist nodes i, j and k such that there is an edge from (i, j), (j, k) and (k, i) then the answer is 0. Case 2: If there exist nodes i, j and k such that only two pairs of vertices are connected then a single edge is required to form a triangle. So update ans = min(ans, 1). Case 3: Otherwise, if there only a single pair of vertices is connected then ans = min(ans, 2). Case 4: When there is no edge then ans = min(ans, 3). Step 5: Stop
Input: 1 / \ 2 3 Output: 1 Input: 1 3 / / 2 4 Output: 2Code Here
5.Write a C Program to Find Minimum number to be added to all digits of X to make X > Y ?
Step 1: Start Step 2: Give two numbvers X and Y of same length Step 3: To find minimum number of digits there exists three cases Step 4: Set a loop Case 1: Find if X is already lexicographically larger than Y. If yes, then we don’t need to do anything Case 2: Otherwise add (Y[0] – X[0]) to all elements of X and then check if X is lexicographically larger than Y or not. Case 3: If it is still not larger, then answer will be (Y[0] – X[0]) + 1 because the first elements of X become larger than first element of Y means X[0] > Y[0]. Step 5: Stop
Input: X = 123, Y = 222 Output: 1 Explanation: Add 1 to all digits of X Then X becomes {2, 3, 4} which is lexicographically larger than {2, 2, 2}. input: X = 4512, Y = 2998 Output: 0 Explanation: X is already lexicographically larger than Y so the answer will be 0.Code Here
More programs will be uploaded soon...