Algorithms on Graphs at Coursera Overview
Duration | 55 hours |
Total fee | Free |
Mode of learning | Online |
Difficulty level | Intermediate |
Official Website | Explore Free Course  |
Credential | Certificate |
- Overview
- Highlights
- Course Details
- Curriculum
- Student Reviews
Algorithms on Graphs at Coursera Highlights
- Shareable Certificate Earn a Certificate upon completion
- 100% online Start instantly and learn at your own schedule.
- Course 3 of 6 in the Data Structures and Algorithms Specialization
- Flexible deadlines Reset deadlines in accordance to your schedule.
- Intermediate Level
- Approx. 55 hours to complete
- English Subtitles: Arabic, French, Portuguese (European), Italian, Vietnamese, German, Russian, English, Spanish
Algorithms on Graphs at Coursera Course details
- If you have ever used a navigation service to find optimal route and estimate time to destination, you've used algorithms on graphs. Graphs arise in various real-world situations as there are road networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect set of computers into a network or efficient algorithm to automatically find communities and opinion leaders in Facebook, you're going to work with graphs and algorithms on graphs.
- In this course, you will first learn what a graph is and what are some of the most important properties. Then you'll learn several ways to traverse graphs and how you can do useful things while traversing the graph in some order. We will then talk about shortest paths algorithms-from the basic ones to those which open door for 1000000 times faster algorithms used in Google Maps and other navigational services. You will use these algorithms if you choose to work on our Fast Shortest Routes industrial capstone project. We will finish with minimum spanning trees which are used to plan road, telephone and computer networks and also find applications in clustering and approximate algorithms.
Algorithms on Graphs at Coursera Curriculum
Decomposition of Graphs 1
Graph Basics
Representing Graphs
Exploring Graphs
Connectivity
Previsit and Postvisit Orderings
About University
Welcome
Rules on the academic integrity in the course
Slides and External References
Slides and External References
Decomposition of Graphs 2
Directed Acyclic Graphs
Topological Sort
Strongly Connected Components
Computing Strongly Connected Components
Slides and External References
Paths in Graphs 1
Most Direct Route
Breadth-First Search
Breadth-First Search (continued)
Implementation and Analysis
Proof of Correctness
Proof of Correctness (continued)
Shortest-Path Tree
Reconstructing the Shortest Path
Slides and External References
Paths in Graphs 2
Fastest Route
Naive Algorithm
Dijkstra's Algorithm: Intuition and Example
Dijkstra's Algorithm: Implementation
Dijkstra's Algorithm: Proof of Correctness
Dijkstra's Algorithm: Running Time
Currency Exchange
Currency Exchange: Reduction to Shortest Paths
Bellman-Ford Algorithm
Bellman-Ford Algorithm: Proof of Correctness
Negative Cycles
Infinite Arbitrage
Slides and External References
Slides and External References
Minimum Spanning Trees
Building a Network
Greedy Algorithms
Cut Property
Kruskal's Algorithm
Prim's Algorithm
Slides and External References
Advanced Shortest Paths Project (Optional)
Programming Project: Introduction
Bidirectional Search
Six Handshakes
Bidirectional Dijkstra
Finding Shortest Path after Meeting in the Middle
Computing the Distance
A* Algorithm
Performance of A*
Bidirectional A*
Potential Functions and Lower Bounds
Landmarks (Optional)
Highway Hierarchies and Node Importance
Preprocessing
Witness Search
Query
Proof of Correctness
Node Ordering
Slides and External References
Slides and External References
Slides and External Refernces
Bidirectional Dijkstra, A* and Contraction Hierarchies
Other courses offered by Coursera
Student Forum
Anything you would want to ask experts?