Dynamic Programming, Greedy Algorithms

Dynamic Programming, Greedy Algorithms

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

Instructor: Sriram Sankaranarayanan

Access provided by Hertz

39,033 already enrolled

4 modules

Gain insight into a topic and learn the fundamentals.

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

243 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

Memoization 30 minutes
Coinchanging Problem 30 minutes
Knapsack Problem 30 minutes
Longest Common Subsequence 30 minutes
Rod Cutting Problem and Recurrence 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

Huffman Codes 30 minutes
Greedy Algorithms 30 minutes
Greedy Interval Scheduling 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

Decision Problems and Languages 30 minutes
Polynomial Time and Certificates 30 minutes
NP Completeness Problems 30 minutes
NP Completeness Reductions 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

(62 ratings)

Sriram Sankaranarayanan

University of Colorado Boulder

5 Courses 98,201 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.36%
4 stars
15.63%
3 stars
2.46%
2 stars
1.64%
1 star
2.88%

Showing 3 of 243

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

View more reviews