Outline ′Graphs ′Connected Components [week 5] ′DAGs, Topological Ordering Algorithm: 03Graphs.pdf (P44-51) ′Demo: Topological Ordering Algorithm ′Greedy Algorithms ′Minimum Spanning Tree (MST) [week 5]: 04GreedyAlgorithmsII.pdf (P21-42) ′Prim, Krusal, Reverse-delete [week 5]: (Three greedy strategies to compute MST) 04GreedyAlgorithmsII.pdf (P43-48), 04DemoMST.pdf (P23-66) ′ Interval Scheduling Problem: 04GreedyAlgorithmsI.pdf (P9-15), 04DemoEarliestFinishTimeFirst.pdf ′Divide and Conquer ′Merge Sort: 05DivideAndConquerI.pdf (P1-13), 05DemoMerge.pdf (P1-14) ′Finding Closest Pair of Points: 05DivideAndConquerI.pdf (P63-74) 3 Graphs See separate slides: DAGs, Topological Ordering Algorithm: – “03Graphs.pdf” (P44-51) 4 Proof by Induction 5 Proof by Induction ′Mathematical induction infers that a statement involving a natural number holds for all values of . The proof consists of two steps: ′Base case ′Step case (Inductive Step) 6 Base case ′Prove that the statement holds for the first natural number !. ′Usually, ! = 0 or ! = 1; 7 Step case (Inductive Step) ′Prove that for every ≥ !, if the statement holds for , then it holds for + 1. ′In other words, assume the statement holds for some arbitrary natural number ≥ !, and prove that then the statement holds for + 1. ′Induction/Inductive hypothesis: the statement holds for some ′To prove the inductive step, one assumes the induction hypothesis and then uses this assumption (involving ), to prove the statement for + 1. 8 Demo: Topological Ordering Algorithm 9 Topological order: v1 Demo: Topological Ordering Algorithm10 v2 v3 v6 v5 v4 v7 Topological order: v1 Demo: Topological Ordering Algorithm11 v2 v3 v6 v5 v4 v7 Topological order: v1 v2 Demo: Topological Ordering Algorithm12 v3 v6 v5 v4 v7 Topological order: v1 v2 v3 Demo: Topological Ordering Algorithm13 v6 v5 v4 v7 Topological order: v1 v2 v3 v4 Demo: Topological Ordering Algorithm14 v6 v5 v7 Topological order: v1 v2 v3 v4 v5 Demo: Topological Ordering Algorithm15 v6 v7 Topological order: v1 v2 v3 v4 v5 v6 Demo: Topological Ordering Algorithm16 v7 Topological order: v1 v2 v3 v4 v5 v6 v7 Demo: Topological Ordering Algorithm17 Topological order: v1 v2 v3 v4 v5 v6 v7 v1 Demo: Topological Ordering Algorithm18 v2 v3 v6 v5 v4 v7 v1 v2 v3 v4 v5 v6 v7 Greedy Algorithms See separate slides: Minimum Spanning Tree (MST): [week 5] Three greedy strategies to compute MST: Prim, Krusal, Reverse-delete [week 5] – “04GreedyAlgorithmsII.pdf” (P21-48) – “04DemoMST.pdf” (P23-66) Interval Scheduling Problem: – “04GreedyAlgorithmsI.pdf” (P9-15) – “04DemoEarliestFinishTimeFirst.pdf” 19 Divide and Conquer See separate slides: Merge Sort: – “05DivideAndConquerI.pdf” (P1-13) – “05DemoMerge.pdf” (P1-14) Finding Closest Pair of Points: – “05DivideAndConquerI.pdf” (P63-74) 20 Thank you! 21
