Computer Science 320 S2 (2020)
Assignment 5
Due date Oct 17, 2020
The following written assignment covers dynamic programming and NP-completeness. An-
swer all of the following questions with full details. Each are worth the same number of marks.
Submit a properly type-setted PDF file (LATEX preferred) of your answers to Canvas before the
deadline.
1. The String Segmentation Problem (SSP) is the problem of cutting up a string
into pieces so that the cumulative value of the pieces is maximized. For each block of
letters x a nonnegative integer value Q(x) is defined, called the quality of x, which can be
computed in one step. Given a string of letters y = y1, y2, . . . , yn, a segmentation of y is
a partition of its letters into contiguous (non-empty) blocks of letters. The total quality
of this partition of y is the sum of the qualities of all the blocks in that segmentation.
(Example: hi has quality 5, there has quality 4, hit and here have both quality 3. All
other blocks have quality 0. If the string hithere is given, the segmentation hi there
has the total quality 9, which is better than the segmentation hit here with total quality
6. Note that 9 is the maximum possible total quality.)
Given an arbitrary assignment of values x and Q(x), describe (in pseudocode) an efficient
dynamic programming algorithm that takes a string y and computes a segmentation of
maximum total quality.
2. With edge-weighted ladder graphs Ln, n > 1 as input (see example below for n = 5), we
want to find the shortest and longest (simple) paths between any two opposite corners of
the graph.
In this example, the shortest path lengths between a and d is -3 (1-3-5+4-2+5-3) and be-
tween b and c is 3 and the longest paths lengths between a and d is 17 (4+2-3+2+2+4+6)
and between b and c is 16.
Shortest LPath: Given an edge-weighted ladder Ln = (V,E), two opposit corners
s, t ∈ V and a positive integer c, is there a simple path in G from s to t of length c
or less?
Longest LPath: Given an edge-weighted ladder Ln = (V,E), two opposite corners
s, t ∈ V and a positive integer c, is there a simple path in G from s to t of length c
or more?
(a) Is either problem NP-hard? If so, justify answer(s).
(b) is either problem solvable in polynomial time? If so, give algorithm(s).
3. Consider the following Graphical Steiner Tree problem. We are given a graph
G = (V,E), a set X ⊆ V of vertices, and a number k. We want to decide whether there
is a set F ⊆ E of at most k edges so that in the graph G′ = (V, F ), X belongs to a single
connected component. Show that the Graphical Steiner Tree problem is NP-hard
by giving a polynomial-time reduction from the Vertex Cover problem.
4. A Boolean expression is in disjunctive normal form (DNF) if it is a disjunction of con-
junctions of literals. For instance, (x ∧ y) ∨ (x ∧ y) is in DNF. Show that the language
{φ | φ is a satisfiable Boolean formula in disjunctive normal form} is in P.
5. Define the Ethnic Subset Problem (ESP) as follows. Given an m × n matrix each
entry of which is either 0 or 1, and given k ≤ m, decide whether there is a subset of at
least k rows that is ethnic, meaning that no two of the selected rows have a 1 in the same
column. Prove that ESP is NP-complete by showing that Independent Set ≤P ESP.
Example: For the following matrix the ESP problem is true for k ≤ 3.
0 0 0 1 1 0
0 1 0 1 1 0
1 1 1 0 0 0
1 1 0 0 0 1
1 1 0 1 0 0
0 0 1 0 0 0

欢迎咨询51作业君