ADA Lab Algorithms
All 13 VTU BCSL40A programs with complete C source code, step-by-step explanations, sample input/output, and viva questions.
Kruskal's Algorithm
Kruskal's algorithm finds the Minimum Spanning Tree of a weighted graph by sorting edges and using union-find to avoid cycles.
Prim's Algorithm
Prim's algorithm builds a Minimum Spanning Tree by greedily expanding from a starting vertex, always picking the minimum cost edge to an unvisited vertex.
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
Greedy (Fractional) Knapsack
The Fractional Knapsack problem uses a greedy approach — selecting items by highest value-to-weight ratio — allowing fractional items to maximize profit.
Floyd's Algorithm
Floyd's algorithm (Floyd-Warshall) finds the shortest paths between all pairs of vertices in a weighted graph using dynamic programming.
Warshall's Algorithm
Warshall's algorithm computes the transitive closure of a directed graph — determining if a path exists between every pair of vertices.
0/1 Knapsack Problem
The 0/1 Knapsack problem uses dynamic programming to find the maximum profit by selecting items with given weights and values without exceeding the knapsack capacity.
Selection Sort
Selection Sort repeatedly finds the minimum element from the unsorted portion of an array and places it at the correct position. This implementation measures time complexity empirically.
Quick Sort
Quick Sort is a fast divide-and-conquer sorting algorithm that partitions the array around a pivot, recursively sorting subarrays. This implementation includes empirical time analysis.
Merge Sort
Merge Sort is a stable divide-and-conquer sorting algorithm that recursively divides the array in half, sorts each half, and merges them back in order.
Subset Sum Problem
The Subset Sum problem uses backtracking to find all subsets of a given set whose elements sum to a target value.
N-Queens Problem
The N-Queens problem uses backtracking to place N queens on an N×N chessboard so that no two queens attack each other.