Page | 1
CS6515 EXAM 2 2025| BRAND NEW ACTUAL
EXAM WITH 100% VERIFIED QUESTIONS AND
CORRECT SOLUTIONS| GUARANTEED VALUE
PACK| ACE YOUR GRADES.
Kruskal Algorithm - correct answer - Input: connected undirected
graph G, edge weights w
Output: minimum spanning tree defined by the edges
Runtime: O(m log(m)) or O(m log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
How it works: Basically Sorts edges from least to greatest and
starts building the tree.
Prim's Algorithm - correct answer - Runtime: O(m log(m)) or O(m
log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
Output: The Minimum Spanning Tree of the graph.
, Page | 2
How it works: Starts at a vertex and adds the smallest connecting
edge to unvisited node.
Ford Fulkerson Algorithm - correct answer - Runtime: O(mC)
Input: Graph with integer edge weights. (Note: Does not work with
Infinity)
Output: max flow f*
Edmonds-Karp Algorithm - correct answer - Runtime: O(nm^2)
Input: Graph with integer edge weights. (Note: Works with
Infinity!)
Output: max flow f*
Orlin Max Flow Algorithm - correct answer - - Current best
solution to max flow problem
- Run Time: O(mn)
Augmenting Path - correct answer - A path that exists on the
residual graph from s -> t.
, Page | 3
This type of path implies there exists more flow that can be
pushed through the graph.
This occurs when there exists a path through which the minimum
residual capacity F among all edges in the path is greater than 0.
When is a flow a max flow - correct answer - When there is no
augmenting path in the residual graph
Size(flow) = - correct answer - F_out(L) - f_in(L)
How to construct a min cut - correct answer - - construct a max
flow
- set L to be those vertices reachable from s in the residual graph
- This st cut then has a capacity equal to the max flow
- maxflow = mincut
Ford-Fulkerson vs Edmonds-Karp - correct answer - FF:
- Finds augmenting paths using DFS or BFS
- O(mC) time, where C is the size of the max flow
CS6515 EXAM 2 2025| BRAND NEW ACTUAL
EXAM WITH 100% VERIFIED QUESTIONS AND
CORRECT SOLUTIONS| GUARANTEED VALUE
PACK| ACE YOUR GRADES.
Kruskal Algorithm - correct answer - Input: connected undirected
graph G, edge weights w
Output: minimum spanning tree defined by the edges
Runtime: O(m log(m)) or O(m log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
How it works: Basically Sorts edges from least to greatest and
starts building the tree.
Prim's Algorithm - correct answer - Runtime: O(m log(m)) or O(m
log(n))
Input: Connected, undirected graph. (Must have edge weights...
basis of algo)
Output: The Minimum Spanning Tree of the graph.
, Page | 2
How it works: Starts at a vertex and adds the smallest connecting
edge to unvisited node.
Ford Fulkerson Algorithm - correct answer - Runtime: O(mC)
Input: Graph with integer edge weights. (Note: Does not work with
Infinity)
Output: max flow f*
Edmonds-Karp Algorithm - correct answer - Runtime: O(nm^2)
Input: Graph with integer edge weights. (Note: Works with
Infinity!)
Output: max flow f*
Orlin Max Flow Algorithm - correct answer - - Current best
solution to max flow problem
- Run Time: O(mn)
Augmenting Path - correct answer - A path that exists on the
residual graph from s -> t.
, Page | 3
This type of path implies there exists more flow that can be
pushed through the graph.
This occurs when there exists a path through which the minimum
residual capacity F among all edges in the path is greater than 0.
When is a flow a max flow - correct answer - When there is no
augmenting path in the residual graph
Size(flow) = - correct answer - F_out(L) - f_in(L)
How to construct a min cut - correct answer - - construct a max
flow
- set L to be those vertices reachable from s in the residual graph
- This st cut then has a capacity equal to the max flow
- maxflow = mincut
Ford-Fulkerson vs Edmonds-Karp - correct answer - FF:
- Finds augmenting paths using DFS or BFS
- O(mC) time, where C is the size of the max flow
