University of California San Diego

Algorithms on Graphs

This course is part of Data Structures and Algorithms Specialization

Taught in English

Some content may not be translated

Neil Rhodes
Daniel M Kane
Michael Levin

Instructors: Neil Rhodes

113,047 already enrolled

Included with Coursera Plus

Course

Gain insight into a topic and learn the fundamentals

4.7

(2,230 reviews)

|

90%

Intermediate level
Some related experience required
54 hours (approximately)
Flexible schedule
Learn at your own pace

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

1 quiz

Course

Gain insight into a topic and learn the fundamentals

4.7

(2,230 reviews)

|

90%

Intermediate level
Some related experience required
54 hours (approximately)
Flexible schedule
Learn at your own pace

See how employees at top companies are mastering in-demand skills

Placeholder

Build your subject-matter expertise

This course is part of the Data Structures and Algorithms Specialization
When you enroll in this course, you'll also be enrolled in this Specialization.
  • Learn new concepts from industry experts
  • Gain a foundational understanding of a subject or tool
  • Develop job-relevant skills with hands-on projects
  • Earn a shareable career certificate
Placeholder
Placeholder

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV

Share it on social media and in your performance review

Placeholder

There are 6 modules in this course

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 hot in Facebook, you're going to work with graphs and algorithms on graphs. In this module, you will learn ways to represent a graph as well as basic algorithms for decomposing graphs into parts. In the programming assignment of this module, you will apply the algorithms that you’ve learned to implement efficient programs for exploring mazes, analyzing Computer Science curriculum, and analyzing road networks. In the first week of the module, we focus on undirected graphs.

What's included

5 videos3 readings1 programming assignment

This week we continue to study graph decomposition algorithms, but now for directed graphs.

What's included

4 videos1 reading1 programming assignment

In this module you will study algorithms for finding Shortest Paths in Graphs. These algorithms have lots of applications. When you launch a navigation app on your smartphone like Google Maps or Yandex.Navi, it uses these algorithms to find you the fastest route from work to home, from home to school, etc. When you search for airplane tickets, these algorithms are used to find a route with the minimum number of plane changes. Unexpectedly, these algorithms can also be used to determine the optimal way to do currency exchange, sometimes allowing to earh huge profit! We will cover all these applications, and you will learn Breadth-First Search, Dijkstra's Algorithm and Bellman-Ford Algorithm. These algorithms are efficient and lay the foundation for even more efficient algorithms which you will learn and implement in the Shortest Paths Capstone Project to find best routes on real maps of cities and countries, find distances between people in Social Networks. In the end you will be able to find Shortest Paths efficiently in any Graph. This week we will study Breadth-First Search algorithm.

What's included

8 videos1 reading1 programming assignment

This week we continue to study Shortest Paths in Graphs. You will learn Dijkstra's Algorithm which can be applied to find the shortest route home from work. You will also learn Bellman-Ford's algorithm which can unexpectedly be applied to choose the optimal way of exchanging currencies. By the end you will be able to find shortest paths efficiently in any Graph.

What's included

13 videos2 readings1 programming assignment

In this module, we study the minimum spanning tree problem. We will cover two elegant greedy algorithms for this problem: the first one is due to Kruskal and uses the disjoint sets data structure, the second one is due to Prim and uses the priority queue data structure. In the programming assignment for this module you will be computing an optimal way of building roads between cities and an optimal way of partitioning a given set of objects into clusters (a fundamental problem in data mining).

What's included

5 videos1 reading1 programming assignment

In this module, you will learn Advanced Shortest Paths algorithms that work in practice 1000s (up to 25000) of times faster than the classical Dijkstra's algorithm on real-world road networks and social networks graphs. You will work on a Programming Project based on these algorithms. You will find the shortest paths on the real maps of parts of US and the shortest paths connecting people in the social networks. We encourage you not only to use the ideas from this module's lectures in your implementations, but also to come up with your own ideas for speeding up the algorithm! We encourage you to compete on the forums to see whose implementation is the fastest one :)

What's included

17 videos3 readings1 quiz1 programming assignment

Instructors

Instructor ratings
4.5 (174 ratings)
Neil Rhodes
University of California San Diego
7 Courses669,544 learners
Daniel M Kane
University of California San Diego
5 Courses652,411 learners
Michael Levin
University of California San Diego
7 Courses689,133 learners

Offered by

Recommended if you're interested in Algorithms

Why people choose Coursera for their career

Felipe M.
Learner since 2018
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

Showing 3 of 2230

4.7

2,230 reviews

  • 5 stars

    79.31%

  • 4 stars

    16.70%

  • 3 stars

    2.64%

  • 2 stars

    0.80%

  • 1 star

    0.53%

MM
5

Reviewed on Mar 28, 2020

FY
5

Reviewed on Jan 6, 2021

ED
5

Reviewed on Apr 15, 2021

New to Algorithms? Start here.

Placeholder

Open new doors with Coursera Plus

Unlimited access to 7,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Frequently asked questions