Design & Analysis of Algorithms

BFS on a graph $G=(V,E)$ has running time:

• (i) $O(|V|+|E|)$
• (ii) $O(|V|)$
• (iii) $O(|E|)$
• (iv) None of the above

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

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $1/2$. What is the expected number of unordered cycles of length three?

• (i) 1/8
• (ii) 1
• (iii) 8
• (iv) 8

Dijkstra's algorithm is used to solve ______ problems?

• (i) Single source shortest path
• (ii) All pair shortest path
• (iii) Sorting
• (iv) Searching

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

• (i) In adjacency list representation, space is saved for sparse graphs.
• (ii) DFS and BFS can be done in $O(V+E)$ time for adjacency list representation. These operations take $O(V^2)$ time in adjacency matrix representation.
• (iii) Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
• (iv) All of the above

Level order traversal of a rooted tree can be done by starting from root and performing:

• (i) Depth first search
• (ii) Breadth first search
• (iii) Pre-order traversal
• (iv) In-order traversal

The approach followed in Floyd Warshall's algorithm is

• (i) Greedy approach
• (ii) Dynamic approach
• (iii) Backtracking
• (iv) Divide and conquer

Which of the following algorithms are used to find the shortest path from a source node to all other nodes in a weighted graph?

• (i) BFS
• (ii) Prim's Algorithm
• (iii) Djikstra's Algorithm
• (iv) Kruskal's Algorithm

The node removal of which makes a graph disconnected is called:

• (i) Pendant vertex
• (ii) Bridge
• (iii) Articulation point
• (iv) Coloured vertex

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

Consider the array $A = \{26, 17, 41, 14, 21, 30, 47, 10, 16, 19, 21, 28, 38, 7, 12, 14, 20, 35, 39, 3\}$. Create binary search tree with one more attribute its size of node. Retrieve 17th smallest element in the tree and rank the 12th element.

You are given a graph containing $n$ vertices and $m$ edges and given that the graph doesn't contain cycle of odd length. What is the time complexity of the best known algorithm to find out whether the graph is bipartite or not?

Solve the single source shortest path problem for the following graph considering '1' as the source vertex using Dijkstra's algorithm. (Graph image reference in source document)

Apply single source shortest path algorithm for the following graph

Explain the max-flow min-cut theorem with an example.

Write short notes on: Topological sorting