CS6515 EXAM 2 CERTIFICATION SCRIPT
2026 QUESTIONS WITH ANSWERS GRADED
A+
⩥ Kruskal's Algorithm. Answer: 1. Sort E by increasing weigt
2. Go through edges in order and add an edge to our current tree if it
doesn't create a cycle
Running Time: O(m log n), m = |E|, n = |V|
⩥ Is there ever a reason to use cycles in a flow graph?. Answer: No
⩥ Flow Network Constraints: Capacity Constraint. Answer: For all
edges, the flow must be larger than zero, but less than the capacity of
that edge
⩥ Goal of Flow Problem. Answer: Maximize the flow out of the source
(or into the sink) of maximum size while satisfying the capacity and
conservation of flow constraints.
⩥ Flow Network Constraints: Conservation of Flow. Answer: For all
vertices (other than the starting (source) and ending (sink) vertices), the
flow into v must equal the flow out of v.
,⩥ Ford-Fulkerson Algo. Answer: 1. Start with f_e = 0 for all edges
2. Build the residual network for current flow
3. Find st-path in residual network
- if no such path then output f
4. Let c(p) = min(c_e - f_e); this is available capacity along some path
5. Augment f by c(p) along p
- for forward edges increase flow by c(p)
- for backward edge, decrease flow by c(p)
6. Repeat
⩥ Residual Network. Answer: For flow network G = (V, E) with c_e for
edges and f_e for flows:
1. If there exists an edge vw where f_vw < c_vw, add vw to residual
network with capacity c_vw - f_aw
2. If there exists an edge vw where f_vw > 0, then add wv to residual
network with capacity f_vw
Note: 1 shows available forwards capacities and 2 shows residual
backward capacities.
, ⩥ Ford-Fulkerson Runtime. Answer: Need to assume all capacities are
integers. This will allow flow to always increase by at least 1 unit per
round. If C is the maxflow, then there are at most C rounds. Each round
of FF takes O(m), so the total time is O(mC), which is pseudo-
polynomial
⩥ What is the time to check whether or not a flow is a max flow.
Answer: - O(n + m)
1. Build the residual graph takes O(n + m) time
2. Checking if there's a path from s to t using DFS, which takes linear
time.
⩥ Capacity of a Cut. Answer: Sum of capacities (edges) going from cut
L to cut R
⩥ Max-flow = Min st-cut. Answer: Size of Max-flow = min capacity of
a st-cut
⩥ Cut Property: Key Ideas. Answer: 1. Take a tree T, add an edge e* will
create a cycle. Removing any edge of the cycle we'll get a new tree
2. A minimum weight edge across a cut is part of a MST
⩥ Runtime: Confirm a vertex exists. Answer: O(1)
2026 QUESTIONS WITH ANSWERS GRADED
A+
⩥ Kruskal's Algorithm. Answer: 1. Sort E by increasing weigt
2. Go through edges in order and add an edge to our current tree if it
doesn't create a cycle
Running Time: O(m log n), m = |E|, n = |V|
⩥ Is there ever a reason to use cycles in a flow graph?. Answer: No
⩥ Flow Network Constraints: Capacity Constraint. Answer: For all
edges, the flow must be larger than zero, but less than the capacity of
that edge
⩥ Goal of Flow Problem. Answer: Maximize the flow out of the source
(or into the sink) of maximum size while satisfying the capacity and
conservation of flow constraints.
⩥ Flow Network Constraints: Conservation of Flow. Answer: For all
vertices (other than the starting (source) and ending (sink) vertices), the
flow into v must equal the flow out of v.
,⩥ Ford-Fulkerson Algo. Answer: 1. Start with f_e = 0 for all edges
2. Build the residual network for current flow
3. Find st-path in residual network
- if no such path then output f
4. Let c(p) = min(c_e - f_e); this is available capacity along some path
5. Augment f by c(p) along p
- for forward edges increase flow by c(p)
- for backward edge, decrease flow by c(p)
6. Repeat
⩥ Residual Network. Answer: For flow network G = (V, E) with c_e for
edges and f_e for flows:
1. If there exists an edge vw where f_vw < c_vw, add vw to residual
network with capacity c_vw - f_aw
2. If there exists an edge vw where f_vw > 0, then add wv to residual
network with capacity f_vw
Note: 1 shows available forwards capacities and 2 shows residual
backward capacities.
, ⩥ Ford-Fulkerson Runtime. Answer: Need to assume all capacities are
integers. This will allow flow to always increase by at least 1 unit per
round. If C is the maxflow, then there are at most C rounds. Each round
of FF takes O(m), so the total time is O(mC), which is pseudo-
polynomial
⩥ What is the time to check whether or not a flow is a max flow.
Answer: - O(n + m)
1. Build the residual graph takes O(n + m) time
2. Checking if there's a path from s to t using DFS, which takes linear
time.
⩥ Capacity of a Cut. Answer: Sum of capacities (edges) going from cut
L to cut R
⩥ Max-flow = Min st-cut. Answer: Size of Max-flow = min capacity of
a st-cut
⩥ Cut Property: Key Ideas. Answer: 1. Take a tree T, add an edge e* will
create a cycle. Removing any edge of the cycle we'll get a new tree
2. A minimum weight edge across a cut is part of a MST
⩥ Runtime: Confirm a vertex exists. Answer: O(1)
