Algorithms on Graphs

  • 4.7
Approx. 55 hours to complete

Course Summary

This course covers algorithms on graphs, including shortest paths, spanning trees, and connectivity. Students will learn how to apply these algorithms to real-world problems.

Key Learning Points

  • Learn algorithms on graphs and their applications
  • Understand shortest paths, spanning trees, and connectivity
  • Develop problem-solving skills

Related Topics for further study


Learning Outcomes

  • Apply graph algorithms to real-world problems
  • Design and implement algorithms on graphs
  • Analyze the time complexity of graph algorithms

Prerequisites or good to have knowledge before taking this course

  • Basic knowledge of programming
  • Familiarity with data structures and algorithms

Course Difficulty Level

Intermediate

Course Format

  • Online
  • Self-paced
  • Video lectures
  • Assignments
  • Quizzes

Similar Courses

  • Algorithms and Data Structures
  • Graph Theory
  • Algorithmic Toolbox

Related Education Paths


Notable People in This Field

  • Robert Sedgewick
  • Tim Roughgarden
  • Eva Tardos

Related Books

Description

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.

Outline

  • 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

Summary of User Reviews

Discover the fascinating world of graph algorithms with this Coursera course on Algorithms on Graphs. Users have praised the course for its in-depth explanations and engaging lectures. Many users found the course to be challenging but rewarding, resulting in a deeper understanding of the subject matter.

Key Aspect Users Liked About This Course

In-depth explanations and engaging lectures

Pros from User Reviews

  • Thorough explanations of complex concepts
  • Challenging assignments that test understanding
  • Engaging lectures that keep users interested
  • Well-organized course materials
  • Opportunities for peer-to-peer learning

Cons from User Reviews

  • Some users found the course too difficult for beginners
  • Occasional technical issues with the online platform
  • Limited interaction with course instructors
  • The pace of the course may be too fast for some learners
  • Some users felt that the course lacked practical applications
English
Available now
Approx. 55 hours to complete
Alexander S. Kulikov, Michael Levin, Daniel M Kane, Neil Rhodes
University of California San Diego, HSE University
Coursera

Instructor

Alexander S. Kulikov

  • 4.7 Raiting
Share
Saved Course list
Cancel
Get Course Update
Computer Courses