Post-class 05/29

7 files changed, 328 insertions, 0 deletions

diff --git a/05-27.md b/05-27.md
index 38a2dba..3a617ea 100644
--- a/05-27.md
+++ b/05-27.md
@@ -237,3 +237,7 @@ Insert 8, 6, 7, 5, 3, 0, 9
 		- "yak" is the right child
 
 - This is the AVL tree with most of the entries. Try adding the rest yourself
+
+---
+
+[05/29 ->](05-29.md)
diff --git a/05-29.md b/05-29.md
new file mode 100644
index 0000000..e67f90c
--- /dev/null
+++ b/05-29.md
@@ -0,0 +1,324 @@
+[\<- 05/27](05-27.md)
+
+---
+
+## A Brief Review
+
+- Linear list: each element can have only one successor
+	- Queue, stack
+- Non-linear list: each element can have more than one successors
+	- Tree: Each element (i.e., node) can have only one predecessor
+		- General tree
+		- Binary tree
+			- Binary Search tree
+				- AVL tree
+			- Binary Heap
+	- Graph: Each element can have more than one predecessor
+
+## Trees & Graphs
+
+- A tree is a collection of nodes in which each node has at most **one predecessor** (the parent) but **arbitrarily many successors** (the children)
+- A graph is a collection of nodes in which each node can have an **arbitrary number of both predecessors and successors**
+
+## Graphs - Categories
+
+- Directed & Undirected
+	- vertex is the same as node
+
+![directed and undirected graphs](05-29_img1.png)
+
+- Weighted Graph
+	- There will be a metric on each edge
+
+## Graphs - Cycle / Acyclic
+
+- A **cycle** is a **non-empty** sequence of **distinct** edges from a vertex back to itself
+- A graph without cycles is called **acyclic**
+- Examples
+	- A directed graph is acyclic
+	- An undirected graph might have a cycle
+
+- Can you have a cycle in a two-node undirected graph? how about a line?
+	- No, "distinct edges" remember?
+
+## Graphs
+
+- A directed acyclic graph is called a **dag**
+- Dags are often used to model dependencies
+- For example, we have 6 courses as A, B, C, D, E, F. As shown below,
+	- Course A requires course C as prerequisite
+	- Course B requires course C and F as prerequisite
+	- Course C requires course D and E as prerequisite,
+	- ...
+
+### Example
+
+- Example dependencies:
+	- Get up in the morning -- 1
+	- Take a Shower -- 2
+	- Put on Shoes -- 3
+	- Put on Socks -- 4
+	- Put on Underwear -- 5
+	- Put on Pants -- 6
+	- Put on Shirt -- 7
+
+- Draw the Graph:
+
+![the graph visualized](05-29_img2.png)
+
+- A graph is called **planar** if it can be drawn in a single plane with no edges crossing
+	- loved by EE majors for obvious reason
+
+- A graph in which each vertex is connected to every other vertex is called a **clique**. Are the following cliques planar?
+	- three-clique? **yes**
+	- four-clique? **yes**
+	- five-clique? **no**
+
+- When discussing graphs we use two variables
+	- V = # of vertices
+	- E = # of edges
+- Is there any relationship between V and E?
+
+- Assume that our graph is directed. What is the max # of edges given V?
+	- V^2 (or V(V-1) if you ignore self loops)
+- Assuming it's undirected (and no self-loops)?
+	- (V(V-1))/2
+- So big-O of E is O(V^2)
+
+- A graph is called **sparse** if E is much less than V^2, and is called **dense** if E is close to V^2
+- Question: for any airline map between 30 airports in reality, is it dense?
+	- Does, for example, Southwest fly 900 routes?
+
+---
+
+# Graph Representations
+
+## Adjacency Matrix
+
+- **adjacency matrix**:
+	- `a[i][j] <> 0 iff i -> j`
+
+- Example:
+
+![example graph](05-29_img3.png)
+
+|     |A|B|C|D|E|F|
+|-----|-|-|-|-|-|-|
+|**A**|0|0|1|0|0|0|
+|**B**|0|0|1|0|0|1|
+|**C**|0|0|0|1|1|0|
+|**D**|0|0|0|0|0|0|
+|**E**|0|0|0|0|0|0|
+|**F**|0|0|0|0|1|0|
+
+- The meaning of "sparse" should be starkly clear in the matrix
+
+- How about undirected graph?
+	- Always symmetric
+
+- How about space complexity?
+	- O(V^2)
+
+## Adjacency List
+
+- **Adjacency List**
+	- Using the graph above:
+	- A: {C}
+	- B: {C, F}
+	- C: {D, E}
+	- D: {}
+	- E: {}
+	- F: {E}
+
+- How about undirected graph?
+	- A: {C}
+	- B: {C, F}
+	- C: {A, B, D, E}
+	- etc.
+
+- What is the space complexity?
+	- Notice that the number of entries reflects E
+	- O(E) space complexity for adjacency list
+
+## Exercise
+
+|     |A|B|C|D|E|F|
+|-----|-|-|-|-|-|-|
+|**A**|0|0|1|0|0|0|
+|**B**|0|0|1|0|1|1|
+|**C**|0|0|0|1|1|0|
+|**D**|0|0|1|0|0|0|
+|**E**|0|0|0|0|0|0|
+|**F**|0|0|1|0|1|0|
+
+- Given the adjacency matrix, answer the following questions
+	1. What is the adjacency list?
+		- A: {C}
+		- B: {C, E, F}
+		- C: {D, E}
+		- D: {C}
+		- E: {}
+		- F: {C, E}
+
+	2. Is the graph directed or undirected?
+		- directed
+
+	3. Draw the graph:
+
+![Graph Visualization](05-29_img4.png)
+
+Time Complexity:
+	- Given a Vertex A, what are the adjacent nodes?
+		- Adjacency Matrix: Always O(V)
+		- Adjacency list: Worst-case O(V), depends on the graph sparseness
+	- Find if edge A-\>B exist in the graph?
+		- Adjacency matrix: O(1)
+		- Adjacency list: Worst-case O(V)
+
+## Comparison
+
+- Space complexity:
+	- Adjacency matrix: O(V^2)
+	- Adjacency list: O(E)
+	- Which one could save more space for a sparse graph?
+- Time Complexity:
+	- Determining the presence of an edge
+		- **Adjacency matrix** is faster (O(1))
+	- Determining the list of all adjacent nodes
+		- **Adjacency list** is faster on average, worst-case O(V)
+
+- Recommendations:
+	- If sparse: list
+	- If dense: matrix
+	- Note that most graphs will be sparse
+
+## Requirements/Expectation
+
+- Given a graph, be able to provide its adjacency matrix & adjacency list
+- Given an adjacency matrix (or adjacency list), be able to draw the graph
+- Understand the differences in adjacency matrices/lists for directed graph & undirected graph
+- Compare adjacency matrix & adjacency list (space and time)
+
+---
+
+## Graphs - When to use it?
+
+- Examples:
+	- Maps
+	- Online Social Networks
+	- Neural Networks
+
+# Graph Traversals
+
+## Graph Algorithms - Traversal
+
+- We want to visit all nodes in a graph
+- Challenge: unlike trees
+	- graphs can have cycles,
+	- and more than one way to visit the same node...
+- Both issues demand that we **avoid visiting the same node**
+	- We need to avoid cycles and avoid repeats
+	- We will solve these problems by marking each vertex
+
+- Review of preorder traversal:
+
+```
+void visit(n){
+	if(n is not empty){
+		print n;
+		for each child ch of n do visit(ch);
+	}
+}
+```
+
+- This code will not work on a graph
+	- Could visit a node multiple times
+	- Could loop forever
+
+- Modification of preorder traversal
+
+```
+void visit(n){
+	label n as marked
+	print n
+	for each adjacent node adj of n do{
+		if(adj is no marked) visit(adj)
+	}
+}
+```
+
+- This code will work on a graph:
+	- A node will only be marked once
+	- So we cannot visit a node more than once and accidently print it twice or get stuck in a cycle
+
+- We just covered **depth-first search**/traversal. **DFS**
+- So called because you down as far as you can before you backtrack and try another option
+- The robot in the maze game used this algorithm: it explored as far as it could before backtracking
+
+![example graph](05-29_img5.png)
+
+- Using the example graph above, show the DFS order starting from A
+	- A, C, D, B, F, E
+- Not do a DFS from B
+	- B, E, F, C, A, D
+- Now do a DFS from F
+	- F, B, C, A, D, E
+
+- DFS was recursive and therefore used a **stack**
+- You can either make your function recursive and let the system take care of it
+- Or you can make your own stack (that's what we did for the maze game)
+- Another logical choice is to use a **queue**
+- In this case, we'll have to make our own queue and maintain it as we go along
+
+- Modification of traversal:
+
+```
+void visit(n){
+	label n as marked and add it to the queue
+	
+	while(the queue is not empty) do{
+		let n be the result of dequeue
+		for each adjacent node adj of n do{
+			if(adj is not marked) label adj as marked and add it to the queue
+		}
+	}
+}
+```
+
+- This code will work on a graph:
+	- It will only add a node to the queue if it hasn't already been marked
+
+- We just covered **breadth-first search**/traversal, **BFS**
+- It is so called because instead of going down, you go across
+- Proceed all the neighbors at distance 1, then all from distance 2, etc.
+
+![example graph](05-29_img5.png)
+
+- Example: BFS starting from A
+	- A, C, B, D, F, E
+	- Notice as you print nodes, the nodes are farther and farther away from A
+		- A is distance 0
+		- C is distance 1
+		- B, D, E are distance 2
+		- F is distance 3
+- Example: BFS starting from E
+	- E, C, F, A, B, D
+- Example: is the traversal (starting from A) BFS or DFS?
+	- A, C, D, B, F, E
+	- it is DFS
+	- can it also be BFS? NO (it would not output F before E)
+
+- Relation to Trees
+	- DFS reflects preorder
+	- BFS reflects level by level
+
+## Requirements/Expectations
+
+- Given a graph, be able perform a depth-first and breadth-first search
+- Understand when you would choose one over other
+- What is the complexity of each algorithm
+	- We only print out each node once
+	- However, we may have to check a node multiple times
+	- How many times? That depends on how many edges lead to it
+	- Although we print out each node only once, we must examine every edge in the graph
+	- So, the complexity of DFS and BFS is O(V+E). (The V comes from the face that we have to initially unmark all vertices before we start a search)
diff --git a/05-29_img1.png b/05-29_img1.png
new file mode 100644
index 0000000..aea215f
--- /dev/null
+++ b/05-29_img1.png
diff --git a/05-29_img2.png b/05-29_img2.png
new file mode 100644
index 0000000..e14422f
--- /dev/null
+++ b/05-29_img2.png
diff --git a/05-29_img3.png b/05-29_img3.png
new file mode 100644
index 0000000..bb383f4
--- /dev/null
+++ b/05-29_img3.png
diff --git a/05-29_img4.png b/05-29_img4.png
new file mode 100644
index 0000000..8ff7a6a
--- /dev/null
+++ b/05-29_img4.png
diff --git a/05-29_img5.png b/05-29_img5.png
new file mode 100644
index 0000000..ecc9a64
--- /dev/null
+++ b/05-29_img5.png