Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
courses:cs211:winter2012:journals:carrie:ch3 [2012/01/30 04:24] hopkinsccourses:cs211:winter2012:journals:carrie:ch3 [2012/02/14 18:01] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] hopkinsc
Line 126: Line 126:
   * seen in dependency networks   * seen in dependency networks
   * for example tasks in order, represent each task by a node.    * for example tasks in order, represent each task by a node. 
-  * topological ordering of G is an ordering of its nodes as v1, v2, .... so that for every edge (vi,vj) wwe have i < j therefore all edges point forward. +  * topological ordering of G is an ordering of its nodes as v1, v2, .... so that for every edge (vi,vj) we have i < j therefore all edges point forward.  
 +  * This will be useful for problm set 4
  
 Theorem 3.18 Theorem 3.18
Line 132: Line 133:
   * see proof in book.    * see proof in book. 
   * is this theorem if and only if? need to find out. TWO sentences later we do find out. The converse is true.    * is this theorem if and only if? need to find out. TWO sentences later we do find out. The converse is true. 
-   ttheorem 3.20+   
 +theorem 3.20
    * see proof in book.     * see proof in book. 
    * uses a lemma 3.19    * uses a lemma 3.19
  
 I'm lost a little towards the end of 3.6, but I'm thinking once we get to it in class it will all be clear!  I'm lost a little towards the end of 3.6, but I'm thinking once we get to it in class it will all be clear! 
 +
 +Update: Class did make this easier to understand. I actually remember using djikstra's alogirthm in a math class before! 
  
  
courses/cs211/winter2012/journals/carrie/ch3.1327897496.txt.gz · Last modified: 2012/01/30 04:24 by hopkinsc
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0