Data Structures Day 2 Full Notes PDF

Data Structures and Algorithms Full Course Exam training Day 2 | Fatima Hasan | 2023  Plan for Today Graphs Sparse/dense/connectivity Directed/weighted BFS DFS Topological ordering Minimum spanning t...

Data Structures and Algorithms Full Course Exam training Day 2 | Fatima Hasan | 2023  Plan for Today Graphs Sparse/dense/connectivity Directed/weighted BFS DFS Topological ordering Minimum spanning trees Kruskal Prim Dijkstra A* algorithm  Planning Data Directed Directed Graphs BFS DFS structures Weighted Weighted  Graphs A B E vertex C D edge Unordered pair of vertices Set of vertices: V(G) = {A, B, C, D, E} Set of edges: E(G) = {{A,B},{A,C},{B,C},{B,E},{E,D}}  Graphs A graph is connected if for every pair of vertices in the graph, there is a path between the two vertices A B A B E E C D C D Connected Not connected  Graphs A B A B E E C D C D Sparse Dense  Graphs A directed graph G, called a digraph, contains a set of directed edges which has an ordered pair of vertices A B A B E E C D C D Undirected Directed  Graphs: Recap - Graph G contain sets of vertices, V(G), and edges, E(G). - Many properties: sparse if its number of edges is ≈ its number of vertices; m = O(n) - Dense/sparse dense if its number of edges is “much more than” its number of vertices; m = Ω(n 2 ) Connected if for every pair of vertices u, v ∈ V (G) there exist at - Connected/Unconnected least one path between u and v. - Directed/Undirected Each edge of G is an unordered pair of vertices for undirected graphs - Complete/ Not complete Complete graph has edge between every single vertex  Planning Data Directed Directed Graphs BFS DFS structures Weighted Weighted ✓  Representations Array containing a pointer for each Matrix of nxn for n vertices vertex Each entry is 1 if there is a path This pointer points to a list of all Adjacency between two corresponding vertices neighbours of the vertex Adjacency list Otherwise 0 matrix Space complexity is Θ(n + m) Space complexity is Θ(n2) Adj(G) has size n. no matter how many edges are in the graph The total number of nodes in all lists is 2m  Space & Time complexities More space efficient Adjacency List Adjacency Matrix Space complexity Space complexity For a graph G, - For sparse graphs: For sparse graphs: with n vertices Θ(n) - Θ(n2) and m edges - For dense graphs: - For dense graphs: Θ(n2) Θ(n2) - For directed graphs: Takes Θ(1) time for AM Θ(n+m) Takes Ω(n) time for AL Ex. Is there an edge between two More time efficient vertices?  Graph Traversals Testing whether G is connected or not. Given two vertices, compute the path with minimum number of edges between the vertices if it exists Overall running time is O(n + m). Overall running time is O(n+m).  Directed Graph A directed graph G, called a digraph, contains a set of directed edges which has an ordered pair of vertices. We say G is strongly connected if for every pair u, v of vertices in V (G), the pair u, v are connected in G. ○ If you use BFS on graph and algorithm terminates before all vertices are visited then it is not strongly connected. ○ If so, it does not imply that BFS does not visit all vertices of G; it depends on which vertex BFS starts from.  Recap Question Is this graph complete or not complete?  Recap Question Is this graph complete or not complete?  Data structures for graphs Exercise: Make an adjacency-list and matrix for the following graph A B E C D  Planning Data Directed Directed Graphs BFS DFS structures Weighted Weighted ✓ ✓  BFS Breath First Search: Way of traversing a graph Starting from node s, all nodes are visited in order of their distance to s BFS: Example s G A B E C D Queue F A A B C B A C E C A B D E F E B D G F D G E  BFS: Example s G A B E C D Queue F B, C A B C B A C E C A B D E F E B D G Explored: A, F D G E  BFS: Example s G A B E C D Queue F C, E A B C B A C E C A B D E F E B D G Explored: A,B F D G E  BFS: Example s G A B E C D Queue F E A B C B A C E C A B D E F E B D G Explored: A,B,C F D G E  BFS: Example s G A B E C D Queue F D, G A B C B A C E C A B D E F E B D G Explored: A,B,C,E F D G E  BFS: Example s G A B E C D Queue F G, F A B C B A C E C A B D E F E B D G Explored: A,B,C,E,D F D G E  BFS: Example s G A B E C D Queue F F A B C B A C E C A B D E F E B D G Explored: A,B,C,E,D,G F D G E  BFS: Example s G A B E C D Queue F A B C B A C E C A B D E F E B D G Explored: A,B,C,E,D,G,F F D G E  BFS: Exercise Use BFS to traverse the following graph and write down the order in which each node was visited s G A B E C D F  Planning Data Directed Directed Graphs BFS DFS structures Weighted Weighted ✓ ✓ ✓  DFS (iterative) A E Depth First Search: S C Way of traversing a graph Idea: Go forward until you can, if not, backtrack B D Stack S S A B A C S B C D S C A B D E D B C E E C D Explored: ∅ DFS (iterative) A E S C B D Stack S S A B A C S B C D S C A B D E D B C E E C D Explored: ∅ DFS (iterative) A E S C B D Stack S S A B A C S B C D S C A B D E D B C E E C D B S A Explored: S  DFS (iterative) A E S C B D Stack S S A B A C S B C D S C A B D E D B C E S S was already explored, E C D D so remove from stack B C and move to D Explored: S,B A A DFS (iterative) A E S C B D Stack S S A B A C S B C D S C A B D E E D B C E C E C D D B C C A A Explored: S,B,D  DFS (iterative) A E S C B D Stack S S A B A C S B C D S D C A B D E E C D B C E C C D was already explored, E C D B B so remove from stack C C and move to C Explored: S,B,D,E A A  DFS (iterative) A E S C B D Stack S S A B E A C S D B C D S B C A B D E C A D B C E C C E,D,B were already explored, E C D B B so remove from stack C C and move to A Explored: S,B,D,E,C A A  DFS (iterative) A E S C B D Stack S S A B A C S B C D S S C A B D E A C D B C E C C All vertexes were already E C D B B explored, so remove C C them from stack Explored: S,B,D,E,C,A A A  DFS (iterative) A E S C B D Stack S S A B A C S B C D S S C A B D E A C D B C E C C Time complexity B B E C D O(|V|+|E|) C C A A Explored: S,B,D,E,C,A  DFS: Exercise Use DFS to traverse the following graph and write down the order in which each node was visited s G A B E C D F DFS (Recursive)  Planning Data Directed Directed Graphs BFS DFS structures Weighted Weighted ✓ ✓ ✓ ✓ Topological sort  Topological sort Every directed acyclic graph has at least one topological ordering. Every directed acyclic graph has at least one source vertex. It is impossible to topologically order the vertices of a graph that contains a directed cycle. Topological sort Topological sort Topological sort s First pass of the DFS: G B F A E Stack S C D A B C B C F C D D E F D E Explored: G B F Topological sort s First pass of the DFS: G Add D to the stack and assign it 7 B F A E Stack S C D 7 A B C B C F C D D E F D E Explored:D D G B F Topological sort s First pass of the DFS: G Add D to the stack and assign it 7 Backtrack to C and add it to the stack Assign 6 to C B F A E Stack S C D 7 6 A B C B C F C D D E C F D E Explored:D,C D G B F Topological sort s First pass of the DFS: G Add D to the stack and assign it 7 Backtrack to C and add it to the stack Assign 6 to C B F Backtrack to B A E Stack S C D 7 6 A B C B C F C D D E C F D E Explored:D,C D G B F Topological sort s Second pass of the DFS: G B has F unexplored child Explore until E Add E to stack and assign 5 B F 5 A E Stack S C D 7 6 A B C B C F C D D E E C F D E Explored:D,C,E D G B F Topological sort s Second pass of the DFS: G B has F unexplored child Explore until E 4 Add E to stack and assign 5 B F 5 Backtrack to F, add to stack and assign 4 A E Stack S C D 7 6 A B C B C F C D F D E E C F D E Explored:D,C,E,F D G B F Topological sort s Second pass of the DFS: G B has F unexplored child Explore until E 3 4 Add E to stack and assign 5 B F 5 Backtrack to F, add to stack and assign 4 A E Backtrack to B, add to stack and assign 3 Stack S C D 7 Backtrack to G 6 A B C B B C F F C D E D B E C F D E Explored:D,C,E,F,B D G B F Topological sort 2 s Third pass of the DFS: G G has no unexplored children So add G to stack and assign 2 3 4 But we still have untouched vertexes B F 5 A E Stack S C D 7 6 G A B C B B C F F C D E D B E C F D E Explored:D,C,E,F,B,G D G B F Topological sort 2 s Third pass of the DFS: G G has no unexplored children So add G to stack and assign 2 3 4 But we still have untouched vertexes 1 B F 5 So add A to stack and assign it 1 A E Stack S C D 7 6 A G A B C B B C F F C D E D B E C F D E Explored:D,C,E,F,B,G,A D G B F  Topological sort Stack S A G B F E Unstack to get B topological ordering C G D B F A E A G B F E C D C D f-value 1 2 3 4 5 6 7  Planning Data Directed DFS Directed Graphs BFS structures (+TopoSort) Weighted Weighted ✓ ✓ ✓ ✓  Directed Graphs Edges are directed in a directed graph Edges are a ordered pair of vertices A B E Set of vertices: V(G) = {A, B, C, D, E} Set of edges: E(G) = {{C,A},{B,A},{C,B},{B,E},{D,E}} C D  Directed Graphs Edges are directed in a directed graph Edges are a ordered pair of vertices What happens in adjacency-list? Adjacency matrix? A B E C D  Directed Graphs Edges are directed in a directed graph Edges are a ordered pair of vertices Connected, only if there is a directed path between all pairs of vertices A B E C D  Directed Graphs Edges are directed in a directed graph Edges are a ordered pair of vertices Connected, only if there is a directed path between all pairs of vertices A B Strongly connected, if for every pair of vertices u,v there is a path E from u to v, and a path from v to u C D  Weighted Graphs Each edge has a weight 3 A B 7 5 1 E 2 C D  Weighted Graphs Each edge has a weight The length of a path, is the sum of the weights of all edges in the path 3 A B 7 5 1 E 2 C D  Weighted Graphs Each edge has a weight The length of a path, is the sum of the weights of all edges in the path 3 The distance between two vertices is the length A B 7 of the minimal length path between them 5 1 E 2 C D  Recap Question Which properties does this graphs have?  Planning Data Directed DFS Directed Graphs BFS structures (+TopoSort) Weighted Weighted ✓ ✓ ✓ ✓ ✓  Break :) See you back at …  Planning MSTs Prim Kruskal Dijkstra A*  Minimum Spanning Trees Spanning Tree: A connected subgraph of G, that does not contain a cycle A B A B E E C D C D Spanning tree  Minimum Spanning Trees Spanning Tree: A connected subgraph of G, that does not contain a cycle Minimum Spanning Tree: Spanning tree with minimal total weight (only for weighted graphs) 4 4 A B 5 A B 5 3 E 5 E 2 2 C D C D Total weight: 14 Total weight: 16  Planning MSTs Prim Kruskal Dijkstra A* ✓ Prim’s Algorithm  Prim’s Algorithm Example: Find a minimum spanning tree  Prim’s Running Time straightforeward with heap Prim’s Running Time (Heap based) 1. Initialization of keys of vertices takes Θ(n) time. 2. Constructing H takes Θ(n) time. 3. The body of the while loop executes n times. 4. Each Extract-Min takes O(log n) time ⇒ all calls to Extract-Min takes O(n log n) time. 5. The for loop executes Θ(m) times altogether. 6. Access to each vertex in H can be done in Θ(1) time. 7. Updating a key in H takes O(log n) time. 8. Thus, the for loop takes O(m log n) time in total. 9. Overall running time of the algorithm O(n log n + m log n) = O((m+n) log n). Prim: Exercise Prim: Exercise  Planning MSTs Prim Kruskal Dijkstra A* ✓ ✓ Kruskal’s Algorithm  Kruskal’s Algorithm straightforward (Kruskal Run Time (Straightforward)) For every graph G = (V,E) and real-valued edge costs, the straightforward implementation of Kruskal runs in O(mn) time, where m = |E| and n = |V |. (Kruskal Run Time (Union-Find-Based)) Kruskal’s Algorithm ★ Idea of the algorithm: ○ let each vertex of G be a single tree ⇒ G looks like a forest of n trees. ○ Sort the edges of G. ○ Pick the edges of G in order: if their endpoints belong to different trees merge the two trees to build a larger tree. ○ At the end, the forest should contain only one tree Like Prim’s algorithm, it runs in O((m+n) log n) time.  Kruskal’s Algorithm Example: Find a minimum spanning tree Kruskal: Exercise Kruskal: Exercise  Planning MSTs Prim Kruskal Dijkstra A* ✓ ✓ ✓ Evaluation form  Dijkstra’s Algorithm Single-source shortest path problem: Given a directed, weighted graph, find the shortest path from a source vertex v, to each vertex u For every directed graph G = (V,E), every starting vertex s, and every choice of nonnegative edge lengths, the straightforward implementation of Dijkstra runs in O(mn) time, where m = |E| and n = |V | Dijkstra’s Algorithm Single-source shortest path problem: Given a directed, weighted graph, find the shortest path from a source vertex v, to each vertex u G -> I  A* algorithm Len(node) = Len(via previous node) + heuristic(node) A: Len(B) = 6 + 8 Start A Len(F) = 3 + 9 (min) End J A -> F F: Len(G) = (3+1) + 5 = 9 (min) Len(H) = (3+7) + 3 = 13 A -> F -> G G: Len(I) = (3+1+3) + 1 = 8 (min) A -> F -> G -> I I: Len(E) = (3+1+3+5) + 3 = 15 Len(H) = (3+1+3+2) + 3 = 12 Len(J) = (3+1+3+3) + 0 = 10 (goal node) A -> F -> G -> I -> J  A* algorithm The time complexity of A* depends on the heuristic. In the worst case O(bd), where b is the branching factor (the average number of successors per state) and d is the depth of the target node. If a goal state exists and is reachable from the start state; if it is not the algorithm will not terminate. Time complexity is polynomial if we have a tree with a single target node and optimal heuristic. A* is guaranteed to return an optimal solution if, the heuristic function is consistent or monotone. Consistency of heuristic: h(N) ≤ c(N,P)+h(P) h(Goal)=0 N – any node in the graph P – any decendant of N c(N,P) – cost of reaching P from N  A* algorithm The time complexity of A* depends on the heuristic. In the worst case O(bd), where b is the branching factor (the average number of successors per state) and d is the depth of the target node. If a goal state exists and is reachable from the start state; if it is not the algorithm will not terminate. Time complexity is polynomial if we have a tree with a single target node and optimal heuristic. A* is guaranteed to return an optimal solution if, the heuristic function is consistent or monotone. Consistency of heuristic: h(N) ≤ c(N,P)+h(P) h(Goal)=0 N – any node in the graph P – any decendant of N c(N,P) – cost of reaching P from N  Planning MSTs Prim Kruskal Dijkstra A* ✓ ✓ ✓ ✓ ✓  Summary 1. Greedy Algorithms Knapsack problem 2. Graphs Sparse/dense/connectivity Directed/weighted BFS DFS Spanning trees -> Prim + Kruskal Dijkstra A* algorithm  Questions? Slides will be posted in the WhatsApp group :) I’ll create some more practice questions! Good luck on the exam Practical Queston Practical Queston Thank you for your attention!