Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch3 [2018/02/07 03:57] – ahmadh
+++ courses:cs211:winter2018:journals:ahmadh:ch3 [2018/02/07 04:06] (current) – ahmadh
@@ Line 229: / Line 229: @@
 This algorithm runs in O(n^2).
+We can improve this running time to O(m+n) by modifying the algorithm slightly as follows:
+We declare a node to be "active" if it has not yet been deleted by the algorithm, and we explicitly maintain two things:
+(a) for each node w, the number of incoming edges that w has from active nodes; and
+(b) the set S of all active nodes in G that have no incoming edges from other active nodes.
+At the start, all nodes are active, so we can initialize (a) and (b) with a single pass through the nodes and edges. Then, each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through all 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 incoming edges to w to drop to zero, then we add w to the set S. Proceeding in this way, we keep track of nodes that are eligible for deletion at all times, while spending constant work per edge over the course of the whole algorithm.
+==== 3.6.2 Comments ====
+I feel like this section was more challenging to understand compared to the rest of the chapter--probably because it was something entirely new to me. The idea of topological ordering seems intuitive and straightforward, and the O(n^2) algorithm felt the most natural way to compute the ordering. While I thought that the optimization to this algorithm to give the O(m+n) running time was genius, I struggled a fair amount understanding the optimized algorithm. However, a few reads later, I did get the idea (took me longer than it should have, to be honest). I'd say this was the most interesting section from 3.2 to 3.6 (the rest was probably 60% review).