i.VVhat is the value of this flow?

11. Is this a maximum s-t flow in this graph? If not, find a maximum s-t flow.

111. Find a minimum s-t cut. (Specify which vertices belong to the sets of the cut.)

b. Compute the prefix function for the pattern aabaababb when the 2 alphabet is E —
{a, b}.
c. Define PSPACE and NPSPACE. mat can you say about the relationship 2 between
PSPACE and NPSPACE?
PART ^
7. ഒ. A convex polygon in the plane is one in which, for every avo points P], p on 6

the polygon, the line segment from PI to p is contained in (or on the boundary
of) the polygon. Given a set P of n points in the plane, no three of which are
collinear, the convex hull of P is defined to be the smallest convex polygon
containing P.

Design an algorithm to compute the convex hull of P that runs in log n) time. Justify
its correctness and running time.

b. Given a graph G, a CWT is a set of edges whose removal splits the graph into 6 at least
two connected components. The MINIMUM CLIT is the cut of minimum size. The
minimum cut problem is to find a cut of minimum size.

Give a randomized algorithm for finding a minimum cut in a given input
graph G. Find the probability that your algorithm output a minimum cut
in the input graph G.

3
8. a.i.Explain the difference between a Las Vegas randomized algorithm and 6 a Monte Carlo
randomized algorithm.

ii. Suppose that a randomized algorithm succeeds (e.g., correctly computes
the minimum cut of a graph) with probability p (with 0

be a small positive number (less than 1). How many independent times do
you need to run the algorithm to ensure that, with probability at least , at
least one trial succeeds?