ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 4
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 ∈ V , sink t ∈ V , and nonnegative node capacities cv for each node v ∈ V . Given a flow f in this graph, the flow into a node is denoted by fi(v). We say that a flow is feasible if it satisfies the usual flow-conservation constraints and the node-capacity constraints: fi(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.
