Graph Algorithms

Course 3 of 8: MicroMasters® Program in Algorithms and Data Structures 6 Weeks 8 - 10 hours each week
856

Please select the start dates for your courses below.

Scheduled Start:

About this course

If you have ever used a navigation service to find the 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, water and electricity supply 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, part of the Algorithms and Data Structures MicroMasters program, you will learn what a graph is and its most important properties. You’ll learn several ways to traverse graphs and how you can do useful things while traversing the graph in some order. We will also talk about shortest paths algorithms. 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.

What you’ll learn

  • Graph exploration and decomposition into connected components
  • Shortest paths algorithms, including breadth-first search, Dijkstra’s algorithm and Bellman-Ford algorithm
  • Minimum spanning tree algorithms

Prerequisites

Basic knowledge of:

 

Who can take this course?

Unfortunately, learners from one or more of the following countries or regions will not be able to register for this course: Iran, Cuba and the Crimea region of Ukraine. While edX has sought licenses from the U.S. Office of Foreign Assets Control (OFAC) to offer our courses to learners in these countries and regions, the licenses we have received are not broad enough to allow us to offer this course in all locations. EdX truly regrets that U.S. sanctions prevent us from offering all of our courses to everyone, no matter where they live.

Meet Your Instructors

Daniel Kane

Assistant Professor,
Computer Science and Engineering & Dept. of Mathematics
UC San Diego

Alexander S. Kulikov

Visiting Professor
UC San Diego

Michael Levin

Chief Data Scientist
Yandex.Market
856

Duration

6 Weeks

Experience Level

Intermediate

Learning Partner

San Diego

Program Type

MicroMasters®
Advanced Business Harvard X-Series