Differences

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

--- courses:cs211:winter2018:journals:martinj:3.2.6 [2018/02/07 04:37] – 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. 3.3 covered implementing graph traversals using queues and stacks, but also covered the different ways to represent graphs themselves.
+.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 30: / Line 28: @@
   * Node m is an ancestor of node n if n was marked as explored after m (I think)
   * 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
-Runtime: O(
-===== Questions =====
 ===== Stuff I want to remember =====
@@ Line 40: / Line 35: @@
 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)
-===== How readable / interesting the section was =====
-.2 was surprisingly easy to read. I liked all the examples equating BFS and DFS to navigating a kind of maze of hallways and rooms.