When will I have access to the lectures and assignments?

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.

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

Dynamic Programming, Greedy Algorithms

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

Instructor: Sriram Sankaranarayanan

41,494 already enrolled

Included with

Learn more

4 modules

Gain insight into a topic and learn the fundamentals.

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

267 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

Module details

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

Memoization 30 minutes
Coinchanging Problem30 minutes
Knapsack Problem30 minutes
Longest Common Subsequence30 minutes
Rod Cutting Problem and Recurrence30 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

Huffman Codes30 minutes
Greedy Algorithms30 minutes
Greedy Interval Scheduling30 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

Decision Problems and Languages30 minutes
Polynomial Time and Certificates30 minutes
NP Completeness Problems30 minutes
NP Completeness Reductions30 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

(67 ratings)

Sriram Sankaranarayanan

University of Colorado Boulder

5 Courses102,448 learners

Offered by

University of Colorado Boulder

Learner reviews

5 stars
77.52%
4 stars
16.10%
3 stars
2.24%
2 stars
1.49%
1 star
2.62%

Showing 3 of 267

Reviewed on Jul 9, 2023

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

Reviewed on Dec 6, 2022

This course save me time on learning the dynamic programming. I really love the 4-steps to construct the dynamic programming. It gives me the guideline when designing DP solution.

Reviewed on Oct 17, 2024

Instructor's material was really good and was very effective in communicating the complex topics

View more reviews