Data Structure And Algorithm : Practice Questions and Answers

The first people to formulate the Maximum flow problem were T.E. Harris and F.S. Ross.

Each augmenting step takes O(|E|) using an unweighted shortest path algorithm, yielding an O(|E|²|V|) bound on the running time.

True. Dinic's algorithm includes construction of level graphs and residual graphs and finding of augmenting paths along with blocking flow, and is faster than the Ford-Fulkerson algorithm.

An augmenting path can be found in O(|E|) time by an unweighted shortest path algorithm.

An augmenting path between source and sink is a simple path without cycles. A path consisting of zero slack edges is called a critical path.

A vertex can combine and distribute flow in any manner but it should not violate edge capacities and it should maintain flow conservation.

The first step in the naive greedy algorithm is to start with the zero flow, followed by adding edges with higher values.

Ford-Fulkerson algorithm uses the idea of residual graphs, which is an extension of the naive greedy approach allowing undo operations.

The Ford-Fulkerson algorithm is used to compute the maximum feasible flow between a source and a sink in a network.

A vertex with no incoming edges is called a source. A vertex with no leaving edges is called a sink.

True. A network can have only one source and one sink in order to find the feasible flow in a weighted connected graph.

The maximum flow problem involves finding a feasible flow between a source and a sink in a network that is maximum, not minimum.

The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp and naive pattern searching algorithm have the same worst case time complexity.

The auxiliary space complexity required by naive pattern searching algorithm is O(1). So it qualifies as an in place algorithm.

Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for maintaining Z array.

Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n) where m is the length of text and n is the length of the pattern.

KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.

After each call in the recursive algorithm, the size of n is reduced by 1. Therefore the optimal solution is T(n-1)+c.