Computer Science > SOLUTIONS MANUAL > Illinois State University - CS 473hw8-solutions (All)

Illinois State University - CS 473hw8-solutions

Document Content and Description Below

CS 473 Homework 8 Solutions Fall 2016 1. Suppose we are given an n × n grid, some of whose cells are marked; the grid is represented by an array M[1..n, 1..n] of booleans, where M[i, j] = True if a... nd only if cell (i, j) is marked. A monotone path through the grid starts at the top-left cell, moves only right or down at each step, and ends at the bottom-right cell. Our goal is to cover the marked cells with as few monotone paths as possible. É Not to submit: Describe an algorithm to find a monotone path that covers the largest number of marked cells. Solution: We construct a graph G. • G has two vertices ui,j and vi,j for each pair of array indices i and j. • Each vertex ui,j has an edge to its partner vi,j. Each partner edge has length 1 if M[i, j] = TRUE and length 0 otherwise. • Each vertex vi,j has edges to its right neighbor ui+1,j and its downward neighbor ui,j+1 (if they exist). Neighbor edges have length 0. Each monotone path through the grid is represented by a directed path in G. Conversely, every directed path in G represents a monotone path through the grid. Thus, if we can cover k marked cells with a monotone path, then there is a path of length k in the graph. Conversely, if the graph has a path of length k, that path corresponds to a monotone path that must cover k marked cells. So we can solve find the monotone path that covers the largest number of marked cells in the grid by finding the longest path in G from u1,1. The graph G has O(n2) vertices and edges, and we can construct it in O(n2) time. Since G is a DAG, finding the longest path can be done in O(jVj + jEj) = O(n2) time using Dynamic Programming. É Not to submit: There is a natural greedy heuristic to find a small cover by monotone paths: If there are any marked cells, find a monotone path Π that covers the largest number of marked cells, unmark any marked cells covered by Π, and recurse. Show that this algorithm does not always compute an optimal solution. Solution: Here is a 6 × 6 counterexample: The greedy strategy is not optimal. The middle figure shows a greedy path; in fact any greedy monotone path covers the same four marked cells. If we start with a greedy path, we need two more monotone paths to cover the other two marked cells. The right figure shows that the marked cells can all be covered with just two monotone paths. É Describe and analyze an efficient algorithm to compute the smallest set of monotone paths that covers every marked cell. Solution (Reduction to flow with lower bounds): Consider the following decision problem: Can the marked cells be covered using at most k monotone paths? If we can solve the decision problem efficiently, then we can find the minimum number of paths efficiently by performing binary search over the possible values of k. We construct a directed flow network G, with both capacities and lower bounds on the edges, [Show More]

Last updated: 2 years ago

Preview 1 out of 7 pages

Buy Now

Instant download

We Accept: