Match List 1 with List 2 and choose the correct answer from the code given below: List I (Graph Algorithm) List II (Time Complexity) a) Dijkstra’s algorithm i) Θ(E log E) b) Kruskal’s algorithm ii) Θ(V 3) c) Floyd-Warshall algorithm iii) Θ(V 2) d) Topological sorting iv) Θ(V + E) Where V and E are the number of vertices and edges in graph respectively.
(a)-(iii), (b)-(i), (c)-(ii), (d)-(iv)
Matching Graph Algorithms with Time Complexities
The question asks us to match standard graph algorithms with their typical time complexities. Understanding the efficiency of these algorithms is crucial in computer science and graph theory.
Let's analyze each algorithm and its time complexity:
- Dijkstra’s algorithm: This algorithm finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. Its time complexity depends on the data structure used for the priority queue.
- Using a simple array or list: $\Theta(V^2)$
- Using a binary heap priority queue: $\Theta((E+V)\log V)$ or $\Theta(E\log V)$ if every vertex is reachable.
- Using a Fibonacci heap priority queue: $\Theta(E + V\log V)$
- Kruskal’s algorithm: This algorithm finds a Minimum Spanning Tree (MST) for a connected, undirected graph. It works by sorting all the edges in non-decreasing order of their weights and adding the edge to the MST if it does not form a cycle with the previously added edges.
- Sorting edges takes $\Theta(E \log E)$.
- Using a Union-Find data structure to check for cycles and union sets takes nearly constant time on average per edge ($\alpha(V)$). The total time for Union-Find operations is $\Theta(E\alpha(V))$.
- Floyd-Warshall algorithm: This algorithm finds the shortest paths between all pairs of vertices in a graph, including graphs with negative edge weights (but no negative cycles). It is a dynamic programming algorithm that uses an adjacency matrix representation.
- The algorithm involves three nested loops, each iterating up to $V$ times.
- Topological sorting: This algorithm produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $(u, v)$, vertex $u$ comes before vertex $v$ in the ordering.
- It can be implemented using Depth First Search (DFS) or Kahn's algorithm (using in-degrees and a queue).
- Both methods visit each vertex and each edge exactly once.
Based on the analysis, the correct matches are:
- (a) Dijkstra’s algorithm: (iii) $\Theta(V^2)$
- (b) Kruskal’s algorithm: (i) $\Theta(E \log E)$
- (c) Floyd-Warshall algorithm: (ii) $\Theta(V^3)$
- (d) Topological sorting: (iv) $\Theta(V + E)$
Let's check the given options against our findings:
| Algorithm | Matches with Complexity |
|---|---|
| (a) Dijkstra’s | (iii) $\Theta(V^2)$ |
| (b) Kruskal’s | (i) $\Theta(E \log E)$ |
| (c) Floyd-Warshall | (ii) $\Theta(V^3)$ |
| (d) Topological sorting | (iv) $\Theta(V + E)$ |
Comparing this with the provided options, we look for the one that matches (a)-(iii), (b)-(i), (c)-(ii), (d)-(iv).
Option 3 is (a)-(iii), (b)-(i), (c)-(ii), (d)-(iv).
Revision Table: Graph Algorithm Time Complexities
| Graph Algorithm | List II Complexity | Description |
|---|---|---|
| Dijkstra’s algorithm | $\Theta(V^2)$ or $\Theta(E\log V)$ | Single-source shortest paths (non-negative weights). $\Theta(V^2)$ is common for adjacency matrix or simple priority queue. |
| Kruskal’s algorithm | $\Theta(E \log E)$ or $\Theta(E \log V)$ | Minimum Spanning Tree. Dominated by edge sorting. |
| Floyd-Warshall algorithm | $\Theta(V^3)$ | All-pairs shortest paths (allows negative weights, but no negative cycles). Dynamic programming approach. |
| Topological sorting | $\Theta(V + E)$ | Linear ordering of vertices in a DAG. Based on DFS or in-degrees. |
Additional Information on Graph Algorithm Efficiency
Time complexity is a measure of how the running time of an algorithm increases with the size of the input. For graph algorithms, the input size is typically represented by the number of vertices ($V$) and the number of edges ($E$).
- Asymptotic Notation: The $\Theta$ (Theta) notation used here describes the average or tight bound on the time complexity, representing both the lower bound and the upper bound of the algorithm's running time.
- Graph Representation: The choice of graph representation (adjacency matrix or adjacency list) can affect the time complexity of some algorithms. For example, Dijkstra's is $\Theta(V^2)$ with an adjacency matrix but $\Theta(E\log V)$ with an adjacency list and a binary heap. Kruskal's complexity is generally independent of the representation because it works with a list of edges.
- Dense vs. Sparse Graphs: A dense graph has many edges ($E$ is close to $V^2$), while a sparse graph has relatively few edges ($E$ is much smaller than $V^2$, possibly close to $V$).
- For dense graphs, $\Theta(V^2)$ might be comparable to or better than $\Theta(E \log V)$.
- For sparse graphs, algorithms with complexities like $\Theta(E \log V)$ or $\Theta(V+E)$ are often more efficient than $\Theta(V^2)$ or $\Theta(V^3)$.
Important Questions from Introduction
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, n and m are number of vertices and edges, respectively. Match each algorithm with its time complexity.
List I List II Standard graph algorithms Time complexities A. Bellman‐Ford algorithm I. O(m*log n) B. Kruskal’s algorithm II. O(n 3) C. Floyd‐Warshall algorithm III. O(n*m) D. Topological sorting IV. O(n + m) Choose the correct answer from the options given below :
How many cards must be selected from a standard deck of 52 cards to guarantee that at least three hearts are present among them?
The solution of recurrence relation: T(n)=2T(sqrt(n)) + lg(n) is
Modulus of elasticity of concrete, E is calculated using:
In how many types can R.C.C. be classified into?
