2 Given a directed weighted acyclic graph G = (V, E, W) and a vertex s, design an O(n+m) algorithm to find a longest path that starts from s, where n = |V|, m=|E|. (Hint: Do topological sorting from s. (Only call DFS once.) Let v1 (= s), v2, v3, ...., vk, be the sorted sequence, k £ n. Define d(vi) to be the longest distance from s to vi. Initially, d(vi) = - ¥. Set d(v1) = 0. If d(v1), d(v2), …, d(vi) have been computed, how to compute d(vi+1) ?)
3 There are n terminals on each side of a circuit board indexed with 1, 2, …, n from left to right, as shown in the following figure. We need to connect terminal i (1 ≤ i ≤ n) on the top side with a unique terminal π(i) on the bottom side. In other words, we need n lines (i, π(i)) (1 ≤ i ≤ n) to connect n pairs of terminals. The following figure shows an example.
Two lines (i, π(i)) and (j, π(j)) ( i ¹ j) will cross each other if i < j but π(i) > π(j), or vice versa. Two lines are called compatible if they do not cross each other. We wish to find the largest set of mutually compatible lines so that they can be layout on the same layer of circuit without crossing each other.
Please model this problem as a graph problem first and then design an O(n2) algorithm to solve it.
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 算法理论与分析 』 → 两个算法题
(订阅本版)
2009/7/23 23:19:00
新浪微博
两个算法题
