You may want to download the lecture slides that were used for these videos (PDF).

1. A Networking Problem

This video introduces a networking problem and asks some motivating questions. We will study two approaches to solve it. (7:05)

2. Kruskal’s Algorithm

This video gives the first solution to the networking problem, Kruskal’s Algorithm. (11:32)

3. Prim’s Algorithm (Build Tree)

In this video we give another algorithm for solving the networking problem. (5:21)

4. The Mathematics Behind the Algorithms

We will explain why Kruskal (avoid cycles) and Prim (build tree) work as intended. This will be done over several videos, and underlying principles are drawn from linear algebra, but now with a finite field rather than with the more familiar fields of real numbers and complex numbers. (2:38)

5. The Exchange Principle

We start by considering a spanning tree T in a graph G. (7:10)

6. A New Kind of Vector Space

Let G be a connected graph, and let E be the edge set of G. We consider subsets of E and call a subset S independent if it contains no cycles. Note that the maximal independent sets are the spanning trees of G. (2:07)

7. Constrained Spanning Trees

We continue our explanation of why Kruskal (avoid cycles) and Prim (build tree) work. Now we discuss a modified version of the original problem. (2:30)

8. Fundamental Lemma

This video introduces a lemma, and gives an outline of its proof. (7:12)

9. Applying the Exchange Principle

This video describes how we can use the exchange principle to show that different solutions to an optimization problem with multiple optimal solutions, are optimal. (4:40)

10. The Correctness of Kruskal’s and Prim’s Algorithms

This video describes the correctness of Kruskal’s and Prim’s algorithms. (8:28)

11. Data Structure and Computational Issues

We discuss some of the practical issues in implementing Kruskal’s and Prim’s algorithms. (4:07)

12. Finding Shortest Paths

This video introduces a constrained optimization problem, which is to find a particular route in a connected digraph whose edges have non-negative weights. (5:23)

13. Dijkstra’s Algorithm

This video introduces Dijkstra’s Algorithm and discusses how it works. In next week’s videos, we will see why this algorithm works. (9:28)

Additional Resources

At the beginning of the following week, Dr. Trotter reviewed some of this week’s material. You may find the following videos helpful in getting a better understanding of the material in Week 22.

14. Review

This video reviews the exchange principle, constrained spanning trees, and the fundamental lemma. (5:09)

15. Review – Applying the Exchange Principle

This video reviews the proof of the exchange principle. (5:45)

16. Review – Dijkstra’s Algorithm and Shortest Paths

This video reviews Dijkstra’s Algoritm and how it works. (6:34)

17. Review – The Correctness of the Algorithm (1)

This video discusses a proof related to Dijkstra’s Algorithm that we will complete in the next lecture. (2:35)

18. Review – The Correctness of the Algorithm (2)

This video goes into more detail on the proof related to Dijkstra’s Algorithm that we complete in the next lecture. (4:50)