summaryrefslogtreecommitdiff
path: root/05-29.md
diff options
context:
space:
mode:
Diffstat (limited to '05-29.md')
-rw-r--r--05-29.md324
1 files changed, 324 insertions, 0 deletions
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)