Department of Computer Science and Engineering
Data Structures Lab

1.Write a C Program to implement counting sort algorithm?

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.

Sample Output:
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

Code Here

2.Write a C Program to implement bucket sort algorithm ?

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

Sample Output:
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.52
Code Here

3.Write a C Program to implement Dijkstra's algorithm?

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

Sample Output:
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<-0
Code Here

4.Write a C Program to find Minimum number of edges that need to be added to form a triangle?

Algorithm :
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

Sample Output:
Input:
  1
 / \
2   3
Output: 1

Input:
  1     3
 /     /
2     4
Output: 2
Code Here

5.Write a C Program to Find Minimum number to be added to all digits of X to make X > Y ?

Algorithm :
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

Sample Output:
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...