CS535 Homework 1
CS Homework代写 General notations: For a digraph D = (V; A), m := jAj and n := jV j. For an edge-weighted digraph D = (V; A; `), ` is the edge-length function.
General notations: For a digraph D = (V; A), m := jAj and n := jV j. For an edge-weighted digraph D = (V; A; `), ` is the edge-length function. CS Homework代写
1. Consider a digraph D = (V; A) with two distinct vertices s and t.
(a) Let F denote the set of edges in A which appear in some shortest s-t path ( in terms of the number of edges) in D. Give an algorithm to output F in O (m + n) time.
(b) Give an algorithm to Önd an inclusion-wise maximal edge-disjoint shortest s-t paths in D in O (m + n) time.
3. Suppose that a digraph D = (V; A) has no negative circuit but has a 0-length circuit C. Let p be an arbitrary potential function, and `p be the edge length function adjusted by p. Prove that for any edge a 2 C, `p (a) = 0.
4. Let D = (V; A) be a digraph, and s and t be two distinct nodes in V . Show that D has no s-t path if and only if there exists a nonnegative integer-valued labeling p of the nodes satisfying that CS Homework代写
- p (s) = n and p (t) = 0;
- for each (u; v) 2 A, p (u)-p (v) ≤ 1.
5. Given a digraph D = (V; A; `) with non-negative edge lengths and a node s 2 V , describe an algorithm to Önd a shortest circuit containing the node s in O (m + n log n) time.
6. Given a digraph D = (V; A; `) in which all but one arc (u; v) have non-negative lengths, describe an algorithm to test whether D has a negative circuit in O (m + n log n) time.
7. [PhD Session only] Consider a convex n-gon with n 4 vertices v1; v2; ; vn in a clockwise order whose coordinates are given. For any subset U of at least three vertices, let f (U) be the area of the convex polygon with U being the vertex set. CS Homework代写
- For any integer 3 m < n, give an e¢ cient algorithm to produce a subset U of m vertices with the largest area f (U), prove its correctness, and analyze its running time.
- Prove that if the two rays v1v2 and v4v3 intersect, then
f (｛v1; v2; v3g｝) + f (｛v2; v3; v4g｝) < f (｛v1; v2; v4g｝) + f (｛v1; v3; v4｝):
