CS 6515 EXAM 2 CERTIFICATION EVALUATION TESTED QUESTIONS FULL SOLUTION GUIDE
Question:
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|
Question:
Is there ever a reason to use cycles in a flow graph?
Answer:
No
Question:
Flow Network Constraints: Capacity Constraint.
Answer:
For all edges, the flow must be larger than zero, but less than the capacity of that edge
Question:
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.
, Question:
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.
Question:
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
Question:
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.
Question:
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
Question:
Question:
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|
Question:
Is there ever a reason to use cycles in a flow graph?
Answer:
No
Question:
Flow Network Constraints: Capacity Constraint.
Answer:
For all edges, the flow must be larger than zero, but less than the capacity of that edge
Question:
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.
, Question:
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.
Question:
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
Question:
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.
Question:
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
Question:
