• 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 and Trees and Graphs: Basics (the 1st and 2nd courses 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. 

View on Coursera

Learning Outcomes 

  • Describe basic algorithm design techniques.
  • Create divide and conquer, dynamic programming, and greedy algorithms.
  • Understand intractable problems, P vs NP and the use of integer programming solvers to tackle some of these problems.

Course Content

Duration: 11h

We will formally cover divide and conquer algorithms as a design scheme and look at some divide and conquer algorithms we have encountered in the past. We will learn some divide and conquer algorithms for Integer Multiplication (Karatsuba’s Algorithm), Matrix Multiplication (Strassen’s Algorithm), Fast Fourier Transforms (FFTs), and Finding Closest Pair of Points.

Duration: 9h

In this module, you will learn about dynamic programming as a design principle for algorithms. We will provide a step-by-step approach to formulating a problem as a dynamic program and solving these problems using memoization. We will cover dynamic programming for finding longest common subsequences, Knapsack problem  and some interesting dynamic programming applications.

Duration: 7h

In this module,  we will learn about greedy algorithm. We will understand the basic design principles for greedy algorithms and learn about a few algorithms for greedy scheduling and Huffman codes. We will also learn some interesting cases when being greedy provides a guaranteed approximations to the actual solution.

Duration: 11h

 P vs NP,  Examples such as Travelling Salesperson Problem, Vertex Cover, 3-Coloring and others; Integer Linear Programming and Translating Problems into Integer Programming.

Duration: 1h 30m

You will complete a programming assignment worth 10% of your grade. You must attempt the final in order to earn a grade in the course. 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.