Algorithm Design and Analysis

A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Adam Smith Algorithm Design and Analysis LECTURE 6 • Topological ordering • Greedy Algorithms Notes • Read on your own – Graph bipartiteness – DFS implementation • Homework notation: – log a (n) = (log n) a – – Useful property: 9/5/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne ceilingleft x ceilingright = smallest in teger ≥ x

= “ceiling” x ≤ ceilingleft x ceilingright < x + 1 Last lecture: BFS • Recall: Digraph G is strongly connected if for every pair of vertices, s↝t and s↝t • Question: Give an algorithm for determining if a graph is connected. What is the running time? 9/5/2008 A. Smith; based on slides by E. Demaine, C. Leiserson, S. Raskhodnikova, K. Wayne Strong Connectivity: Algorithm Lemma: G is strongly connected if and only if for any node s, every other node t has paths to and from s. Theorem. Can determine if G is strongly connected in O(m + n) time. Pf. Pick any node s. Run BFS from s in G. Run BFS from s in G rev . Return true iff all nodes reached in both BFS executions. Correctness follows immediately from the previous lemma. reverse orientation of every edge in G strongly connected not strongly connected Directed Acyclic Graphs Def. An DAG is a directed graph that contains no directed cycles. Ex. Precedence constraints: edge (v i , v j ) means v i must precede v j . Def. A topological order of a directed graph G = (V, E) is an ordering of its nodes as v 1 , v 2 , …, v n so that for every edge (v i , v j ) we have i < j. a DAG a topological ordering v 2 v 3 v 6 v 5 v 4 v 7 v 1 v 1 v 2 v 3 v 4 v 5 v 6 v 7 Precedence Constraints Precedence constraints. Edge (v i , v j ) means task v i must occur before v j . Applications. Course prerequisite graph: course v i must be taken before v j . Compilation: module v i must be compiled before v j . Pipeline of computing jobs: output of job v i needed to determine input of job v j . Directed Acyclic Graphs Lemma. If G has a topological order, then G is a DAG. Pf. (by contradiction) Suppose that G has a topological order v 1 , …, v n and that G also has a directed cycle C. Let's see what happens. Let v i be the lowest-indexed node in C, and let v j be the node just before v i ; thus (v j...

Website: www.cse.psu.edu | Filesize: -
No of Page(s): 17
Download Algorithm Design and Analysis.pdf