Differences

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

--- courses:cs211:winter2018:journals:martinj:3.2.6 [2018/02/07 04:12] – martinj
+++ courses:cs211:winter2018:journals:martinj:3.2.6 [2018/02/07 04:55] (current) – martinj
@@ Line 2: / Line 2: @@
 ===== Brief summary  =====
-.2 covered graph connectivity and graph traversal, including breadth-first and depth-first searches, which determine s-t connectivity, or whether or not there is a path between s and t in a given graph.
+.2 covered graph connectivity and graph traversal, including breadth-first and depth-first searches, which determine s-t connectivity, or whether or not there is a path between s and t in a given graph. 3.3 covered implementing graph traversals using queues and stacks, but also covered the different ways to represent graphs themselves. 3.4 covered an application of BFS that tested bipartness, and 3.5 covered connectivity in directed graphs. Overall, this section wasn't too difficult for me, as it was pretty readable. However, it did admittedly get progressively more difficult. I honestly think I need more time to let it all sink in before I can conjure up concrete questions to ask.
-===== Motivations =====
 ===== Algorithms: brief sketches, intuitions, implementations, runtimes =====
 ==== Breadth-First Search ====
@@ Line 27: / Line 25: @@
             Endif
         Endfor
+Concepts:
+  * Node m is an ancestor of node n if n was marked as explored after m (I think)
-===== Questions =====
+  * If x & y are two nodes that are connected by an edge in the original graph, but not connected its BFS tree, one of them is an ancestor of the other
 ===== Stuff I want to remember =====
+There are 2 basic ways to represent graphs:
-===== How readable / interesting the section was =====
+  - An adjacency matrix -- requires O(n^2 ) space
+  - An adjacency list representation -- requires only O(m+n) space
+A queue is a set form which we extract elements in FIFO (first in, first out) order = the order in which they were added
+  * Stack = same, but opposite (LIFO)