Differences

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

--- courses:cs211:winter2018:journals:donohuem:chapter3 [2018/01/30 00:24] – donohuem
+++ courses:cs211:winter2018:journals:donohuem:chapter3 [2018/02/07 02:17] (current) – donohuem
@@ Line 1: / Line 1: @@
 ====== Chapter 3 ======
 ===== 3.1 Basic Definitions and Applications =====
 A graph is a collection of V nodes and E edges where an edge e is represented as a two-element subset {u, v}. Directed graphs represent an edge e in ordered pairs (u, v), which are not interchangeable. An undirected graph is essentially a default graph. Examples of graphs include transportation, communication, information(e.g. world wide web), social, and dependency networks. An important operation in graphs is traversing a sequence of nodes connected by edges. Traversal requires that a path, a sequence of of connected nodes, exist. An undirected graph is corrected if there exists a path between every pair of nodes. Interestingly, trees are undirected graphs that do not contain a cycle (the sequence of nodes does not cycle back to where it begins). Overall the section was a basic overview of graphs, and it's readability is an 8/10.
+===== 3.2 Graph Connectivity and Graph Traversal =====
+Chapter begins with introduction to the problem of determining connectivity between two nodes, s and t. One algorithm for determining connectivity is Breadth-First Search (BFS), which explores outwards from s layer by layer. BFS outputs a tree. Another natural way of determining connectivity between s and t is Depth-First Search (DFS). Unlike BFS, DFS explores outward from s following a path of connected edges until it reaches a dead end. It then backtracks to a node with an unexplored neighbor and tries another route. DFS also outputs a tree, but of a very different shape. Another important subject in this section is a Connected Component. The connected component of a node s is the set of nodes reachable from s. For any two nodes s and t in a graph, their connected components are either identical and disjoint. Overall, the readability of this section is 8/10.
+===== 3.3 Implementing Graph Traversal Using Queues and Stacks =====
+There are two ways to represent a graph: an adjacency matrix and an adjacency list. When discussing nodes and edges, n represents the number of nodes and m the number of edges. The goal run time for graph search algorithms is O(n+m), which is technically referred to as linear time. An adjacency matrix allows us to check in O(1) time if an edge (u, v) is present. However, the representation takes O(n^2) space and checking all incident edges to a node takes O(n) time. An adjacency list requires only O(m + n) list. However, checking if an edge is present takes O(n) time. Returning to the BFS and DFS, BFS effectively uses a queue to select which node to consider next, while DFS uses a stack. A BFS algorithm implementing a queue runs in O(m + n) time, as does a DFS algorithm implementing a stack. Overall, the readability of this section was 6/10.
+===== 3.4 Testing Bipartiteness: An Application of BFS =====
+A bipartite graph is one where its nodes can be separated into sets of either "red" or "blue" nodes such that every edge has a red and blue end. A bipartite graph cannot contain an odd cycle. So, an algorithm that tests for bipartiteness of graphs need only check for odd cycles. This test for bipartiteness algorithm is essentially BFS with the additional step of coloring each layer of nodes and checking whether there is any edge has two ends of the same color. Thus, the run time of this algorithm is O(m + n). Overall, the readability was 7/10.
+===== 3.5 Connectivity in Directed Graphs =====
+When representing directed graphs, we use a modified version of the adjacency list. The search algorithms (BFS and DFS) for undirected graphs are almost the same for directed graphs with slight exceptions. For example, a BFS on nodes and s and t may reveal that a path exists between from s to t AND from t to s. For a directed graph, however, it is not a guarantee that t may have a path to s. An important notion is this section is Strong Connectivity. A graph is strongly connected if every two nodes are mutually reachable -- a path exists from nodes s to t and t to s. An algorithm to test whether a directed graph is strongly connected can be done in linear time. Overall, the readability of this section was 7/10.
+===== 3.6 Directed Acyclic Graphs and Topological Ordering =====
+A DAG is simply a directed graph that has no cycles. DAGs are common structures in computer science. A relatable example is a graph showing prerequisite course requirements for a major, with each node representing a course. If a graph is a DAG, then it must have a topological ordering. A topological ordering is a organization of a graph such that all edges point from left to right. We can use an algorithm that computes a topological ordering for a DAG. First we must find a node with no incoming edges, order it first, then delete it from the graph. We then recursively call the algorithm. The run time for this algorithm is ostensibly O(n^2) because finding a node with no incoming edges takes O(n) time in addition to recursively running the algorithm for n iterations. However, we can reduce this run time to O(m + n) by more efficiently finding a node with no incoming edges. Overall, the readability of this section was 6/10.