Solved–ASSIGNMENT 4– Solution

Description

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.

1. 1. If all edge capacities are distinct, the max ow is unique.

1. 2. There exists a max ow for which there is no directed cycle on which every edge carries positive ow.

1. 3. 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 c_v for each node v 2 V . Given a ow f in this graph, the ow into a node is denoted by fⁱ(v). We say that a ow is feasible if it satis es the usual ow-conservation constraints and the node-capacity constraints: fⁱ(v) c_v for all nodes.

Show how Ford-Fulkerson algorithm can be used to nd a maximum ow in a node-capacitated 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, nd the maximum number of edge-disjoint s-t paths.

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

1