Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 01:02] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterthreesectionvi [2012/02/21 01:34] (current) – [Designing And Analyzing the Algorithm] mugabej
@@ Line 10: / Line 10: @@
 \\
-=== Algorithm ===\\
+ **Algorithm** \\
 \\
->>>>>>To computer a topological ordering on G:\\
+To computer a topological ordering on G:\\
->>>>>>>>Find a node //v// with no incoming edges and order it first\\
+Find a node //v// with no incoming edges and order it first\\
->>>>>>>>>> Delete //v// from G\\
+Delete //v// from G\\
->>>>>>>>>>>> Recursively compute a topological ordering G-{//v//}\\
+Recursively compute a topological ordering G-{//v//}\\
->>>>>>>>>>>>>>and append this order after //v//\\
+and append this order after //v//\\
+\\
+**Analysis**:\\
+\\
+-->Identifying a node //v// with no incoming edges takes O(n) time. Thus for n iterations, we get a O(n<sup>2</sup>) time.\\
+--> If G contains Θ(n²) edges, then it's linear in the size of the input and the running time is not really bad\\
+--> But if we have a number of edges m less than n<sup>2</sup>, a running time of O(m+n) is a much more improvement over Θ(n²).\\
+\\
+To get a O(m+n) time:\\
+\\
+--> We declare a node to be "active" if it has not yet been deleted by the algorithm and we keep two things:\\
+-->For each node //w//, the number of incoming edges that //w// has from active nodes \\
+--> And a set S of all active nodes in G that have no incoming edges from other active nodes.\\
+\\
+At the start, we initialize both of the above things with a single pass through the graph since all of the nodes are active. Thus S consists of all of the nodes in G.\\
+--> With each iteration, we select a node //v// from the set S and delete it.\\
+-->After deleting //v// from S, we go through all of the nodes //w// to which //v// had an edge, and subtract one from the number of active incoming edges that we are maintaining for //w//.\\
+\\
+--> If this causes the number of active edges to //w// to drop to zero, then we add //w// to the set //w//.\\
+--> Proceeding in this way, we keep track of nodes eligible for deletion at all times, while spending constant work per edge during the execution of the algorithm.\\
+Thus we get a O(m+n) time. \\
+\\
+Since I wrote this after doing Problem set 4, everything made more sense and the section became really interesting. I give it a 9/10.