• Specialization: Data Science Foundations: Data Structures and Algorithms
• Instructor: Sriram Sankaranarayanan, Assistant Professor
• Prior knowledge needed: We highly recommended successfully completing Algorithms for Searching, Sorting, and Indexing (the first course in this specialization) before attempting this course.
• Mathematical Background: We expect that the student is comfortable with basic mathematics at the level of a U.S. first-year college STEM student. This includes basic notions such as sets and functions: Properties of sets, definition and properties of functions; logarithms and exponentials: and their properties; basic series summations: arithmetic and geometric series summations; and probability theory: basic definition of probability, independence of events, probability distributions and expectations.  CLRS has a helpful appendix but the student unfamiliar with these concepts can find numerous high quality explanations online.
• Programming Background: The course involves solving programming assignments in Python. You must be comfortable with Python programming. This includes basic control structures in Python: conditional branches, for loops and recursion; functions: defining and calling functions, and recursion; in-built data structures: lists and dictionaries; and classes. Our use of Python will get more sophisticated as the course progresses to accommodate some learning of Python.

## Learning Outcomes

• Define basic tree data structures and identify algorithmic functions associated with them
• Execute traversals and create graphs within a binary search tree structure
• Describe strongly connected components in graphs

## Course Content

Duration: 9h

In this module, you will learn about binary search trees and basic algorithms on binary search trees. We will also become familiar with the problem of balancing in binary search trees and study some solutions for balanced binary search trees such as Red-Black Trees.

Duration: 8h

In this module, you will learn about graphs and various basic algorithms on graphs such as depth first/breadth first traversals, finding strongly connected components, and topological sorting.

Duration: 8h

Union Find Data-structure with rank compression. Spanning trees and properties of spanning trees.Prim’s algorithm for finding minimal spanning trees. Kruskal’s algorithm for finding minimal spanning trees.

Duration: 8h

In this module, you will learn about:Shortest Path Problem: Basics.Bellman-Ford Algorithm for single source shortest path.Dijkstra’s algorithm.Algorithms for all-pairs shortest path problem (Floyd-Warshall Algorithm)

Duration: 1h 30m

This module contains materials for the final exam for MS-DS degree students. If you've upgraded to the for-credit version of this course, please make sure you review the additional for-credit materials in the Introductory module and anywhere else they may be found.

Note: This page is periodically updated. Course information on the Coursera platform supersedes the information on this page. Click View on Coursera button above for the most up-to-date information.