Design and Analysis of Algorithms

An adjacency matrix representation of a graph cannot contain information of
(i) nodes
(ii) edges
(iii) direction of edges
(iv) parallel edges

The minimum number of colors needed to color a graph having $n > 3$ vertices and 2 edges is
(i) 2
(ii) 3
(iii) 4
(iv) 1

Which of the following algorithms is used to find the minimum spanning tree in a weighted undirected graph?
(i) Dijkstra's algorithm
(ii) Kruskal's algorithm
(iii) Bellman-Ford algorithm
(iv) Floyd-Warshall algorithm

BFS on a graph $G = (V, E)$ has running time
(i) $O(|V| + |E|)$
(ii) $O(|V|)$
(iii) $O(|E|)$
(iv) None of these

In DFS traversal of a graph, which data structure is used to keep track of visited nodes?
(i) Queue
(ii) Stack
(iii) Priority Queue
(iv) Heap

In an unweighted graph, which algorithm is guaranteed to find the shortest path between two nodes?

(i) Depth First Search
(ii) Kruskal's Algorithm
(iii) Breadth First Search
(iv) Prim's Algorithm

Which algorithm is used to find a Minimum Spanning Tree?
(i) Dijkstra's algorithm
(ii) Prim's algorithm
(iii) Bellman-Ford algorithm
(iv) Floyd-Warshall algorithm

Which of the following algorithms is commonly used to find the Minimum Spanning Tree of a graph?

(i) Dijkstra's Algorithm
(ii) Kruskal's Algorithm
(iii) Bellman-Ford Algorithm
(iv) Floyd-Warshall Algorithm

Which of the following algorithm solves the All Pair Shortest Path problem
(i) Dijkstra's
(ii) Floyd's Warshall's
(iii) Prim's
(iv) Kruskal's

Topological sorting is only possible in:
(i) Undirected Graphs
(ii) Trees
(iii) Directed Acyclic Graphs
(iv) Weighted Graphs

If all edge weights in a graph are positive, what is the minimum number of edges in a spanning tree for a graph with vertices?

(i) V
(ii) V-1
(iii) V+1
(iv) 2V

Which algorithm is typically used in maximum flow problems?
(i) Kruskal's Algorithm
(ii) Floyd-Warshall
(iii) Ford-Fulkerson
(iv) Prim's Algorithm

What is the time complexity of topological sorting of a directed acyclic graph (DAG) with $V$ vertices and $E$ edges using Depth-First Search (DFS)?
(i) $O(V^2)$
(ii) $O(E^2)$
(iii) $O(V+E)$
(iv) $O(V.E)$

Give step by step procedure to find minimal spanning tree for the given graph.

What is a Minimum Cost Spanning tree? Explain Kruskal's Minimum cost spanning tree algorithm with a suitable example.

Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm.

Answer the following:
(i) Compare and contrast the BFS and DFS traversal techniques in terms of their algorithmic approach, time complexity, data structures used, and typical applications.
(ii) Give examples where one is preferred over the other.

Explain BFS algorithm in detail. Also explain its time complexity.

Design a system that finds the shortest paths between various locations in a city. The locations and roads are represented using a graph. What algorithm would you use if:
(i) All roads have equal length
(ii) Roads have varying lengths, but no negative lengths
(iii) Some roads have negative lengths
Justify your choices with suitable algorithms and reasoning.

Explain how Bellman Ford algorithm can be used to detect the presence of negative weight cycles.

In the below given weighted graph W (Given in form of matrix), apply Bellman Ford's algorithm to find the shortest distances from source node 3. Write the time complexity of Bellman Ford's algorithm.

	1	2	3	4	5
1	0	1	8	1	4
2	1	0	12	4	9
3	8	12	0	7	3
4	1	4	7	0	2
5	4	9	3	2	0

A graph with five nodes is represented using the adjacency list as follows:

A	->	B (10)	C (3)
B	->	C (1)	D (5)
C	->	B (4)	D (8)	E (2)
D	->	E (7)
E	->	D (9)

Answer the following:
(i) Draw the graph for the above adjacency list.
(ii) Write the algorithm for the Breadth-First Traversal (BFS).
(iii) Show the BFS traversal of the graph with the starting node as A.

Explain the Prim's algorithm. What is the time complexity of Prim's algorithm?

What is minimum spanning tree (MST)? Explain the steps of Prim's algorithm to find the MST using an example.

Write the Pseudo-code for the Dijkstra's Algorithm. Further, find the single source (A) shortest path on the following graph:

Apply the Prim's algorithm and find the optimal solution for the following graph:

What is negative weight-cycle? Write Bellman-Ford algorithm to find single source shortest distance of a directed graph.

Discuss the differences between BFS and DFS in terms of traversal order, memory usage, and their applications in real-world problems.

Answer the following:
(i) Explain the concept of a Minimum Spanning Tree (MST) in a connected, weighted, undirected graph.
(ii) Compare and contrast Prim's and Kruskal's algorithms for finding the MST.
(iii) Analyze the time complexity of both algorithms and discuss their advantages and scenarios where one is preferred over the other.

Given the flow network below with capacities:

EDGE	CAPACITY
S -> A	10
S -> C	10
A -> B	4
A -> C	2
C -> D	9
B -> T	10
D -> B	6
D -> T	10

Answer the following:
(i) Use the Ford-Fulkerson algorithm to find the maximum flow from source (S) to sink (T).
(ii) Show the augmenting paths selected, the bottleneck capacities on each path, and the updated residual capacities after each augmentation.
(iii) Calculate the final maximum flow value.