റാവു

i. Give a sequence of seven unions that produces a tree whose height is as large
as possible. Your answer should be a sequence of procedure calls of the form
Union (a,b) where a and b are integers between | and 8. Draw the resulting tree.

ii. Give a sequence of seven unions, on the original eight sets, that produces a tree
of minimum height. Draw the resulting tree.
iii. Explain why both the min- and max-height trees use seven unions.

3. a. Describe an algorithm that can sometimes detect whether a large integer (say, of 3 100
or 200 digits) is composite. It is important that your algorithm be more practical than, say,
trial division which would run for well over a billion years on a very fast computer with a
number of this size.

b. Find the greatest common divisor d of 12378 and 3054, and find integers 3 x
and y solving the equation 12378x + 3054y = d.
3 Factor 221 using the Pollard's Rho method with polynomial f(x) = .1 2+ 3
Imod221 and initial guess xo = 2. http:/'www.ktuonline.com PART
B

4. a. Let G = (४, E) be a flow with source s and sink t in which each edge 4

e e Eis restricted to capacity c(e) = 1. Further suppose that a maximum flow for G has been
computed and an edge is now removed from E. Describe how the maximum flow can
be efficiently updated and give the run time of your algorithm.

b. Given a string T with only digits (characters 'O' - '9), Suppose we use the 3
Rabin-Karp hash value with mod 113 and 10 as the base. The hash values for
the two prefixes of T are Til .. 12] = 100 and 61 = 50. Calculate the RabinKarp
hash value of T[7 .. 12}. (T[ij] denotes the substring from index i to index J)

5 Define P, NP and NP-complete problems. Give an example for each. 2 5.
a. State and prove Maxflow-mincut theorem. 5

b. Show that an algorithm that makes at most a constant number of calls to 4 polynomial-
time subroutines runs in polynomial time, but that a polynomial number of calls to

polynomial-time subroutines may result in an exponentialtime algorithm.

2
6. a. The figure below shows a flow network on which an s-t flow is shown. The 5 capacity of
each edge appears as a label next to the edge, and the numbers in boxes give the amount
of flow sent on each edge. (Edges without boxed numbers have no flow being sent on
them.)