Test by Bikram | Algorithms | Test 2 | Question: 14

Question

Match the following:
$\begin{array}{|l|l|l|l|} \hline (1) & \text{Multistage graph} & (P) & \text{Divide and conquer}\\ \hline (2) & \text{Convex hull } & (Q) & \text{Depth first search} \\ \hline (3) & \text{Bi-connected components} & (R) & \text{Greedy method} \\ \hline (4) & \text{Knapsack problem} & (S) & \text{Dynamic programming} \\ \hline (5) & \text{All pairs shortest path} & \text{}\\\hline \end{array}$    

• A. 1 – Q, 2 – P, 3 – Q,  4– R,  5 – S
• B. 1 - Q,  2 - R, 3 - Q,  4 - P,  5 – S
• C. 1 - S,  2 – R, 3 - Q,  4– R,  5 – S
• D. 1 - S,  2 - P,  3 – Q,  4– R,  5 – S

Comments

multistage graph and convex hull in syllabus?

---

multistage graph and convex hull syllabus in ...

Answer 1

Multistage graph  :Dynamic Programming as it needs to see all the possibilities from each vertex to mark the vertex as source or sink

Convex hull  :Divide and Conquer as its algorithm divides the problem in upper convex and lower convex

Bi-connected components :Depth first search as Idea is to store visited edges in a stack while DFS on a graph and keep looking for Articulation Points(highlighted in above figure). As soon as an Articulation Point u is found, all edges visited while DFS from node u onwards will form one biconnected component. When DFS completes for one connected component, all edges present in stack will form a biconnected component.If there is no Articulation Point in graph, then graph is biconnected and so there will be one biconnected component which is the graph itself.

Knapsack problem :Greedy method as the knapsack needs to be filled with maximum profit possible.

All pairs shortest path: Dynamic programming as it needs to check all the possibilities from each vertex for shortest path

therefore Option D is correct

Answer 2

I am confused between C and D

all pair shortest path --dynamic programming

knapsack -- greedy

connected component--dfs

multistage graph=dynamic programming

what is meant by hull