Fall 22

Question 1

Which algorithm is used to find the augmenting path in Edmonds-Karl

Answer 1

BFS

Question 2

Which algorithm can be used to find the maximum matching of a bipartite graph

Answer 2

Network flow

Question 3

Which algorithm can be used to identify the connected components of an unweighted, undirected graph in O(V+E) time

Answer 3

BFS or DFS

Question 4

Which algorithm is used when you are processing the sorted edges in Kruskal’s algorithm

Answer 4

Disjoint sets

Question 5

I have a network of pipes that connect junctions. Each pipe has a length and a diameter. In my control center, I can turn pipes on and off. I am at junction A, and I have been given a chemical that will improve the longevity of each junction. I want to deliver the chemical to each junction. The problem is that the chemical corroded the pipes, so I want to minimize the inner surface area of pipes that the chemical touches. What algorithm should I use?

Answer 5

Minimum spanning tree of a weighted graph

Question 6

Which algorithm can be used to find the minimum cut of a weighted graph?

Answer 6

Network flow

Question 7

You have:
FBRRBABABBB

What is the pivot using median of 3

Answer 7

B