This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engineer.
You will begin with an introduction to the running-time analysis of algorithms and the representation and structure of graphs. You’ll cover the depth-first search algorithm and its many applications, like detecting cycles, topological sorting, and identifying cut-vertices and strongly connected components. You will then cover algorithms for finding shortest paths and minimum spanning trees. You’ll also learn about the Ford-Fulkerson algorithm and its use in finding a maximum flow and minimum cut in networks. Moreover, you will adapt it to find maximum matchings and minimum vertex covers in bipartite graphs. Finally, you will learn about the Gale-Shapley algorithm for finding stable matchings.
The material in this course serves as a basis for other advanced algorithms, like parallel and distributed algorithms, and has many diverse applications in other computing disciplines.
This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engin...Show More
WHAT YOU'LL LEARN
An understanding of classical graph algorithms
The ability to think and visualize in terms of graph structures
An inside-out understanding of what makes each algorithm work the way it does
Cultivation of a broader perspective that informs other computing disciplines
An understanding of classical graph algorithms
Show more
Content
2.
Review: Asymptotic Notation and Math Prerequisites
11 Lessons
Grasp the fundamentals of logarithms, running time, and big-O notation for algorithm analysis.
Getting Started with LogarithmsFood for Thought: Running TimeRunning Time as a Function of Input SizeComparing Running timesBig-O NotationRuminating on Constants in Big-O NotationSome Useful FactsA Big-O DrillLeveraging the Proof by Contradiction TechniqueExercise: Order of GrowthQuiz: Big-O Notation
3.
Working with Graphs
9 Lessons
Work your way through understanding and representing graphs, including adjacency matrices, lists, and special graph types.
4.
Depth-First Search and Applications
16 Lessons
Grasp the fundamentals of Depth-First Search and its applications in graph traversal and analysis.
5.
Prelude: Shortest Paths
7 Lessons
Explore shortest-path strategies, BFS for unweighted digraphs, and apply graph traversal concepts.
6.
Single-source Shortest Paths in Weighted Digraphs
12 Lessons
Focus on solving the single-source shortest paths problem using various algorithms in weighted digraphs.
7.
All Pairs Shortest Paths
5 Lessons
Practice using Johnson's and Floyd-Warshall algorithms for efficient all-pairs shortest paths.
8.
Minimum Spanning Tree
12 Lessons
Learn how to use Minimum Spanning Trees via Prim's and Kruskal's algorithms effectively.
9.
Flows
6 Lessons
Walk through network flows, the Ford-Fulkerson algorithm, and practical exercises.
10.
Matchings and Vertex Covers
11 Lessons
Examine matchings, vertex covers, the Ford-Fulkerson algorithm, and the Gale-Shapley algorithm.
Certificate of Completion
Showcase your accomplishment by sharing your certificate of completion.
Developed by MAANG Engineers
Trusted by 2.8 million developers working at companies
"These are high-quality courses. Trust me. I own around 10 and the price is worth it for the content quality. EducativeInc came at the right time in my career. I'm understanding topics better than with any book or online video tutorial I've done. Truly made for developers. Thanks"
Anthony Walker
@_webarchitect_
"Just finished my first full #ML course: Machine learning for Software Engineers from Educative, Inc. ... Highly recommend!"
Evan Dunbar
ML Engineer
"You guys are the gold standard of crash-courses... Narrow enough that it doesn't need years of study or a full blown book to get the gist, but broad enough that an afternoon of Googling doesn't cut it."
Software Developer
Carlos Matias La Borde
"I spend my days and nights on Educative. It is indispensable. It is such a unique and reader-friendly site"
Souvik Kundu
Front-end Developer
"Your courses are simply awesome, the depth they go into and the breadth of coverage is so good that I don't have to refer to 10 different websites looking for interview topics and content."
Vinay Krishnaiah
Software Developer
Hands-on Learning Powered by AI
See how Educative uses AI to make your learning more immersive than ever before.
AI Prompt
Code Feedback
Explain with AI
AI Code Mentor
Free Resources
