算法分析代考 CS 535 Final Exam (Open-Notes)
算法分析代考 Given a digraph D = (V; A; `) in which all but one arc (u; v) have non-negative lengths, describe an algorithm to compute…
1. Given a digraph D = (V; A; `) in which all but one arc (u; v) have non-negative lengths, describe an algorithm to compute a shortest path from a node s to another node t in O (m + n log n) time where m = 丨A丨 and n = 丨V 丨.
2. Suppose that there are n jobs and m machines. For each 1 i n, the job i has a weight wi > 0 and a processing time interval (ai ; bi ]. Each job can be served on any machine, however each machine can serve at most one job at any time. We would like to select m disjoint subsets S1; S2; ; Sm of the job set f1; 2; ; ng such that (1) the set of jobs in Sj can be served on the machine j for each 1 j m; and (2) the total weight Pm j=1 P i2Sj wi is maximized. Give a polynomial-time algorithm to solve this problem. 算法分析代考
3. Suppose that G is an edge-weighted graph and k is a positive integer. Give a polynomial-time algorithm for computing a maximum weighted matching M in G subject to jMj k.
6. [PhD Session only] Consider a set of n planar points (xi ; yi) for 1 i n in an Euclidean plane. A subset I of these points is said to be independent if every pair of points in I are apart by a distance greater than one. We would like to Önd a largest independent subset. Give a (n log n)-time 3-approximation algorithm for this problem.
