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