CS6515 Exam 2 || 100% Accurate Answers.
Basic Properties of Trees correct answers 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 correct answers 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? correct answers No
Flow Network Constraints: Capacity Constraint correct answers For all edges, the flow must be
larger than zero, but less than the capacity of that edge
Goal of Flow Problem correct answers 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 correct answers 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 correct answers 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 correct answers 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 correct answers 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 correct answers - 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 correct answers Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut correct answers Size of Max-flow = min capacity of a st-cut
Cut Property: Key Ideas correct answers 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 correct answers O(1)
Runtime: Confirm edge exists correct answers O(m)
Runtime: Explore entire graph correct answers O(n + m)
x mod N = correct answers x = qN + r
Basic Properties of MOD correct answers 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 correct answers O(n^2)
Modular Inverse correct answers 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 correct answers When GCD(x, N) = 1. That is x and N
don't share a common divisor and are thus "relatively prime"
Properties of Modular Inverses correct answers - if x^-1 MOD N exists, then it's unique
- x^-1 MOD N doesn't exist when gcd(x, N) > 1
Basic Properties of Trees correct answers 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 correct answers 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? correct answers No
Flow Network Constraints: Capacity Constraint correct answers For all edges, the flow must be
larger than zero, but less than the capacity of that edge
Goal of Flow Problem correct answers 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 correct answers 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 correct answers 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 correct answers 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 correct answers 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 correct answers - 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 correct answers Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut correct answers Size of Max-flow = min capacity of a st-cut
Cut Property: Key Ideas correct answers 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 correct answers O(1)
Runtime: Confirm edge exists correct answers O(m)
Runtime: Explore entire graph correct answers O(n + m)
x mod N = correct answers x = qN + r
Basic Properties of MOD correct answers 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 correct answers O(n^2)
Modular Inverse correct answers 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 correct answers When GCD(x, N) = 1. That is x and N
don't share a common divisor and are thus "relatively prime"
Properties of Modular Inverses correct answers - if x^-1 MOD N exists, then it's unique
- x^-1 MOD N doesn't exist when gcd(x, N) > 1
