## Updated: Depth First Search Based Topological Sort

This is Topological Sort, using Depth First Search. It’s the third video in a playlist, following an introduction to topological sorting, and a different, very intuitive algorithm called Kahn’s Algorithm. Before this video, you should watch those two videos, and also the video on depth first search, including the stuff on discovery and finishing times, […]

## Updated: Kahn’s Algorithm for Topological Sorting

This video covers Kahn’s Algorithm for topological sorting. No. Still no. Really? I don’t know if my students know who that is, but they should. Those weren’t spelled right. Before watching this video, you should watch the introduction, especially if you don’t know what topological order is. If you just want the clean, final, linear […]

## Kosaraju’s Algorithm for Strongly Connected Components

This video covers strongly connected components in directed graphs. You should already understand graph basics including depth first search, as well as BOTH topological sorting algorithms. After introducing strongly connected components, I will try to show some intuition of where a linear time algorithm comes from and explain why it works, all with a running […]

## Geometric Series for Algorithms Analysis

Geometric series come up in algorithm analysis, so here’s a freakin’ video. A bunch of versions of the formula are out there, with different levels of complexity and generality, but if you are like me, and have a memory like… uh, what’s that thing? Anyway, if you know where the first one comes from, the […]

## Linear Time BuildHeap

Okay, this is a quick video on building a binary heap, in worst-case linear time, with an elegant proof. Before watching the video, you should understand the introduction to heaps video, where we saw the insertion and heapify methods. Of course, we can build a heap by iterated insertion, that looks great at first, because […]

## Dijkstra’s Single Source Shortest Paths Algorithm with Example

This video covers Dijkstra’s Algorithm for finding Single Source Shortest Paths. After mentioning prerequisites, we will cover what the algorithm accomplishes and get an idea of how it works before seeing the algorithm and its analysis. After an example of it working properly, we’ll see how it fails with negative edges, and cover how to […]

## Kahn’s Algorithm for Topological Sorting

This video covers Kahn’s Algorithm for topological sorting. No. Still no. Really? Okay, nobody watching this even knows who that is, but they should. None of these are even spelled right. Before watching this video, you should watch the introduction, especially if you don’t know what topological order is. If you just want the clean, […]