Mini Map
Search
⌘ K
Log In
Mastering Graph Algorithms
0%
1.
Introduction
What Is This Course About?
2.
Review: Asymptotic Notation and Math Prerequisites
Getting Started with Logarithms
Food for Thought: Running Time
Running Time as a Function of Input Size
Comparing Running times
Big-O Notation
Ruminating on Constants in Big-O Notation
Some Useful Facts
A Big-O Drill
Leveraging the Proof by Contradiction Technique
Exercise: Order of Growth
Quiz: Big-O Notation
3.
Working with Graphs
Graphs
Adjacency Matrix
Adjacency List
Directed Graphs
Weighted Graphs
Subgraphs, Paths, Cycles and Components
Trees
Bipartite Graphs
Quiz: Working with Graphs
4.
Depth-First Search and Applications
Depth-First Search
Edge Classification in Directed Graphs
Exercise: Classify Edges of a Directed Graph
Edge Classification in Undirected Graphs
Exercise: Classify Edges of an Undirected Graph
Identifying Cut-Vertices
Exercise: Identify Cut-Vertices
Topological Sorting
Exercise: Sort the Vertices in Topological Order
Thought Exercise: Detecting Cycles in Directed Graphs
Characterizing Strongly Connected Components
Tarjan’s Algorithm
Exercise: Practice Tarjan’s Algorithm
The Kosaraju-Sharir Algorithm
Exercise: Practice the Kosaraju-Sharir Algorithm
Quiz: DFS and Applications
5.
Prelude: Shortest Paths
The Shortest-Paths Problem
Reflections on Shortest Paths
Quiz: Shortest Paths Terminology
Breadth-First Search
Shortest Paths in Unweighted Digraphs
Exercise: Print Shortest Path
Quiz: BFS and Shortest Paths
6.
Single-source Shortest Paths in Weighted Digraphs
Single-Source Shortest-Paths Problem
Exercise: Path-Relaxation
An Immediate Algorithm for DAGs
Thought Exercise: Longest Paths in DAG
Exercise: Shortest Paths in a DAG
Dijkstra’s Algorithm
Exercise: Dijkstra’s Algorithm
Thought Exercise: Negative Weights
The Bellman-Ford Algorithm
Exercise: The Bellman-Ford Algorithm
Thought Exercise: The Bellman-Ford Algorithm
Quiz: Single-Source Shortest-Paths
7.
All Pairs Shortest Paths
Johnson’s Algorithm
Exercise: Johnson’s Algorithm
The Floyd-Warshall Algorithm
Exercise: Floyd-Warshall Algorithm
Quiz: All-Pairs Shortest Paths
8.
Minimum Spanning Tree
What’s an MST?
Quiz: Minimum Spanning Trees
Thought Exercise: Uniqueness
Prim’s Algorithm
Exercise: Select Edges as Specified by Prim’s Algorithm
Exercise: Prim’s Algorithm
Kruskal’s Algorithm
Implementation of Disjoint-Set Data Structure
Exercise: Select Edges as Specified by Kruskal’s Algorithm
Exercise: Kruskal’s Algorithm
Thought Exercise: MSTs and Shortest Paths
Quiz: Minimum Spanning Trees
9.
Flows
Network Flows
The Essence of the Ford-Fulkerson Algorithm
Ford-Fulkerson Algorithm: The Fine Print
Thought Exercise: Rational Capacities
Exercise: The Ford-Fulkerson Algorithm
Quiz: Network Flows
10.
Matchings and Vertex Covers
Matchings
Maximum Matchings in Bipartite Graphs
Exercise: Maximum Matchings in Bipartite Graphs
The Dual Problem of Minimum Vertex Cover
Minimum Vertex Cover in Bipartite Graphs
Exercise: Minimum Vertex Cover in Bipartite Graphs
The Gale-Shapley Algorithm
Proof that the Gale-Shapley Algorithm Favors the Proposers
Thought Exercise: Asymmetry in the Gale-Shapley Algorithm
Exercise: Find Stable Matching
Quiz: Matchings and Vertex Covers
11.
Conclusion
Final Remarks
Project
Premium
Use Simulated Annealing for the Traveling Salesman Problem
Home
Courses
Mastering Graph Algorithms
Thought Exercise: Longest Paths in DAG
Think about how to find a longest path in a DAG.
We'll cover the following...
Principal of reuse
Principal of reuse
...