Differences

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

--- courses:cs211:winter2018:journals:thetfordt:chapter3 [2018/02/04 19:16] – thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter3 [2018/02/05 19:37] (current) – thetfordt
@@ Line 15: / Line 15: @@
 The section then goes on to illustrate a few different ways to generate the connected component - the first being the breadth-first search (BFS). The
-BFS starts at a node, call it 's', and then branches out from that node s to create a layer, L_1 (layer 1). That layer contains all of the nodes to which s is directly connected. The process is then done again, but L_2 contains all of those nodes that are connected to all nodes in L_1, but does not add any nodes which are already in the set. This process continues until we reach an empty layer. The book also walks through the fact that for any node in L_i, that node is exactly a distance of i away from 's'. And that the structure of a BFS can be represented as a tree rooted at the start node.
+BFS starts at a node, call it 's', and then branches out from that node s to create a layer, L_1 (layer 1). That layer contains all of the nodes to which s is directly connected. The process is then done again, but L_2 contains all of those nodes that are connected to all nodes in L_1 but does not add any nodes which are already in the set. This process continues until we reach an empty layer. The book also walks through the fact that for any node in L_i, that node is exactly a distance of i away from 's'. And that the structure of a BFS can be represented as a tree rooted at the start node.
 The section then moves on to the concept of exploring a connected component. It lays forth an algorithm to seek out the connected component in a vague manner. It just continually adds nodes to a set R which are connected to nodes in the component, R, until it cannot any longer. The set R begins as just the start node, 's'. I found the proof that this algorithm works slightly confusing, but I agree with the intuition behind it.
@@ Line 25: / Line 25: @@
 ===== Section 3.3 - Implementing Graph Traversal Using Queues and Stacks =====
-The section begins by providing a short summary of what will be covered. We will walk through the different ways for implementing graphs, and then the same concept, but with the implementation of graph-traversal algorithms.
+The section begins by providing a short summary of what will be covered. We will walk through the different ways of implementing graphs, and then the same concept, but with the implementation of graph-traversal algorithms.
 The section then outlines the two ways of representing a graph, an adjacency matrix and an adjacency list. And although the adjacency matrix maintains constant access runtime to access a particular connection between two nodes. The book also walks through the proof that the adjacency list takes only O(m+n) space whereas the matrix takes O(n^2) space. I found this proof very helpful, as I was a bit hazy on using two separate variables after covering it in class. Because of this improved space (as m is always less than or equal to n^2), the book uses the adjacency lists for further implementation.
@@ Line 32: / Line 32: @@
 The section then walks through the implementation of the depth-first search (DFS). This algorithm uses a stack for implementation. It initializes S to be a stack with one element, the start node 's'. And then while S is nonempty, it takes a node u from S, and if that node has not been explored, it sets the value to explored, adds each edge (u,v) incident to u to the stack S. And then by the termination of the algorithm, all nodes in the DFS will have been set to explored. The section notes that the algorithm will examine all of the nodes in the same order as the DFS, but the adjacency lists are processed in reverse order (because we are using a stack). The DFS algorithm also runs in O(n+m) time.
+I found this section to be helpful, but a bit dense. I understood most of these concepts from class, so it was primarily review. I would rate the readability at 7/10.
 ===== Section 3.4 - Testing Bipartiteness: An Application of Breadth-First Search =====
+This section walks through an application of the Breadth-First Search. The problem we encounter is that we want an efficient way of determining if a graph is bipartite. The section first reasons clearly through the fact that if a graph is bipartite, then it cannot contain an odd-length cycle.
+The section then designs an algorithm for determining if a graph is bipartite. It assumes first that a graph is connected. We pick any node to start with, color it red, perform a breadth-first search, alternating the colors of each layer. And if at any point, there is some edge with ends of the same color, we know that the graph is not bipartite. Otherwise, every edge has opposite colors on it and thus is bipartite.
+The section then analyzes the algorithm, claiming that either (1) there is no edge of G joining two nodes of the same layer - and here G is bipartite. Otherwise, there is an edge of G joining two nodes of the same layer. And here, G contains an odd-length cycle and thus is not bipartite. This proof was very clear and cleared up some confusion I had at the last class, as we were cut short while going over the logic behind this claim.
+This section was short and easy to read, I would rate the readability at 9/10.
+===== Section 3.5 - Connectivity in Directed Graphs =====
+In this section, we move away from undirected graphs into the territory of directed graphs. The book first walks through the primary way of representing directed graphs. We will do this using two adjacency lists of the nodes, one containing the "out" edges, and one containing the "in" edges. Note that this will take O(m+n) space, as each one individually takes O(m+n) space. The book notes that the process BFS and DFS change very little when moving to directed graphs, besides adjusting for direction.
+The text walks through the idea of strong connectivity, where two nodes are strongly connected if there are mutual paths between them. They also defined a strong component (say of a node, 's') - the set of all nodes to which 's' is strongly connected. They then walked through the proof that for any two nodes in a directed graph, their strong components are either identical or disjoint, which I found very intuitive.
+This section was a nice review, and short. I would rate the readability at 8/10.
+===== Section 3.6 - Directed Acyclic Graphs and Topological Ordering =====
+This section begins by walking through some ideas surrounding directed versus undirected graphs and then defines what a graph with no cycles is called - a directed acyclic graph, or DAG.
+The book walks simply through the proof that if a graph G has a topological ordering, then G is a DAG, but then proposes the question as to whether there is an implication that G has a topological ordering if G is a DAG. When walking through the proof of this, I understood it more clearly from class. In class, I did not make the connection that we could continue walking backward through the graph indefinitely.
+The book then walks through the algorithm to organize a DAG in a topological order. The algorithm first targets a node with no incoming edges, deletes that node from the graph, and then recursively computes a topological ordering of the graph minus that first node. This algorithm appears to run in O(n^2) time, but in actuality, if we keep track of the number of incoming edges that each node has whenever we delete a node, the runtime is O(n+m). This concept was a bit hazy in class, but made more sense after reading the chapter.
+I would rate the readability of this section at 9/10. It was easy to follow and cleared up some confusing concepts.