CS6515 Exam 2 Questions And Complete Solutions

CS6515 Exam 2 Questions And Complete Solutions 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" Properties of Modular Inverses - ANSWER -- if x^-1 MOD N exists, then it's unique - x^-1 MOD N doesn't exist when gcd(x, N) > 1 Euclid's Rule - ANSWER -- If x >= y > 0: - gcd(x, y) = gcd(x MOD y, y) Note: For Euclid's also that gcd(x, 0) = x Extended-Euclid's algorithm alpha and beta output params - ANSWER -- Alpha is the inverse of x MOD y - Beta is the inverse of y MOD x Fermat's Little Theorem - ANSWER -- If p is prime then for every 1 <= z <= p - 1: - z ^ (p-1) ::: 1 MOD P Note: since 1 <= z <= p - 1 that the gcd(z, p) = 1; they are relatively prime Euler's Theorem - ANSWER -- for any N,z where gcd(z, N) = 1; that is they are relatively prime: - then z^(phi(n)) = 1 mod N