VTU 4th Semester ADA Lab - Complete Study & Viva Workbook
Viva Questions by Program
## Viva Questions by Program
### Kruskal's Algorithm
- How does it prevent cycles? -> Uses Disjoint Set (Union-Find)
- Time complexity? -> O(E log E)
### Prim's Algorithm
- Difference from Kruskal? -> Greedy but vertex-based
- Optimized using? -> Min-Heap
### Floyd's Algorithm
- Works on? -> All-pairs shortest path, no negative cycles
- Time complexity? -> O(n^3)
### Warshall's Algorithm
- Purpose? -> Transitive closure
- Output? -> Reachability matrix
### Dijkstra's Algorithm
- Source node to others? Yes
- Fails with negative weights
### Topological Sorting
- Used for? -> DAGs only
- Application? -> Task scheduling
### 0/1 Knapsack
- Optimal strategy? -> DP
VTU 4th Semester ADA Lab - Complete Study & Viva Workbook
- Greedy fails? -> Yes
### Greedy Knapsack
- Only for? -> Fractional knapsack
### Subset Sum (Backtracking)
- Pruning? -> Avoid extra work
- Time? -> Exponential
### Sorting Algorithms
- Quick Sort: Avg O(n log n), Worst O(n^2)
- Merge Sort: Stable, O(n log n)
- Selection Sort: O(n^2) always
### N-Queens
- Backtracking-based, checks safe positions column-wise.
Algorithm Comparison Tables
## Algorithm Comparison Tables
### Kruskal's vs Prim's Algorithm
| Feature | Kruskal's | Prim's |
|----------------------|-----------------------------------|-----------------------------------|
| Approach | Greedy, edge-based | Greedy, vertex-based |
| Data Structures | Disjoint Set | Min Heap / Priority Queue |
| Works on | Connected & disconnected graphs | Only connected graphs |
| Sorting Required | Yes | No |
| Cycle Detection | Yes (Union-Find) | No |
VTU 4th Semester ADA Lab - Complete Study & Viva Workbook
| Time Complexity | O(E log E) | O(V^2) or O(E + V log V) |
### Dijkstra's vs Floyd's Algorithm
| Feature | Dijkstra's | Floyd's |
|----------------------|-----------------------------------|-----------------------------------|
| Use-case | Single-source shortest paths | All-pairs shortest paths |
| Negative Weights | Not allowed | Allowed (no negative cycles) |
| Time Complexity | O((V + E) log V) | O(V^3) |
### Warshall's vs Floyd's Algorithm
| Feature | Warshall's | Floyd's |
|----------------------|-----------------------------------|-----------------------------------|
| Purpose | Reachability | Shortest distances |
| Graph Type | Unweighted | Weighted |
| Operation | Logical OR | Arithmetic min |
### 0/1 vs Greedy Knapsack
| Feature | 0/1 Knapsack | Fractional Knapsack |
|----------------------|-----------------------------------|-----------------------------------|
| Selection | Take full or leave | Take fractions allowed |
| Approach | Dynamic Programming | Greedy |
| Time Complexity | O(nW) | O(n log n) |
| Always Optimal | Yes | Only in fractional |
### Sorts: Selection vs Quick vs Merge
| Feature | Selection Sort | Quick Sort | Merge Sort |
|----------------------|-----------------------------------|-----------------------------------|-----------------------------------|
VTU 4th Semester ADA Lab - Complete Study & Viva Workbook
| Time Complexity | O(n^2) | Avg O(n log n), Worst O(n^2) | O(n log n) |
| Space Complexity | O(1) | O(log n) (rec stack) | O(n) |
| Stable | No | No | Yes |
### Algorithm Paradigms
| Paradigm | Key Idea | Examples |
|----------------------|-----------------------------------|-----------------------------------|
| Greedy | Local optimum | Kruskal, Prim, Fractional Knapsack|
| Divide & Conquer | Divide -> Solve -> Combine | Quick Sort, Merge Sort |
| Dynamic Programming | Overlapping subproblems | 0/1 Knapsack, Floyd |
| Backtracking | Try/Reject/Backtrack | N-Queens, Subset Sum |
Dry Run Examples
## Dry Run Examples
### Kruskal's Algorithm
Edges: (1,2)=1, (2,3)=2, (1,3)=3
MST: Add 1-2, then 2-3
Output: Cost = 3
### Prim's Algorithm
Graph: 1-2(1), 2-3(2), 1-3(3)
Start at 1 -> pick 1-2, then 2-3
Output: Cost = 3
### Floyd's Algorithm
Matrix update using min(dist[i][j], dist[i][k]+dist[k][j])
All pairs shortest path computed
VTU 4th Semester ADA Lab - Complete Study & Viva Workbook
### Warshall's Algorithm
Logical OR used: reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])
### Dijkstra's Algorithm
Start at 1 -> 1->3=1, then 3->2=2
Output: Shortest 1->2 = 3
### Topological Sort
DAG: 1->2, 1->3, 3->4
Valid Order: 1 2 3 4 or 1 3 2 4
### 0/1 Knapsack
Items: (1,10),(2,15),(3,40), Capacity=5
Pick items 2+3 = 55 profit
### Greedy Knapsack
Same items. Pick 3, then fraction of 2
Max profit = 65.0
### Subset Sum
Set = {2, 4, 6, 10}, d=16
Valid subsets: [2,4,10], [6,10]
### Selection Sort
[5,2,8,1] -> [1,2,5,8]
### Quick Sort
[5,2,8,1] -> pivot partition -> sorted
### Merge Sort
VTU 4th Semester ADA Lab - Complete Study & Viva Workbook
Divide [5,2,8,1], then merge -> [1,2,5,8]
### N-Queens (N=4)
Place queens column-wise checking rows and diagonals.
Output:
#Q##
###Q
Q###
##Q#