Give a sequence of m Make-Set, Union, and Find-Set
operations, n of which 5 are Make-Set, that takes
O(m*log(n)) time when we use union by rank only.

a. Consider the quick-union algorithm for diSoint sets.
Explain why if all the 3finds are done before all the unions,
a sequence of operations is guaranteed to take O(n) ame.

Find the greatest common divisor d of 88 and 16, and find integers x and y 2 solving the equation 88x + 16y = d.

Factor 31861 using the Pollard Rho method with
polynomial f(x) + 4

1 and initial guess xo = 1.
PART B
a. Given a flow network G = (V, E) with source s and sink t, a cut (S,T) is a4
partition Of Vinto 5 and T = ‏ا‎ 5 such that 5 ಆ
8, t € 7. Let (S,T) be a cut of a flow network.
Let C be a subset of T such that t e C. Let D=T

— C. Consider the following statement about the
flow network:' (S, C) +

where f£(X, ४) = {1 (श+ y)and £(X, y)denotes the flow from
vertex x to vertex y.
http: /Gvvww.ktuonline.com

Either prove the statement or provide a counterexample.

b. Working modulo q = 3, how many spurious hits does the
Rabin-Karp matcher 3 encounter in the text T =
4126719021586 when looking for the pattern P = 125?

c. Define P, NP and NP-complete problems. Give an example
for each. 2

a. State and prove Maxflow-Mincut theorem. 4

∙ 3
Show the result of executing the Ford-Fulkerson algorithm
on the flow network below, where node s is the source and

node t is the sink. What is the value of the maximum flow
from s to t?