When will I have access to the lectures and assignments?

To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.

What will I get if I subscribe to this Specialization?

When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.

Is financial aid available?

Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.

Graph Search, Shortest Paths, and Data Structures

This course is part of Algorithms Specialization

Instructor: Tim Roughgarden

93,480 already enrolled

4 modules

Gain insight into a topic and learn the fundamentals.

1,998 reviews

Intermediate level

Some related experience required

Flexible schedule

1 week at 10 hours a week

Learn at your own pace

93%

Most learners liked this course

4 modules

Gain insight into a topic and learn the fundamentals.

1,998 reviews

Intermediate level

Some related experience required

Flexible schedule

1 week at 10 hours a week

Learn at your own pace

93%

Most learners liked this course

Skills you'll gain

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

9 assignments

Taught in English

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

Learn more about Coursera for Business

logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

Build your subject-matter expertise

This course is part of the 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

There are 4 modules in this course

The primary topics in this part of the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis).

Module details

Breadth-first and depth-first search; computing strong components; applications.

What's included

9 videos4 readings2 assignments

9 videosTotal 162 minutes

Graph Search - Overview23 minutes
Breadth-First Search (BFS): The Basics14 minutes
BFS and Shortest Paths8 minutes
BFS and Undirected Connectivity13 minutes
Depth-First Search (DFS): The Basics7 minutes
Topological Sort22 minutes
Computing Strong Components: The Algorithm29 minutes
Computing Strong Components: The Analysis26 minutes
Structure of the Web [Optional]19 minutes

4 readingsTotal 40 minutes

Week 1 Overview10 minutes
Overview, Resources, and Policies10 minutes
Lecture slides10 minutes
Optional Theory Problems (Week 1)10 minutes

2 assignmentsTotal 32 minutes

Problem Set #130 minutes
Programming Assignment #12 minutes

Dijkstra's shortest-path algorithm.

What's included

4 videos2 readings2 assignments

4 videosTotal 79 minutes

Dijkstra's Shortest-Path Algorithm21 minutes
Dijkstra's Algorithm: Examples13 minutes
Correctness of Dijkstra's Algorithm19 minutes
Dijkstra's Algorithm: Implementation and Running Time26 minutes

2 readingsTotal 20 minutes

Week 2 Overview10 minutes
Optional Theory Problems (Week 2)10 minutes

2 assignmentsTotal 32 minutes

Problem Set #230 minutes
Programming Assignment #22 minutes

Heaps; balanced binary search trees.

What's included

9 videos1 reading2 assignments

9 videosTotal 141 minutes

Data Structures: Overview5 minutes
Heaps: Operations and Applications18 minutes
Heaps: Implementation Details [Advanced - Optional]21 minutes
Balanced Search Trees: Operations and Applications11 minutes
Binary Search Tree Basics, Part I13 minutes
Binary Search Tree Basics, Part II30 minutes
Red-Black Trees21 minutes
Rotations [Advanced - Optional]8 minutes
Insertion in a Red-Black Tree [Advanced]15 minutes

1 readingTotal 10 minutes

Week 3 Overview10 minutes

2 assignmentsTotal 32 minutes

Problem Set #330 minutes
Programming Assignment #32 minutes

Hashing; bloom filters.

What's included

9 videos3 readings3 assignments

9 videosTotal 171 minutes

Hash Tables: Operations and Applications19 minutes
Hash Tables: Implementation Details, Part I19 minutes
Hash Tables: Implementation Details, Part II22 minutes
Pathological Data Sets and Universal Hashing Motivation22 minutes
Universal Hashing: Definition and Example [Advanced - Optional]26 minutes
Universal Hashing: Analysis of Chaining [Advanced - Optional]19 minutes
Hash Table Performance with Open Addressing [Advanced - Optional]16 minutes
Bloom Filters: The Basics15 minutes
Bloom Filters: Heuristic Analysis13 minutes

3 readingsTotal 30 minutes

Week 4 Overview10 minutes
Optional Theory Problems (Week 4)10 minutes
Info and FAQ for final exam10 minutes

3 assignmentsTotal 62 minutes

Problem Set #430 minutes
Programming Assignment #42 minutes
Final Exam30 minutes

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.

Instructor

Instructor ratings

(131 ratings)

Tim Roughgarden

Stanford University

6 Courses380,984 learners

Offered by

Stanford University

Learner reviews

5 stars
86.09%
4 stars
11.50%
3 stars
1.70%
2 stars
0.25%
1 star
0.45%

Showing 3 of 1998

Reviewed on Jun 8, 2021

Thanks a lot to Prof Roughgarden for great lectures, to course mentors and fellow students for fruitful discussions. It was a hard, but insanely informative course.

Reviewed on Dec 11, 2020

I like the handwritten slides during the lecture. It reminds me of actually sitting in class and the professor developing the material on the chalk board live. Very cool.

Reviewed on Apr 8, 2020

The best algorithms course available. More on the theoretical side which in my opinion is more important, if theory is understood, implementation becomes second nature.

View more reviews