1. Draw the KMP DFA for the following pattern string: AACAAAB.

2. Construct an example where the Boyer-Moore algorithm performs poorly.

3. True or false. If true, provide a short proof. If false, give a counterexample.

(a) If all edge capacities are distinct, the max flow is unique.

(b) There exists a max flow for which there is no directed cycle on which every edge

carries positive flow.

(c) If all edge capacities are increased by an additive constant, the min cut remains

unchanged.

4. Consider a variant of the Maximum-Flow problem with node capacities as follows. Let

G = (V; E) be a directed graph with source s 2 V , sink t 2 V , and nonnegative node

capacities cv for each node v 2 V . Given a flow f in this graph, the flow into a node is

denoted by f i(v). We say that a flow is feasible if it satisfies the usual flow-conservation

constraints and the node-capacity constraints: f i(v) ≤ cv for all nodes.

Show how Ford-Fulkerson algorithm can be used to find a maximum flow in a nodecapacitated network.

5. Two paths in a graph are edge-disjoint if they have no edge in common.

Disjoints Path Problem: Given a digraph G = (V; E) and two nodes s and t, find the

maximum number of edge-disjoint s-t paths.

Sow how this problem can be reduced to the max flow problem.

Sale!