CS/ECE 374 A (Spring 2022) Homework 8 (due March 31 Thursday at 10am)
Instructions: As in previous homeworks.
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!)
Copyright By PowCoder代写 加微信 powcoder
(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.
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.
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.]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com