We may earn an affiliate commission when you visit our partners.

Graph Search, Shortest Paths, and Data Structures

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).

Enroll now

Or subscribe to Coursera Plus

And get unlimited access to Coursera

Two deals to help you save

We found two deals and offers that may be relevant to this course.

Save money when you learn. All coupon codes, vouchers, and discounts are applied automatically unless otherwise noted.

Valid for a limited time only

Future-proof your career

Access O'Reilly books, live events, courses, and more. Save with an annual subscription.

Take

15%

off

What's inside

Syllabus

Week 1

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

Week 2

Dijkstra's shortest-path algorithm.

Week 3

Heaps; balanced binary search trees.

Week 4

Hashing; bloom filters.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Develops the core algorithmic constructs of computer science

Taught by Tim Roughgarden who is recognized for their contributions to theoretical computer science and algorithmic theory

Provides a balance between breadth and depth of study by teaching algorithmic constructs and their immediate applications

Useful for students of computer science and related fields

Not explicitly intended for beginners or experts

Save this course

Save Graph Search, Shortest Paths, and Data Structures to your list so you can find it easily later:

Save

Reviews summary

Algorithms & data structures: intermediate

Learners say graph search, shortest paths, and data structures are explained in detail with examples. The programming assignments are thought-provoking, especially the hash problem set and week 4 assignment. Professor Roughgarden is engaging and clear in his lectures, making the difficult concepts understandable. Overall, this course is well-received by learners and is highly recommended for computer science students and those interested in algorithms and data structures.

Professor Roughgarden captivates learners with his teaching style.

"Tim really did an awesome job preparing the lectures for this course. Material was presented quickly, efficiently, and engagingly. I highly recommend this class."

"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."

Mind-bending assignments that push your limits.

"Very helpful and informative. Thank you so much!"

"Even better than the first course in specialization! "

"This course forced me to think algorithmically and design efficient code! Thank you!"

"I think the course taught me a lot of things. i learnt a lot. thank you. "

"Good course! Programming assignments were more challenging than the previous course which is good!"

Concepts are made understandable through detailed explanations and examples.

"Great Course - good examples - always going to the point - clear and providing good information."

"The course was very interesting. As a person who struggles with problem-solving, I found this course very helpful because the professor's ideas are well explained. It makes me to learn more."

"It makes you think about the algorithm in a low level, which helps in building the understanding how and why an algorithm works."

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Graph Search, Shortest Paths, and Data Structures with these activities:

Introduction to Algorithms, 4th Edition

Show steps

This textbook provides a comprehensive and rigorous introduction to algorithms, with a focus on graph theory and its applications.

View Introduction to Algorithms, fourth edition on Amazon

Show steps

Read assigned chapters
Complete end-of-chapter exercises
Summarize main concepts in your own words

Review minimum spanning tree algorithms

Show steps

Reviewing this algorithm prior to beginning this course will help solidify the concepts and prepare you for delving deeper into graph theory.

Show steps

Research background and applications
Implement algorithms in your preferred programming language

Depth-first search tutorial

Show steps

This course covers depth-first search in detail, so it's beneficial to have a foundational understanding of the concepts. This tutorial will get you up to speed.

Browse courses on Depth-first Search

Show steps

Watch the tutorial video
Follow along with the code examples
Complete the practice exercises

Four other activities

Expand to see all activities and additional details

Show all seven activities

Breadth-first search practice

Show steps

Practice makes perfect! Perform several sample problems on graph theory to gauge your understanding and identify areas for improvement.

Browse courses on Breadth-First Search

Show steps

Find online practice problems on reputable websites like Leetcode or Hackerrank
Solve problems using one or more algorithms for breadth first search
Identify pain points and seek out additional resources

Data structure cheat sheet

Show steps

Creating your own cheat sheet will help you quickly reference and better understand data structures.

Browse courses on Data Structures

Show steps

Gather resources and examples
Organize and structure the cheat sheet
Review and iterate

Study group

Show steps

Participating in a study group will provide opportunities to discuss course concepts, work through problems together, and clarify misunderstandings.

Show steps

Find a group of peers with similar learning goals
Establish a regular meeting schedule
Prepare for each session by reviewing materials

Contribute to a graph library

Show steps

By contributing to an existing library, you will deepen your understanding of advanced graph theory algorithms and libraries and contribute to the community.

Browse courses on Graph Theory

Show steps

Find an existing graph library
Identify areas for improvement or new features
Submit a pull request with your changes

Career center

Learners who complete Graph Search, Shortest Paths, and Data Structures will develop knowledge and skills that may be useful to these careers:

Software Engineer

Software Engineers design, develop, and test software applications. They work with code, data structures, and algorithms to create functionally sound, high-quality software. Software Engineers typically need at least a bachelor's degree in computer science or a related field, but the requirements may vary by industry. Graph Search, Shortest Paths, and Data Structures can be an excellent resource for Software Engineers because of its focus on applying data structures for solving problems.

See salaries and explore the career path for Software Engineer

Data Analyst

Data Analysts collect, clean, and analyze data to uncover insights and trends. They use their findings to make recommendations for businesses and organizations. Data Analysts typically need at least a bachelor's degree in a field like statistics, computer science, or a related field. Graph Search, Shortest Paths, and Data Structures can help Data Analysts build a foundation in working with data, making it an excellent addition to their skill set.

See salaries and explore the career path for Data Analyst

Database Administrator

Database Administrators design, build, and maintain databases. They ensure that data is stored securely and efficiently, and that it is accessible to those who need it. Database Administrators typically need at least a bachelor's degree in computer science or a related field, and they often hold certifications in database management. Graph Search, Shortest Paths, and Data Structures provides an excellent foundation for Database Administrators as it covers the fundamentals of data management and storage.

See salaries and explore the career path for Database Administrator

Data Engineer

Data Engineers design, build, and maintain data pipelines. They work with data from a variety of sources, including relational databases, NoSQL databases, and cloud storage. Data Engineers typically need at least a bachelor's degree in computer science or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures provides Data Engineers with a foundational knowledge of data structures and algorithms, which can be applied to data pipeline design and implementation.

See salaries and explore the career path for Data Engineer

Data Scientist

Data Scientists use data to solve business problems. Working with data from a variety of sources, they clean, analyze, and model data to identify trends, patterns, and insights. Data Scientists need at least a master's degree, typically in a field like computer science, mathematics, or statistics. Those with a strong quantitative background may also qualify for Data Scientist roles. Graph Search, Shortest Paths, and Data Structures can be a valuable course to add to a Data Scientist's skill set.

See salaries and explore the career path for Data Scientist

Research Scientist

Research Scientists study phenomena in fields like biology, chemistry, and physics. They design the experiments, conduct them, and analyze the results. They often publish their findings or present them at conferences. Research Scientists generally need a master's degree in their field or a related field. Graph Search, Shortest Paths, and Data Structures can help build a foundation for a career in research science as it teaches the skills for designing experiments, working with data, and presenting your findings.

See salaries and explore the career path for Research Scientist

Software Architect

Software Architects design and develop the overall architecture of software systems. They work with teams of engineers to ensure that systems are scalable, reliable, and secure. Software Architects typically need at least a bachelor's degree in computer science or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures provides Software Architects with a foundational knowledge of data structures and algorithms, which can be applied to software architecture design.

See salaries and explore the career path for Software Architect

Computer Systems Analyst

Computer Systems Analysts study the needs of an organization and design and implement computer systems to meet those needs. They work with stakeholders to gather requirements, design solutions, and implement and test systems. Computer Systems Analysts typically need at least a bachelor's degree in computer science or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures can provide Computer Systems Analysts with the foundational knowledge of data structures and algorithms, which can be applied to systems design and implementation.

See salaries and explore the career path for Computer Systems Analyst

Web Developer

Web Developers design, build, and maintain websites. They work with design teams to create the visual look and feel of a website, and they work with programmers to implement the functionality. Web Developers typically need at least a bachelor's degree in computer science or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures provides Web Developers with a solid foundation in data structures and algorithms, which can be applied to web design and development.

See salaries and explore the career path for Web Developer

Quantitative Analyst

Quantitative Analysts use mathematical and statistical models to analyze financial data and provide investment recommendations. They work with data from a variety of sources, including financial statements, market data, and economic data. Quantitative Analysts typically need at least a master's degree in a field like mathematics, statistics, or finance. Graph Search, Shortest Paths, and Data Structures provides a good foundation for Quantitative Analysts as it covers the fundamentals of data analysis and modeling.

See salaries and explore the career path for Quantitative Analyst

Operations Research Analyst

Operations Research Analysts use mathematical and statistical models to solve business problems. They work on projects ranging from supply chain optimization to workforce scheduling. Operations Research Analysts typically need at least a master's degree in operations research, industrial engineering, or a related field. Graph Search, Shortest Paths, and Data Structures can provide Operations Research Analysts with a foundational knowledge of data structures and algorithms, which can be applied to modeling and optimization.

See salaries and explore the career path for Operations Research Analyst

Information Security Analyst

Information Security Analysts design, implement, and maintain security measures to protect an organization's computer systems and networks. They work with management to assess risks, and they develop and implement policies and procedures to mitigate those risks. Information Security Analysts typically need at least a bachelor's degree in computer science or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures can provide Information Security Analysts with a solid foundation in data structures and algorithms, which can be applied to security design and implementation.

See salaries and explore the career path for Information Security Analyst

Mobile App Developer

Mobile App Developers design, build, and maintain mobile applications. They work with design teams to create the visual look and feel of an app, and they work with programmers to implement the functionality. Mobile App Developers typically need at least a bachelor's degree in computer science or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures provides Mobile App Developers with a solid foundation in data structures and algorithms, which can be applied to mobile app design and development.

See salaries and explore the career path for Mobile App Developer

Business Analyst

Business Analysts work with stakeholders to understand their business needs and design and implement solutions to meet those needs. They may work on projects ranging from process improvement to software implementation. Business Analysts typically need at least a bachelor's degree in business administration or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures can provide Business Analysts with foundational knowledge of data structures and algorithms, which can be applied to business process analysis and design.

See salaries and explore the career path for Business Analyst

User Experience Designer

User Experience Designers design the look and feel of products and services. They work with teams of engineers and designers to create products that are easy to use and enjoyable to interact with. User Experience Designers typically need at least a bachelor's degree in design or a related field, and additional certifications may be required for specialized roles. Graph Search, Shortest Paths, and Data Structures provides User Experience Designers with a foundational knowledge of data structures and algorithms, which can be applied to the design of user interfaces.

See salaries and explore the career path for User Experience Designer

Reading list

We've selected 13 books that we think will supplement your learning. Use these to develop background knowledge, enrich your coursework, and gain a deeper understanding of the topics covered in Graph Search, Shortest Paths, and Data Structures.

Introduction to Algorithms, fourth edition

Save

This classic textbook provides a comprehensive overview of algorithms and data structures. It covers topics such as graph algorithms, shortest paths, and data structures in depth, making it a valuable resource for further exploration beyond the course.

Introduction to Algorithms, fourth edition

Hardcover

$$$$

Introduction to Algorithms, fourth edition

Kindle Edition

$$$

Introduction to Programming in Java

Save

Offers a comprehensive overview of graph algorithms, including topics covered in the course, such as breadth-first search, depth-first search, shortest paths, and data structures. It provides a solid theoretical foundation for the course.

Graph Search, Shortest Paths, and Data Structures

Two deals to help you save

What's inside

Syllabus

Good to know

Save this course

Reviews summary

Algorithms & data structures: intermediate

Activities

Career center

Reading list

Share

Similar courses