CS/ECE 374 A (Spring 2022) Homework 8 Solutions
Problem 8.1: We are given a set P of n points {p1, . . . , pn} in two dimensions. Each point pi has coordinates (xi,yi). (In this question, the xi’s and yi’s may not be distinct!)
(a) Given a source point s ∈ P and a destination point t ∈ P , we want to determine whether there exists a sequence pi0 pi1 pi2 · · · pik with pi0 = s and pik = t, such that each segment pij pij+1 is either horizontal or vertical. (Paths are allowed to self-intersect.) Describe an efficient algorithm to solve this problem.
(b) Next, given a source s ∈ P and a destination t ∈ P and a value L, we want to determine whether there exists a sequence pi0 pi1 pi2 · · · pik with pi0 = s and pik = t, such that (i) each segment pij pij+1 is either horizontal or vertical, and (ii) d(pij , pij+1 ) + d(pij+1 , pij+2 ) ≥ L for all j = 0, . . . , k − 2. (The motivation is in finding a path that avoids quick turns.) Describe an efficient algorithm to solve this problem.
Copyright By PowCoder代写 加微信 powcoder
You should solve the above problems by transforming the input into a graph and applying a standard algorithm you have seen in class. In these type of graph questions, remember to give mathematically precise definitions of the vertices and edges of your graph. Analyze the overall running time (the time to construct the graph plus the time to run the standard algorithm) as a function of n.
[Hint: For (a), partial credit will be given for an O(n2)-time algorithm, but there is an O(n log n)-time algorithm. For (b), construct a graph with O(n2) vertices. . . ]
Below, the left picture shows one path that is a feasible solution for (a). The right picture shows a path that might work better for (b), depending on the value of L.
First Solution for (a): Define an undirected graph G = (V, E): The vertices are the input points, i.e., V = P .
For each point pi ∈ P, define its right neighbor NR(pi) to be a point pj with the smallest xj such that yj = yi and xj > xi; define its left neighbor NL(pi) to be a point pj with the largest xj such that yj = yi and xj < xi; define its up neighbor NU (pi) to be a point pj with the smallest yj such that xj = xi and yj > yi; define its down neighbor ND(pi) to be a point pj with the largest yj such that xj = xi and yj < yi. Add the edges from pi to its four neighbors NR(pi), NL(pi), NU(pi), and ND(pi) (if they exist). We run BFS or DFS from s, to decide whether there exists a path from s to t in G. (Correctness is not difficult to see. Suppose there is a sequence pi0 pi1 · · · pik with pi0 = s and pik = t, such that each segment pij pij+1 is either horizontal or vertical. For each j, since pij and pij+1 have the same x-coordinate or the same y-coordinate, there is a path from pij and pij+1 by following a series of up/down neighbors or a series of left/right neighbors, and so there is a path from s to t in G. Conversely, if there is path pi0pi1 ···pik from s to t in G, then pi0 pi1 · · · pik obviously satisfies the stated condition.) Running time analysis. The graph G has n vertices. Since each vertex has degree at most 4, the number of edges is m ≤ 4n. To construct the graph, we sort all the input points lexicographically by x coordinates, and for points with the same x, by y-coordinates. This takes O(n log n) time. Then for the points with the same x, we can identify their top and bottom neighbors by a linear scan in the y-sorted list (the top and bottom neighbors are precisely the successor and predecessor in the y-sorted list). The total time for the linear scans is O(n). Similarly, we can identify the left and right neighbors of all points in O(n) time, this time by sorting by y-coordinates first, and for points with the same y, by x-coordinates. Afterwards, the running time of BFS or DFS is O(m + n), which is O(n) since m ≤ 4n. Total time: O(n log n). (Remark. For a more naive solution, we can just add an edge between pi and pj iff xi = xj or yi = yj. But this graph may have quadratically many edges, resulting in an O(n2)-time algorithm.) Second Solution for (a): We describe an alternate solution that is even simpler. Define an undirected (bipartite) graph G′ = (V, E): Let X be all the x-coordinates of P, and Y be all the y-coordinates of P. The vertices of our new graph will be the coordinates rather than the points. More precisely, V = {(x, 1) : x ∈ X} ∪ {(y, 2) : y ∈ Y }. For each point pi = (xi,yi) ∈ P, we add an edge between (xi,1) and (yi,2). Suppose s = pa and t = pb. We run BFS or DFS from (xa, 1), to decide whether there exists a path from (xa, 1) to (xb, 1) in G′. Correctness. Suppose there is a sequence pi0 pi1 · · · pik with i0 = a and ik = b, such that each segment pij pij+1 is either horizontal or vertical. For each j, there is a path from (xij , 1) to (xij+1 , 1) in G′, namely, the path (xij , 1)(yij , 2)(xij+1 , 1) if pij pij+1 is horizontal (i.e., yij = yij+1 ), or the trivial path of length 0 if pij pij+1 is vertical (i.e., xij = xij+1 ). It follows that there is path from (xa, 1) to (xb, 1) in G′. Conversely, suppose there is path from (xa, 1) to (xb, 1) in G′, say, (xi0 , 1)(yi0 , 2)(xi1 , 1)(yi1 2) · · · (xik , 1) with i0 = a and ik = b. Then s,(xi0,yi0),(xi1,yi0),(xi1,yi1),...,(xik,yik−1),t form a sequence of points in P and alternate between vertical and horizontal segments. Running time analysis. The graph G′ has at most 2n vertices and n edges. Thus, the running time of the BFS or DFS is O(n). We also need to bound the time to construct the graph G′. To construct X and Y , one needs to identify and remove duplicate coordinate values. This requires either hashing, which takes O(n) expected time (if coordinates are integers), or sorting, which takes O(n log n) time. (After duplicates are identified, we technically also need to map coordinate values to indices, so that we can build an adjacency list representation of the graph.) The total time is at most O(n log n) either way. Solution for (b): Define an directed (or undirected) graph G = (V, E): V = {s,t}∪{(pi,pj) : pi,pj ∈ P and (xi = xj or yi = yj)}. Notice that except for s and t, vertices are pairs of points! Foreachpi,pj,pk ∈P,if(pi,pj),(pj,pk)∈V,weaddanedgefrom(pi,pj)to(pj,pk)iff d(pi , pj ) + d(pj , pk ) ≥ L. Foreachpi ∈P,if(s,pi)∈V,weaddanedgefromsto(s,pi). Foreachpi ∈P,if(pi,t)∈V,weaddanedgefrom(pi,t)tot. We run BFS or DFS from s, to determine whether there is a path from s to t in G. Correctness is obvious from the definition of the problem. Running time analysis. The number N of vertices in G is at most 2 + n2 = O(n2). The number M of edges in G is at most n3 + 2n = O(n3). The graph can be constructed in O(n3) time, by looping through all O(n3) combinations of pi,pj,pk. The running time of BFS or DFS is O(M + N), which is O(n3). Total time: O(n3). (Remark. A faster algorithm is possible with more complicated ideas. I can get close to O(n2 log n) time. I currently don’t have a subquadratic-time algorithm, but suspect that there could be one. . . ) Problem 8.2: We are given a directed graph with n vertices and m edges and a source vertex s, where each edge e has a color c(e) from {1,...,k}. (a) (25 pts) Describe an algorithm to determine whether there is a closed walk that contains s and uses at least 4 colors. (Recall that in a walk, repeated vertices are allowed.) For full credit, the running time should be O(m + n). [Hint: use the meta-graph.] (b) (75 pts) Describe an algorithm to determine whether there is a walk (not necessarily closed) that starts at s and uses at least 4 colors. For full credit, the running time should be O(k3(m + n)) or better. [Hint: one approach is to define a new graph with O(k3n) vertices. You will still get partial credit if you obtain O(k4(m + n)) time instead.] (a) The algorithm is simple: (a) First compute the strongly connected components. (b) Return true iff the component containing s contains at least 4 colors. Runtime. We can compute the strongly connected components in O(m) time by the algorithm from class. We can check whether a component uses at least 4 colors, by examining each edge one by one, and adding its color to the current list, and stopping as soon as the list has size 4. (Remark: actually, the strongly connected components algorithm from class is unnec- essary, since we only want the component containing s. A simpler way is to run BFS from s in G, and run BFS from s in the reverse graph of G. Vertices in the component of s are precisely those that are both reachable from s in G and reachable from s in the reverse graph.) Correctness. If a component contains edges (u1, v1), . . . , (uk, vk) using at least 4 colors, we can connect these edges together to form a closed walk (since by definition of strongly connected components, there are paths from v1 to u2, v2 to u3, etc.). Conversely, if there is a closed walk using at least 4 colors, all vertices in the walk belong to the same strongly connected component, so this component uses at least 4 colors. (b) Let G = (V, E) be the given directed graph. Construct a new directed graph G′: For each v ∈ V and each subset S ⊆ {1,...,k} of size at most 3, create a new vertex (v,S) in G′. Also create an extra vertex t′. For each edge (u,v) ∈ E with color c(u,v) and each subset S ⊆ {1,...,k} of size at most 3, create an edge from (u,S) to (v,S ∪ {c(u,v)}) in G′ if |S ∪ {c(u,v)}| ≤ 3, andanedgefrom(u,S)tot′ inG′ if|S∪{c(u,v)}|=4. We then run BFS or DFS in G′ from (s, ∅), and return true iff there is a path from (s, ∅) to t′ in G′. Runtime. G′ has at most O(k3n) vertices (since there are O(k3) subsets of {1, . . . , k} of size at most 3) and O(k3m) edges. The BFS/DFS takes O(k3(m + n)) time. Justification. For each subset S of size at most 3, a vertex (v, S) is reachable from (s, ∅) inG′ iffthereisawalkinGfromstovandusespreciselythecolorsinS. Andt′ is reachable from (s, ∅) iff there is a walk from s using at least 4 colors. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com