CS6515 EXAM 2 QUESTIONS & ANSWERS
Basic Properties of Trees - Answer -Tree's are undirected, connected and acyclic that
connect all nodes.
1. Tree on n vertices has (n-1) edges -> would have a cycle otherwise (more than n-1
edges means cycle)
2. In tree exactly one path between every pair of vertices (otherwise it's not connected)
- More than 1 path implies cycle
- less than 1 path implies not connected
3. Any connected G(V, E) with |E| = |V| - 1 is a tree
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)
Runtime: Confirm edge exists - Answer -O(m)
Runtime: Explore entire graph - Answer -O(n + m)
x mod N = - Answer -x = qN + r
Basic Properties of MOD - Answer -if x:::y MOD N & a:::b MOD N:
1. x+a ::: y+b MOD N
2. xa ::: yb MODN N
Time to multiply or divide 2 n-bit numbers - Answer -O(n^2)
Modular Inverse - Answer -X is the multiplicative inverse of Z MOD N if:
- (x * z) MOD N = 1
Notation:
x:::z^-1 MOD N
z::::x^-1 MOD N
When does the inverse of x MOD N exist - Answer -When GCD(x, N) = 1. That is x and
N don't share a common divisor and are thus "relatively prime"
Basic Properties of Trees - Answer -Tree's are undirected, connected and acyclic that
connect all nodes.
1. Tree on n vertices has (n-1) edges -> would have a cycle otherwise (more than n-1
edges means cycle)
2. In tree exactly one path between every pair of vertices (otherwise it's not connected)
- More than 1 path implies cycle
- less than 1 path implies not connected
3. Any connected G(V, E) with |E| = |V| - 1 is a tree
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)
Runtime: Confirm edge exists - Answer -O(m)
Runtime: Explore entire graph - Answer -O(n + m)
x mod N = - Answer -x = qN + r
Basic Properties of MOD - Answer -if x:::y MOD N & a:::b MOD N:
1. x+a ::: y+b MOD N
2. xa ::: yb MODN N
Time to multiply or divide 2 n-bit numbers - Answer -O(n^2)
Modular Inverse - Answer -X is the multiplicative inverse of Z MOD N if:
- (x * z) MOD N = 1
Notation:
x:::z^-1 MOD N
z::::x^-1 MOD N
When does the inverse of x MOD N exist - Answer -When GCD(x, N) = 1. That is x and
N don't share a common divisor and are thus "relatively prime"
