CS 6515 EXAM 2 QUESTIONS WITH CORRECT ANSWERS LATEST UPDATE 2026
Basic Properties of Trees - 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 - 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? - Answers No
Flow Network Constraints: Capacity Constraint - Answers For all edges, the flow must be larger than
zero, but less than the capacity of that edge
Goal of Flow Problem - 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 - 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 - 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 - 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 - 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 - 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 - Answers Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut - Answers Size of Max-flow = min capacity of a st-cut
Cut Property: Key Ideas - 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 - Answers O(1)
Runtime: Confirm edge exists - Answers O(m)
Runtime: Explore entire graph - Answers O(n + m)
x mod N = - Answers x = qN + r
Basic Properties of MOD - 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 - Answers O(n^2)
Modular Inverse - 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 - 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 - Answers - 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 - Answers - 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 - Answers - Alpha is the inverse of x MOD y
- Beta is the inverse of y MOD x
Fermat's Little Theorem - Answers - 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 - Answers - for any N,z where gcd(z, N) = 1; that is they are relatively prime:
- then z^(phi(n)) = 1 mod N
phi(N) = # of integers between 1 & N which are relatively prime to N
phi(N) - is called Euler's totient function
Note: Euler's Theorem is a generalization of Fermat's little theorem for arbitrary N
RSA Protocol - Answers 1. Bob picks 2 n-bit random primes p & q
2. Bob chooses e relatively prime to (p-1)(q-1)
3. Bob publishes his public key (p*q, e)
4. Bob computes his private key: d ::: e^-1 mod (p-1)(q-1)
1. Alice looks up Bob's public key (pq, e)
2. Alice computes y:::m^e MOD N
1. Bob receives y
2. Bob decrypted: computes y^d MOD N ::: m
RSA Pitfalls - Answers 1. If gcd(m, N) > 1, crypto system is broken
2. m is not too large (m < N)
3. m is not too small, MOD N doesn't do anything
- send m and r, padding message by m + r
4. send same m, e times
- can decrypt message using Chinese remainder theorem
Fermat's Test - Answers - Find z where z ^(r-1) != 1 mod r
--> r is composite
- This is called a Fermat Witness
--> every composite has a Fermat Witness
Trivial Fermat Witness - Answers Passes Fermat's test and z where gcd (z, r) > 1. Trivial since don't
really need to run Fermat's Test.
Non-trivial Fermat Witness - Answers - z where gcd(z, r) = 1 that also passes Fermat's Test (z^(r-1) ::: 1
mod r)
- if this is the case, then a composite number has many Fermat Witnesses; thus they are easy to find
Charmichael Numbers - Answers - Pseudoprimes
- Composite # with No nontrivial Fermat Witnesses
- Inefficient to use Fermat's Test to prove a number is a composite number
Basic Properties of Trees - 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 - 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? - Answers No
Flow Network Constraints: Capacity Constraint - Answers For all edges, the flow must be larger than
zero, but less than the capacity of that edge
Goal of Flow Problem - 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 - 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 - 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 - 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 - 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 - 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 - Answers Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut - Answers Size of Max-flow = min capacity of a st-cut
Cut Property: Key Ideas - 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 - Answers O(1)
Runtime: Confirm edge exists - Answers O(m)
Runtime: Explore entire graph - Answers O(n + m)
x mod N = - Answers x = qN + r
Basic Properties of MOD - 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 - Answers O(n^2)
Modular Inverse - 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 - 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 - Answers - 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 - Answers - 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 - Answers - Alpha is the inverse of x MOD y
- Beta is the inverse of y MOD x
Fermat's Little Theorem - Answers - 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 - Answers - for any N,z where gcd(z, N) = 1; that is they are relatively prime:
- then z^(phi(n)) = 1 mod N
phi(N) = # of integers between 1 & N which are relatively prime to N
phi(N) - is called Euler's totient function
Note: Euler's Theorem is a generalization of Fermat's little theorem for arbitrary N
RSA Protocol - Answers 1. Bob picks 2 n-bit random primes p & q
2. Bob chooses e relatively prime to (p-1)(q-1)
3. Bob publishes his public key (p*q, e)
4. Bob computes his private key: d ::: e^-1 mod (p-1)(q-1)
1. Alice looks up Bob's public key (pq, e)
2. Alice computes y:::m^e MOD N
1. Bob receives y
2. Bob decrypted: computes y^d MOD N ::: m
RSA Pitfalls - Answers 1. If gcd(m, N) > 1, crypto system is broken
2. m is not too large (m < N)
3. m is not too small, MOD N doesn't do anything
- send m and r, padding message by m + r
4. send same m, e times
- can decrypt message using Chinese remainder theorem
Fermat's Test - Answers - Find z where z ^(r-1) != 1 mod r
--> r is composite
- This is called a Fermat Witness
--> every composite has a Fermat Witness
Trivial Fermat Witness - Answers Passes Fermat's test and z where gcd (z, r) > 1. Trivial since don't
really need to run Fermat's Test.
Non-trivial Fermat Witness - Answers - z where gcd(z, r) = 1 that also passes Fermat's Test (z^(r-1) ::: 1
mod r)
- if this is the case, then a composite number has many Fermat Witnesses; thus they are easy to find
Charmichael Numbers - Answers - Pseudoprimes
- Composite # with No nontrivial Fermat Witnesses
- Inefficient to use Fermat's Test to prove a number is a composite number
