Dynamic Programming, Greedy Algorithms (Coursera)

Dynamic Programming, Greedy Algorithms (Coursera)

This course covers basic algorithm design techniques such as divide and conquer, dynamic programming, and greedy algorithms. It concludes with a brief introduction to intractability (NP-completeness) and using linear/integer programming solvers for solving optimization problems. We will also cover some advanced topics in data structures.

Class Deals by MOOC List - Click here and see Coursera's Active Discounts, Deals, and Promo Codes.

Dynamic Programming, Greedy Algorithms can be taken for academic credit as part of CU Boulder’s Master of Science in Data Science (MS-DS) degree offered on the Coursera platform. The MS-DS is an interdisciplinary degree that brings together faculty from CU Boulder’s departments of Applied Mathematics, Computer Science, Information Science, and others. With performance-based admissions and no application process, the MS-DS is ideal for individuals with a broad range of undergraduate education and/or professional experience in computer science, information science, mathematics, and statistics.
Course 3 of 3 in the Data Structures and Algorithms Specialization.

What You Will Learn

  • 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

Syllabus

WEEK 1
Divide and Conquer Algorithms
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.

WEEK 2
Dynamic Programming Algorithms
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.

WEEK 3
Greedy Algorithms
In this module, we will learn about greedy algorithms. 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 approximation to the actual solution.

WEEK 4
Intractability and Supplement on Quantum Computing
P vs NP, Examples such as Travelling Salesperson Problem, Vertex Cover, 3-Coloring and others; Integer Linear Programming and Translating Problems into Integer Programming.

Go to Class
MOOC List is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Related Courses

Machine Learning Rapid Prototyping with IBM Watson Studio (Coursera) Coursera
IBM

Machine Learning Rapid Prototyping with IBM Watson Studio (Coursera)

An emerging trend in AI is the availability of technologies in which automation is used to select a best-fit model, perform feature engineering and improve model performance via hyperparameter optimization. This automation will provide rapid-prototyping of models and allow the Data Scientist to focus their efforts on applying domain knowledge to fine-tune models. This course will take the learner through the creation of an end-to-end automated pipeline built by Watson Studio’s AutoAI experiment tool, explaining the underlying technology at work as developed by IBM Research.

Dec 7th 2026
4 Weeks
Introduction to Open Source Application Development (Coursera) Coursera
Illinois Tech

Introduction to Open Source Application Development (Coursera)

This course introduces basic concepts of systems programming using a modern open source language. You will learn to apply basic programming concepts toward solving problems, writing pseudocode, working with and effectively using basic data types, abstract data types, control structures, code modularization and arrays. You will learn to detect errors, work with variables and loops, and discover how functions, methods, and operators work with different data types. You will also be introduced to the object paradigm including classes, inheritance, and polymorphism.

Dec 7th 2026
5-12 Weeks
Digital Signal Processing 1: Basic Concepts and Algorithms (Coursera) Coursera
École Polytechnique Fédérale de Lausanne

Digital Signal Processing 1: Basic Concepts and Algorithms (Coursera)

Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By reworking the principles of electronics, telecommunication and computer science into a unifying paradigm, DSP is a the heart of the digital revolution that brought us CDs, DVDs, MP3 players, mobile phones and countless other devices.

Dec 7th 2026
4 Weeks
Algorithmic Thinking (Part 2) (Coursera) Coursera
Rice University

Algorithmic Thinking (Part 2) (Coursera)

Experienced Computer Scientists analyze and solve computational problems at a level of abstraction that is beyond that of any particular programming language. This two-part class is designed to train students in the mathematical concepts and process of "Algorithmic Thinking", allowing them to build simpler, more efficient solutions to computational problems.

Nov 30th 2026
4 Weeks
Algorithms, Part II (Coursera) Coursera
Princeton University

Algorithms, Part II (Coursera)

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.

Dec 7th 2026
5-12 Weeks
Gen AI for Code Generation for Python (Coursera) Coursera
Edureka

Gen AI for Code Generation for Python (Coursera)

Welcome to the 'Gen AI for Code Generation for Python' course, where you'll embark on a journey to explore and develop your skills in the art of code generation with Generative AI. Throughout this short course, you will delve into various techniques for generating Python code effortlessly, ranging from simple scripts to complete end-to-end projects.

Dec 7th 2026
1 Week
Understanding and Applying Text Embeddings (Coursera) Coursera
DeepLearning.AI

Understanding and Applying Text Embeddings (Coursera)

The Vertex AI Text-Embeddings API enhances the process of generating text embeddings. These text embeddings, which are numerical representations of text, play a pivotal role in many tasks involving the identification of similar items, like Google searches, online shopping recommendations, and personalized music suggestions.

Dec 7th 2026
1 Week
An Introduction to Interactive Programming in Python (Part 1) (Coursera) Coursera
Rice University

An Introduction to Interactive Programming in Python (Part 1) (Coursera)

This two-part course is designed to help students with very little or no computing background learn the basics of building simple interactive applications. Our language of choice, Python, is an easy-to learn, high-level computer language that is used in many of the computational courses offered on Coursera. To make learning Python easy, we have developed a new browser-based programming environment that makes developing interactive applications in Python simple.

Nov 30th 2026
5-12 Weeks
Uso de bases de datos con Python (Coursera) Coursera
University of Michigan

Uso de bases de datos con Python (Coursera)

Este curso presentará a los estudiantes los conceptos básicos del lenguaje de consulta estructurado (Structured Query Language, SQL), así como el diseño básico de bases de datos para almacenar datos como parte de una iniciativa de varios pasos para recopilar, analizar y procesar datos. El curso utilizará SQLite3 como base de datos. También crearemos rastreadores web y procesos de visualización y recopilación de datos de varios pasos. Utilizaremos la biblioteca D3.js para realizar la visualización básica de datos.

Dec 7th 2026
5-12 Weeks
An Introduction to Interactive Programming in Python (Part 2) (Coursera) Coursera
Rice University

An Introduction to Interactive Programming in Python (Part 2) (Coursera)

This two-part course is designed to help students with very little or no computing background learn the basics of building simple interactive applications. Our language of choice, Python, is an easy-to learn, high-level computer language that is used in many of the computational courses offered on Coursera. To make learning Python easy, we have developed a new browser-based programming environment that makes developing interactive applications in Python simple.

Nov 30th 2026
4 Weeks