Differences

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

--- courses:cs211:winter2018:journals:thetfordt:chapter3 [2018/01/29 20:34] – thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter3 [2018/02/05 19:37] (current) – thetfordt
@@ Line 8: / Line 8: @@
 Following this, the author briefly covers trees, and the role they play in the graphing world. Having just covered heaps in Chapter 2, these seem very similar with some small variations. This section offered a strong introduction to graphs and was both understandable and concise. I would rate the readability of this section at 9/10.
+===== Section 3.2 - Graph Connectivity and Graph Traversal =====
+The section by laying out the problem of connectivity. For two nodes s and t, we want to be able to determine if they are connected. We do this by defining a set of nodes called the connected component. This connected component of a node s contains all nodes which are connected to s.
+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.
+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.
+The section continues on to the depth-first search (DFS). This starts at a node s, and rather than defining layers, it continues to one node, then adds it to the component, then recursively calls itself. Eventually, when it reaches a stopping point, the algorithm backtracks to previous calls, and recalls itself to see if there was a different, deeper, path it could have explored. I found the proof of (3.6) to be very helpful, as I found the concept slightly confusing in class.
+The section ends by outlining the set of all connected components and proves that for any two nodes, their connected component is either identical or disjoint. I found this proof very straight-forward. I enjoyed reading this section and found it to be a helpful refresher from class. I would rate the readability at 9/10.
+===== 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 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.
+The section then walks through the implementation for the BFS. The algorithm uses an array of lists in order to manage each layer in the adjacency list. It also maintains an array length n to maintain if each node is discovered or no. It takes the start node, s, and sets it's value to true in the Discovered array, let's L_0 consist of 's', sets the layer counter 'i' to 0, and sets the current BFS tree T = empty set. It then begins a while loop that stops when L[i], the i-th layer, is empty. In the while loop, it forms an empty list at L[i+1], considers each node u in L[i], and for each edge (u,v) incident to u, if the node v is not discovered, we set it to discovered, add the edge (u,v) to the BFS tree T, and add v to the list L[i+1]. the for-loop terminates, the layer counter is incremented, and the while loop continues. The book then proves, very concisely and logically, that the implementation of the BFS algorithm runs in O(m+n) time. I was a little confused why the section made a point to say that we would use queues to implement this (at the beginning) but then went on to note here that we could use either queues or lists without a difference.
+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.