Algorithm and Data Structures related questions (Explanation with the answers wi

Question

Algorithm and Data Structures related questions (Explanation with the answers will be appreciated) :

Spring 2014 Multiple Choice. Write the letter of your answer to the LEFT of each problem. 2 points each 1. Suppose a maximum bipartite matching with k edges is found using Edmonds-Karp. Which of the following does not hold? A. The capacity of the minimum cut is k. B. There will be k 1 breadth-first searches. C. All residual network capacities are zero or one. D. Every augmenting path uses three edges. 2. Suppose a depth-first search on a directed graph yields a path of tree edges from vertex X to vertex Y and a path of tree edges from vertex X to Z. If there is also an edge from Yto Z, then its type will be C. Forward A. Back B. Cross D. Tree 3. During a breadth-first search, the status of a gray vertex is: A. It has been completely processed. B. It is in the FIFO queue. C. It is in the priority queue. D. It is undiscovered. 4. The fastest method for finding the diameter of a tree is to A. se the Floyd-Warshall algorithm. B. Use the Ford-Fulkerson algorithm. C. Use breadth-first search. D. Use Dijkstra's algorithm. 5. The capacity of any cut is: A. An upper bound on the maximum flow B. The same as the capacity of all other cuts. C. The same as the maximum attainable flow. D. A lower bound on the maximum flow. 6. Suppose a directed graph has a path from vertex X to vertex Y, but no path from vertex Y to vertex X. The relationship between the finish times for depth-first search is: B. finish(X) finish(Y) A. finish (X) finish(Y) C. finish(X) finish(Y) D. could be either A. or B 7. The relationship of the net flow across a cut and the amount of flow from the source to the sink is: A. They are equal. B. The amount of flow does not exceed the net flow C. The net flow does not exceed the amount of flow D. There is no relationship. 8. What is the number of strongly connected components in this graph? A. 1 B. 2 C. 3 D. 4

Explanation / Answer

3)Ans is B.

BFS colors each vertex to keep its track. Each vertex of the graph is in one of three states:

1. Undiscovered : White

2. Discovered but not fully explored : Grey

3. Fully explored : Black

BFS uses FIFO queue to store Grey vertices.

=================================================================

4)Ans is C.Diameter of tree can be found by BFS.

Ford-Fulkerson Algorithm is used for minimum cut .

floyd warshall algorithm and Dijktra is used for shortest path

===============================================================

7)Ans is D.

net flow across a cut =total flow out of source -total flow in to source

==========================================================

9)Ans is C

Capacity of cut is sum of edges int that cut.

Here 5+10+1=16

======================================

10)Ans is C.

As we have to find minimum spaning tree.Kruskal will sort edges according to weight and choose smallest weight first But they should not belong to same group .this is checked by find() function.If they are in different group then and then they are proceesed.

Here find(x) return poniter to  the set containing x.

======================================================

11)Ans is B.

Edmonds–Karp algorithm is used to find maximum flow in graph.

Its time complexity is O(V E2) .This time complexity comes from showing that each augmenting path can be found in O(E) time

=======================================================================

15)Ans is B

O(ElogV) which is came from O((E+V)logV) in worst case.

Where E is number of edges and V is number of vertices

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.