Buy Now AED 274.99 + VAT

Monthly Subscription Starting at AED 99 + VAT

Algorithms on Graphs
  • Level Professional
  • Duration 55 hours
  • Course by University of California San Diego
  • Offered by

About

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 a 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 online 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.

Modules

Welcome

    • 1 Readings
Show info about module content

1 Readings

  • Welcome

Graph Basics

    • 2 Videos
    • 1 Readings
Show info about module content

2 Videos

  • Graph Basics
  • Representing Graphs

1 Readings

  • Slides and External References

Exploring Undirected Graphs

    • 3 Videos
    • 1 Readings
Show info about module content

3 Videos

  • Exploring Graphs
  • Connectivity
  • Previsit and Postvisit Orderings

1 Readings

  • Slides and External References

Programming Assignment

    • 1 Programming
Show info about module content

1 Programming

  • Programming Assignment 1: Decomposition of Graphs

Directed Graphs

    • 4 Videos
    • 1 Readings
Show info about module content

4 Videos

  • Directed Acyclic Graphs
  • Topological Sort
  • Strongly Connected Components
  • Computing Strongly Connected Components

1 Readings

  • Slides and External References

Programming Assignment

    • 1 Programming
Show info about module content

1 Programming

  • Programming Assignment 2: Decomposition of Graphs

Breadth-First Search

    • 8 Videos
    • 1 Readings
Show info about module content

8 Videos

  • Applications
  • Paths and Distances
  • Breadth-First Search
  • Breadth-First Search (continued)
  • Implementation and Analysis
  • BFS Properties
  • Correct Distances
  • Shortest Path Tree

1 Readings

  • Slides and External References

Programming Assignment

    • 1 Programming
Show info about module content

1 Programming

  • Programming Assignment 3: Paths in Graphs

Fastest Route

    • 7 Videos
    • 1 Readings
Show info about module content

7 Videos

  • Fastest Route
  • Naive Algorithm
  • Dijkstra's Algorithm
  • Dijkstra Example
  • Implementation
  • Proof of Correctness
  • Analysis

1 Readings

  • Slides and External References

Currency Exchange

    • 6 Videos
    • 1 Readings
Show info about module content

6 Videos

  • Currency Exchange
  • Reduction to Shortest Paths
  • Bellman-Ford Algorithm
  • Proof of Correctness
  • Negative Cycles
  • Infinite Arbitrage

1 Readings

  • Slides and External References

Programming Assignment

    • 1 Programming
Show info about module content

1 Programming

  • Programming Assignment 4: Paths in Graphs

Minimum Spanning Trees

    • 5 Videos
    • 1 Readings
Show info about module content

5 Videos

  • Building a Network
  • Greedy Algorithms
  • Cut Property
  • Kruskal's Algorithm
  • Prim's Algorithm

1 Readings

  • Slides and External References

Programming Assignment

    • 1 Programming
Show info about module content

1 Programming

  • Programming Assignment 5: Minimum Spanning Trees

Bidirectional Dijkstra

    • 6 Videos
    • 1 Readings
Show info about module content

6 Videos

  • Programming Project: Introduction
  • Bidirectional Search
  • Six Handshakes
  • Bidirectional Dijkstra
  • Finding Shortest Path after Meeting in the Middle
  • Computing the Distance

1 Readings

  • Slides and External References

A-star Algorithm (A*)

    • 5 Videos
    • 1 Readings
Show info about module content

5 Videos

  • A* Algorithm
  • Performance of A*
  • Bidirectional A*
  • Potential Functions and Lower Bounds
  • Landmarks (Optional)

1 Readings

  • Slides and External References

Contraction Hierarchies

    • 6 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Bidirectional Dijkstra, A* and Contraction Hierarchies

6 Videos

  • Highway Hierarchies and Node Importance
  • Preprocessing
  • Witness Search
  • Query
  • Proof of Correctness
  • Node Ordering

1 Readings

  • Slides and External Refernces

Programming Project

    • 1 Programming
Show info about module content

1 Programming

  • Advanced Shortest Paths

Auto Summary

Explore the fascinating world of graph algorithms with this professional-level course in IT & Computer Science. Taught by expert instructors on Coursera, you'll delve into graph properties, traversal methods, shortest paths, and minimum spanning trees. Ideal for those in navigation, networking, or social media analysis, this comprehensive course spans 3300 minutes and offers flexible subscription options including Starter, Professional, and Paid plans. Perfect for professionals seeking to enhance their skills in efficient algorithm design and application.

Neil Rhodes
Instructors

Neil Rhodes

Daniel M Kane
Instructors

Daniel M Kane

Michael Levin
Instructors

Michael Levin

Michael Levin
Instructors

Michael Levin

Alexander S. Kulikov
Instructors

Alexander S. Kulikov