Sale!

# ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 4

\$30.00

Category:

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. ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 4
\$30.00
Hello
Can we help?