What will I get if I subscribe to this Specialization?

When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.

Is financial aid available?

Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.

Dynamic Programming, Greedy Algorithms

Grow your skills with Coursera Plus for $239/year (usually $399). Save now.

Dynamic Programming, Greedy Algorithms

This course is part of Foundations of Data Structures and Algorithms Specialization

Instructor: Sriram Sankaranarayanan

39,586 already enrolled

Included with

Learn more

4 modules

Gain insight into a topic and learn the fundamentals.

251 reviews

Advanced level

Recommended experience

Flexible schedule

4 weeks at 10 hours a week

Learn at your own pace

87%

Most learners liked this course

4 modules

Gain insight into a topic and learn the fundamentals.

251 reviews

Advanced level

Recommended experience

Flexible schedule

4 weeks at 10 hours a week

Learn at your own pace

87%

Most learners liked this course

What you'll 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

Skills you'll gain

Tools you'll learn

Python Programming

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

18 assignments

Taught in English

See how employees at top companies are mastering in-demand skills

Learn more about Coursera for Business

logos of Petrobras, TATA, Danone, Capgemini, P&G and L'Oreal

Build your subject-matter expertise

This course is part of the Foundations of Data Structures and Algorithms Specialization

When you enroll in this course, you'll also be enrolled in this Specialization.

Learn new concepts from industry experts
Gain a foundational understanding of a subject or tool
Develop job-relevant skills with hands-on projects
Earn a shareable career certificate

There are 4 modules in this course

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.

This course can be taken for academic credit as part of CU Boulder’s MS in Data Science or MS in Computer Science degrees offered on the Coursera platform. These fully accredited graduate degrees offer targeted courses, short 8-week sessions, and pay-as-you-go tuition. Admission is based on performance in three preliminary courses, not academic history. CU degrees on Coursera are ideal for recent graduates or working professionals. Learn more: MS in Data Science: https://www.coursera.org/degrees/master-of-science-data-science-boulder MS in Computer Science: https://coursera.org/degrees/ms-computer-science-boulder

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.

What's included

9 videos16 readings6 assignments1 programming assignment1 discussion prompt

9 videos Total 231 minutes

What Are Divide and Conquer Algorithms? 8 minutes
Max Subarray Problem Using Divide and Conquer 24 minutes
Karatsuba’s Multiplication Algorithm 40 minutes
Master Method Revisited 28 minutes
FFT Part 1: Introduction and Complex Numbers 48 minutes
FFT Part 2: Definition and Interpretation of Discrete Fourier Transforms 35 minutes
FFT Part 3: Divide and Conquer Algorithm for FFT 22 minutes
Application # 1 : Fast Polynomial Multiplication using FFT 9 minutes
Application # 2: Data Analysis using FFT 18 minutes

16 readings Total 146 minutes

Course Updates and Accessibility Support 1 minute
Earn Academic Credit for Your Work! 10 minutes
Course Support 10 minutes
Assessment Expectations 5 minutes
AI Citation and Acknowledgement 10 minutes
Reading: Important Prerequisites 10 minutes
Logistics: Textbook and Readings 10 minutes
Important Specialization Information 10 minutes
Overview of Module 1 10 minutes
CLRS Chapter 4 10 minutes
CLRS Chapter 4.1 10 minutes
Jupyter Notebook on Karatsuba's Algorithm 10 minutes
CLRS Chapters 4.3 - 4.5 10 minutes
Basics of Complex Numbers 10 minutes
Fourier Transforms 10 minutes
Fast Fourier Transform 10 minutes

6 assignments Total 155 minutes

AI Policy Quiz 5 minutes
Max Subarray Problem 30 minutes
Karatsuba's Multiplication Algorithm 30 minutes
Master Method 30 minutes
Complex Numbers and Roots of Unity 30 minutes
FFT Algorithm and Applications 30 minutes

1 programming assignment Total 180 minutes

Problem Set 1 180 minutes

1 discussion prompt Total 10 minutes

Introduce Yourself! 10 minutes

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.

What's included

6 videos6 readings5 assignments1 programming assignment

6 videos Total 132 minutes

Introduction to Dynamic Programming + Rod Cutting Problem 31 minutes
Rod Cutting Problem: Memoization 24 minutes
Coin Changing Problem 12 minutes
Knapsack Problem 29 minutes
When Optimal Substructure Fails 10 minutes
Dynamic Programming: Longest Common Subsequence 25 minutes

6 readings Total 60 minutes

Overview of Module 2 10 minutes
Rod Cutting Problem 10 minutes
Memoization 10 minutes
Coin Changing Problem 10 minutes
Jupyter Notebook 10 minutes
CLRS Chapter 15.4 10 minutes

5 assignments Total 150 minutes

Rod Cutting Problem and Recurrence 30 minutes
Memoization 30 minutes
Coinchanging Problem 30 minutes
Knapsack Problem 30 minutes
Longest Common Subsequence 30 minutes

1 programming assignment Total 180 minutes

Problem Set 2 180 minutes

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.

What's included

5 videos4 readings3 assignments1 programming assignment

5 videos Total 103 minutes

Introduction to Greedy Algorithms 20 minutes
Greedy Interval Scheduling 23 minutes
Prefix Codes 30 minutes
Huffman Codes 11 minutes
Huffman Codes: Proof of Optimality 17 minutes

4 readings Total 40 minutes

Overview of Module 3 10 minutes
CLRS Chapter 16 10 minutes
CLRS Chapters 16.1 and 16.2 10 minutes
CLRS Chapter 16.3 10 minutes

3 assignments Total 90 minutes

Greedy Algorithms 30 minutes
Greedy Interval Scheduling 30 minutes
Huffman Codes 30 minutes

1 programming assignment Total 180 minutes

Problem Set 3 180 minutes

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

What's included

9 videos5 readings4 assignments1 programming assignment

9 videos Total 289 minutes

Decision Problems and Languages 37 minutes
Polynomial Time Problems 29 minutes
NP Definition 29 minutes
NP Completeness and Reductions 37 minutes
NP Complete Problems: Examples 25 minutes
Computation and Physics 30 minutes
Qubits and Operations 37 minutes
Bell's Inequality 22 minutes
Grover's Search Algorithm 43 minutes

5 readings Total 50 minutes

Overview of Module 4 10 minutes
CLRS Chapter 34 10 minutes
CLRS chapter 34.1 10 minutes
CLRS Chapter 34.2 and 34.3 10 minutes
CLRS Chapter 34.5 10 minutes

4 assignments Total 120 minutes

NP Completeness Reductions 30 minutes
Decision Problems and Languages 30 minutes
Polynomial Time and Certificates 30 minutes
NP Completeness Problems 30 minutes

1 programming assignment Total 180 minutes

Problem Set 4 180 minutes

Earn a career certificate

Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.

Build toward a degree

This course is part of the following degree program(s) offered by University of Colorado Boulder. If you are admitted and enroll, your completed coursework may count toward your degree learning and your progress can transfer with you.¹

Instructor

Instructor ratings

(64 ratings)

Sriram Sankaranarayanan

University of Colorado Boulder

5 Courses 99,116 learners

Offered by

University of Colorado Boulder

Explore more from Algorithms

University of Colorado Boulder
Approximation Algorithms and Linear Programming
Course
Packt
Advanced Algorithms and Problem-Solving Techniques
Course
University of Colorado Boulder
Foundations of Data Structures and Algorithms
Specialization
Stanford University
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
Course

Why people choose Coursera for their career

Felipe M.

Learner since 2018

"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."

Jennifer J.

Learner since 2020

"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."

Larry W.

Learner since 2021

"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."

Chaitanya A.

"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."

Learner reviews

5 stars
76.89%
4 stars
16.33%
3 stars
2.39%
2 stars
1.59%
1 star
2.78%

Showing 3 of 251

Reviewed on Sep 18, 2022

Great work from professor Sriram Sankaranarayanan explaining such complex material. I wish we could review more examples during the class (specially Dynamic Programming ones).

Reviewed on Jul 9, 2023

Clear and helpful instructions but the last assignment is so hard.

Reviewed on Sep 20, 2021

Excellent. This course covers some difficult topics, but the lectures and homework assignments were superb and made them quite approachable.

View more reviews

Open new doors with Coursera Plus

Unlimited access to 10,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription

Learn more

Advance your career with an online degree

Earn a degree from world-class universities - 100% online

Explore degrees

Join over 3,400 global companies that choose Coursera for Business

Upskill your employees to excel in the digital economy

Learn more

Frequently asked questions

A cross-listed course is offered under two or more CU Boulder degree programs on Coursera. For example, Dynamic Programming, Greedy Algorithms is offered as both CSCA 5414 for the MS-CS and DTSA 5503 for the MS-DS.

· You may not earn credit for more than one version of a cross-listed course.

· You can identify cross-listed courses by checking your program’s student handbook.

· Your transcript will be affected. Cross-listed courses are considered equivalent when evaluating graduation requirements. However, we encourage you to take your program's versions of cross-listed courses (when available) to ensure your CU transcript reflects the substantial amount of coursework you are completing directly in your home department. Any courses you complete from another program will appear on your CU transcript with that program’s course prefix (e.g., DTSA vs. CSCA).

· Programs may have different minimum grade requirements for admission and graduation. For example, the MS-DS requires a C or better on all courses for graduation (and a 3.0 pathway GPA for admission), whereas the MS-CS requires a B or better on all breadth courses and a C or better on all elective courses for graduation (and a B or better on each pathway course for admission). All programs require students to maintain a 3.0 cumulative GPA for admission and graduation.

Yes. Cross-listed courses are considered equivalent when evaluating graduation requirements. You can identify cross-listed courses by checking your program’s student handbook.

You may upgrade and pay tuition during any open enrollment period to earn graduate-level CU Boulder credit for << this course/ courses in this specialization>>. Because << this course is / these courses are >> cross listed in both the MS in Computer Science and the MS in Data Science programs, you will need to determine which program you would like to earn the credit from before you upgrade.

MS in Data Science (MS-DS) Credit: To upgrade to the for-credit data science (DTSA) version of << this course / these courses >>, use the MS-DS enrollment form. See How It Works.

MS in Computer Science (MS-CS) Credit: To upgrade to the for-credit computer science (CSCA) version of << this course / these courses >>, use the MS-CS enrollment form. See How It Works.

If you are unsure of which program is the best fit for you, review the MS-CS and MS-DS program websites, and then contact datascience@colorado.edu or mscscoursera-info@colorado.edu if you still have questions.

To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.