Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:patelk:chapter3 [2018/02/05 05:33] – [3.2 Basic Definitions and Applications] patelk | courses:cs211:winter2018:journals:patelk:chapter3 [2018/02/05 05:40] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] patelk | ||
|---|---|---|---|
| Line 148: | Line 148: | ||
| * O(m+n): although algorithm may run BFS/DFS multiple times, only a constant amount of work on a given edge or node is done in the iteration when the connected component it belongs to is under consideration | * O(m+n): although algorithm may run BFS/DFS multiple times, only a constant amount of work on a given edge or node is done in the iteration when the connected component it belongs to is under consideration | ||
| + | ==== Personal Thoughts ==== | ||
| + | |||
| + | This section was not intuitive for me, but made a lot of sense as I was reading. Being familiar with BST, DST, queues, and stacks already, helped make this section easier to understand. The algorithms do take some time to conceptually understand, but are not that difficult. | ||
| + | Readability: | ||
| + | Interesting: | ||
| ===== 3.4 Testing Bipartiteness: | ===== 3.4 Testing Bipartiteness: | ||
| Line 164: | Line 169: | ||
| - There is an edge of G joining two nodes of the same layer: Not Bipartite | - There is an edge of G joining two nodes of the same layer: Not Bipartite | ||
| + | ==== Personal Thoughts ==== | ||
| + | I don't really remember bipartite graphs from other classes, but they are pretty simple and this section made them very simple. We did already talk about them in class, so that did help as well. There wasn't any information that was too confusing in this short section. | ||
| + | Readability: | ||
| + | Interesting: | ||
| ===== 3.5 Connectivity in Directed Graphs===== | ===== 3.5 Connectivity in Directed Graphs===== | ||
| Line 192: | Line 201: | ||
| * Compute the strong components for all nodes: O(m+n) | * Compute the strong components for all nodes: O(m+n) | ||
| + | ==== Personal Thoughts ==== | ||
| + | |||
| + | Again, this section was not very difficult to understand and most of it makes sense. I would like to talk a little bit more about strong connectivity in class. The concept makes sense, but I would like to learn more about why it is useful/ | ||
| + | Readability: | ||
| + | Interesting: | ||
| ===== 3.6 Directed Acyclic Graphs and Topological Ordering===== | ===== 3.6 Directed Acyclic Graphs and Topological Ordering===== | ||
| Line 209: | Line 223: | ||
| * Thus, in every DAG G, there is a node with no incoming edges | * Thus, in every DAG G, there is a node with no incoming edges | ||
| * If this is not true, then there is a cycle, so it is not a DAG | * If this is not true, then there is a cycle, so it is not a DAG | ||
| - | * | + | |
| {{: | {{: | ||
| Line 225: | Line 239: | ||
| * This leads to constant work per edge | * This leads to constant work per edge | ||
| + | ==== Personal Thoughts ==== | ||
| + | |||
| + | This section contained information that I had not yet been exposed to. However, most of the section was very intuitive. Cycles are not a very difficult concept so it makes sense why a DAG cannot have a cycle. This is my first time, as far as I remember, being exposed to DAGs, so it will be interesting to see how difficult I find them as we do more complex things with them. | ||
| + | Readability: | ||
| + | Interesting: | ||
