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作业君