We may earn an affiliate commission when you visit our partners.
Course image
Tim Roughgarden

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

What's inside

Syllabus

Week 1
Breadth-first and depth-first search; computing strong components; applications.
Week 2
Dijkstra's shortest-path algorithm.
Read more
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
This textbook provides a comprehensive and rigorous introduction to algorithms, with a focus on graph theory and its applications.
Show steps
  • Read assigned chapters
  • Complete end-of-chapter exercises
  • Summarize main concepts in your own words
Review minimum spanning tree algorithms
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
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
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
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
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.

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.
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.
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.
Offers an in-depth coverage of graph algorithms in Java. It covers topics such as breadth-first search, depth-first search, and shortest paths, providing a comprehensive resource for those interested in specializing in this area.
Offers a practical approach to data structures and algorithms, with a focus on Java implementation. It covers topics such as heaps, balanced search trees, and hash tables, which are essential for understanding the data structures component of the course.
Offers a classic and concise introduction to algorithms and data structures. It covers topics such as heaps, balanced search trees, and hash tables, providing a solid theoretical foundation.
Provides a comprehensive introduction to graph theory, which is the mathematical foundation for many of the topics covered in the course. It offers a solid theoretical background for understanding graph properties, connectivity, and shortest paths.
Offers a comprehensive coverage of data structures and algorithm analysis in Java. It covers topics such as heaps, balanced search trees, and hash tables, complementing the course's focus on data structures and their applications.
Offers a practical guide to algorithm design, focusing on problem-solving and implementation. It covers topics such as graph algorithms and shortest paths, providing a hands-on approach to complement the course's theoretical focus.
Offers a collection of thought-provoking programming problems and solutions. It covers topics such as graph algorithms and data structures, providing practical insights and challenges to complement the course's focus on algorithms.
Offers a practical and approachable introduction to algorithms. It covers topics such as graph algorithms and shortest paths, providing a clear and concise explanation of these concepts.
Offers a collection of challenging programming problems and their solutions. It covers topics such as graph algorithms and shortest paths, providing a valuable resource for those interested in honing their problem-solving skills.
Offers an engaging and accessible introduction to programming and problem-solving. It covers topics such as graph algorithms and data structures, providing a gentle introduction to these concepts and their applications.

Share

Help others find this course page by sharing it with your friends and followers:

Similar courses

Here are nine courses similar to Graph Search, Shortest Paths, and Data Structures.
Our mission

OpenCourser helps millions of learners each year. People visit us to learn workspace skills, ace their exams, and nurture their curiosity.

Our extensive catalog contains over 50,000 courses and twice as many books. Browse by search, by topic, or even by career interests. We'll match you to the right resources quickly.

Find this site helpful? Tell a friend about us.

Affiliate disclosure

We're supported by our community of learners. When you purchase or subscribe to courses and programs or purchase books, we may earn a commission from our partners.

Your purchases help us maintain our catalog and keep our servers humming without ads.

Thank you for supporting OpenCourser.

© 2016 - 2024 OpenCourser