Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
courses:cs211:winter2012:journals:ian:chapter3 [2012/02/01 00:20] sturdyicourses:cs211:winter2012:journals:ian:chapter3 [2012/02/01 03:11] (current) sturdyi
Line 4: Line 4:
  
    * A graph is a connection of nodes and edges, which may be either directed or undirected; this can model a variety of complexes and relationships, especially networks (whether physical or notional); trees are graphs that do not contain cycles. A typical operation on a graph is traversal between nodes along edges, and more generally the search for possible and optimal traversals.    * A graph is a connection of nodes and edges, which may be either directed or undirected; this can model a variety of complexes and relationships, especially networks (whether physical or notional); trees are graphs that do not contain cycles. A typical operation on a graph is traversal between nodes along edges, and more generally the search for possible and optimal traversals.
-   +   I would have liked to see some examples of graphs representing things other than networks, like the prior example of phrasing stable matching as a graph-solving problem. They gave a lot of examples, but all fell into two or three sets up to isomorphism. 
 +   * No questions. 
 +   * No other complaints. 7/10.
  
 ===== 3.2 Graph Connectivity and Traversal ===== ===== 3.2 Graph Connectivity and Traversal =====
  
-   * Two common patterns to algorithms answering questions about graphs are breadth-first and depth-first search; the former is particularly useful for finding shortest roots and analyzing cycles, and the latter where backtracking is easier than arbitrary jumping; both are suited to finding connected components.+   * Two common patterns to algorithms answering questions about graphs are breadth-first and depth-first search; the former is particularly useful for finding shortest roots and analyzing cycles, and the latter where backtracking is easier than arbitrary jumping; both are suited to finding connected components. In BFS two nodes sharing an edge must be in the same layer or subsequent layers; in DFS if {//a//,//b//} is an edge either //a// is an ancestor of //b// or vice versa. 
 +   * No insights. 
 +   * No questions. 
 +   * No complaints.. 7/10.
  
 ===== 3.3 Implementing Graph Traversal Using Queues and Stacks ===== ===== 3.3 Implementing Graph Traversal Using Queues and Stacks =====
Line 33: Line 38:
 ===== 3.6 Directed Acyclic Graphs and Topological Ordering ===== ===== 3.6 Directed Acyclic Graphs and Topological Ordering =====
  
-   * DAGs appear in such contexts as dependency networks (at least one hopes that one's dependencies are acyclic). a topological ordering of a DAG is an ordering of the nodes such that every edge connects nodes in order. For directed graphs, acyclicality is equivalent to the existence of a topological ordering.+   * DAGs appear in such contexts as dependency networks (at least one hopes that one's dependencies are acyclic). a topological ordering of a DAG is an ordering of the nodes such that every edge connects nodes in order. For directed graphs, acyclicality is equivalent to the existence of a topological ordering. Every DAG must have a node with no incoming edges; recursive application of this fact yields a topological ordering. This can be done in O(m+n) time by keeping an array of the number of incoming connections to each node and then, whenever adding a node to the ordering, decrementing that number for each of the nodes to which it leads. 
 +   * I had been wondering how to do this in conceptual work for a project I shall probably never get to (applying parallelization and large-dataset techniques (as discussed yesterday) to econometrics)--I am consistently impressed at how elegant some of these solutions are. 
 +   * Does not the O(m+n) runtime of the algorithm depend on being able to select an edge with no remaining ancestors in constant time? If it involves a scan through the array of remaining parents, I would think that the inner loop would be O(n^2), since it must repeat once for each node and each step is O(n) on account of the scan. 
 +   * Well written. 8/10.
courses/cs211/winter2012/journals/ian/chapter3.1328055607.txt.gz · Last modified: 2012/02/01 00:20 by sturdyi
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0