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