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

40,953 already enrolled

Included with

4 modules

Gain insight into a topic and learn the fundamentals.

263 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.

263 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

Category: Advanced Mathematics
Category: Data Structures
Category: Pseudocode
Category: Programming Principles
Category: Computational Thinking
Category: Design Strategies
Category: Theoretical Computer Science
Category: Computer Science
Category: Algorithms
Category: Analysis

Tools you'll learn

Category: Python Programming

Details to know

Shareable certificate

Add to your LinkedIn profile

Assessments

18 assignments

Taught in English

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 videosTotal 231 minutes

What Are Divide and Conquer Algorithms?8 minutes
Max Subarray Problem Using Divide and Conquer24 minutes
Karatsuba’s Multiplication Algorithm40 minutes
Master Method Revisited28 minutes
FFT Part 1: Introduction and Complex Numbers48 minutes
FFT Part 2: Definition and Interpretation of Discrete Fourier Transforms35 minutes
FFT Part 3: Divide and Conquer Algorithm for FFT22 minutes
Application # 1 : Fast Polynomial Multiplication using FFT 9 minutes
Application # 2: Data Analysis using FFT18 minutes

16 readingsTotal 146 minutes

Course Updates and Accessibility Support1 minute
Earn Academic Credit for Your Work! 10 minutes
Course Support10 minutes
Assessment Expectations5 minutes
AI Citation and Acknowledgement10 minutes
Reading: Important Prerequisites10 minutes
Logistics: Textbook and Readings10 minutes
Important Specialization Information10 minutes
Overview of Module 110 minutes
CLRS Chapter 410 minutes
CLRS Chapter 4.110 minutes
Jupyter Notebook on Karatsuba's Algorithm10 minutes
CLRS Chapters 4.3 - 4.510 minutes
Basics of Complex Numbers10 minutes
Fourier Transforms10 minutes
Fast Fourier Transform10 minutes

6 assignmentsTotal 155 minutes

AI Policy Quiz5 minutes
Max Subarray Problem30 minutes
Karatsuba's Multiplication Algorithm30 minutes
Master Method30 minutes
Complex Numbers and Roots of Unity30 minutes
FFT Algorithm and Applications30 minutes

1 programming assignmentTotal 180 minutes

Problem Set 1180 minutes

1 discussion promptTotal 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 videosTotal 132 minutes

Introduction to Dynamic Programming + Rod Cutting Problem31 minutes
Rod Cutting Problem: Memoization24 minutes
Coin Changing Problem12 minutes
Knapsack Problem29 minutes
When Optimal Substructure Fails10 minutes
Dynamic Programming: Longest Common Subsequence25 minutes

6 readingsTotal 60 minutes

Overview of Module 210 minutes
Rod Cutting Problem10 minutes
Memoization 10 minutes
Coin Changing Problem10 minutes
Jupyter Notebook10 minutes
CLRS Chapter 15.410 minutes

5 assignmentsTotal 150 minutes

Rod Cutting Problem and Recurrence30 minutes
Memoization 30 minutes
Coinchanging Problem30 minutes
Knapsack Problem30 minutes
Longest Common Subsequence30 minutes

1 programming assignmentTotal 180 minutes

Problem Set 2180 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 videosTotal 103 minutes

Introduction to Greedy Algorithms20 minutes
Greedy Interval Scheduling23 minutes
Prefix Codes30 minutes
Huffman Codes11 minutes
Huffman Codes: Proof of Optimality 17 minutes

4 readingsTotal 40 minutes

Overview of Module 310 minutes
CLRS Chapter 1610 minutes
CLRS Chapters 16.1 and 16.210 minutes
CLRS Chapter 16.310 minutes

3 assignmentsTotal 90 minutes

Greedy Algorithms30 minutes
Greedy Interval Scheduling30 minutes
Huffman Codes30 minutes

1 programming assignmentTotal 180 minutes

Problem Set 3180 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 videosTotal 289 minutes

Decision Problems and Languages37 minutes
Polynomial Time Problems29 minutes
NP Definition29 minutes
NP Completeness and Reductions37 minutes
NP Complete Problems: Examples25 minutes
Computation and Physics30 minutes
Qubits and Operations37 minutes
Bell's Inequality22 minutes
Grover's Search Algorithm43 minutes

5 readingsTotal 50 minutes

Overview of Module 410 minutes
CLRS Chapter 34 10 minutes
CLRS chapter 34.110 minutes
CLRS Chapter 34.2 and 34.310 minutes
CLRS Chapter 34.510 minutes

4 assignmentsTotal 120 minutes

NP Completeness Reductions30 minutes
Decision Problems and Languages30 minutes
Polynomial Time and Certificates30 minutes
NP Completeness Problems30 minutes

1 programming assignmentTotal 180 minutes

Problem Set 4180 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

(65 ratings)

Sriram Sankaranarayanan

University of Colorado Boulder

5 Courses100,991 learners

Offered by

University of Colorado Boulder

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
77.56%
4 stars
15.96%
3 stars
2.28%
2 stars
1.52%
1 star
2.66%

Showing 3 of 263

Reviewed on Feb 8, 2023

I totally loved all the courses from this instructor. The content was rich, the programming assignments were instructive, and the whole course was so engaging.

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.

Reviewed on Apr 5, 2024

Amazing opportunity to learn! A Stanford graduate as a professor, OMG! Super bright!

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.

Dynamic Programming, Greedy Algorithms

Dynamic Programming, Greedy Algorithms

What you'll learn

Skills you'll gain

Tools you'll learn

Details to know

Build your subject-matter expertise

There are 4 modules in this course

Divide and Conquer Algorithms

What's included

Dynamic Programming Algorithms

What's included

Greedy Algorithms

What's included

Intractability and Supplement on Quantum Computing

What's included

Earn a career certificate

Build toward a degree

Instructor

Offered by

Why people choose Coursera for their career

Felipe M.

Jennifer J.

Larry W.

Chaitanya A.

Learner reviews

Frequently asked questions

What is a cross-listed course?

Can I take cross-listed courses to fulfill my degree requirements?

How do I upgrade and earn credit from CU Boulder?