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.
Dynamic Programming, Greedy Algorithms
This course is part of Foundations of Data Structures and Algorithms Specialization
Instructor: Sriram Sankaranarayanan
Sponsored by Mojatu Foundation
28,753 already enrolled
(174 reviews)
Recommended experience
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
Details to know
Add to your LinkedIn profile
17 assignments
See how employees at top companies are mastering in-demand skills
Build your subject-matter expertise
- 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
Earn a career certificate
Add this credential to your LinkedIn profile, resume, or CV
Share it on social media and in your performance review
There are 4 modules in this course
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 videos13 readings5 assignments1 programming assignment1 discussion prompt
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
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
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
Instructor
Offered by
Why people choose Coursera for their career
Learner reviews
174 reviews
- 5 stars
78.85%
- 4 stars
14.28%
- 3 stars
2.85%
- 2 stars
1.71%
- 1 star
2.28%
Showing 3 of 174
Reviewed on Oct 17, 2024
Instructor's material was really good and was very effective in communicating the complex topics
Reviewed on Apr 5, 2024
Amazing opportunity to learn! A Stanford graduate as a professor, OMG! Super bright!
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.
Recommended if you're interested in Computer Science
The Chinese University of Hong Kong
Tsinghua University
Whizlabs
Fred Hutchinson Cancer Center
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
Advance your career with an online degree
Earn a degree from world-class universities - 100% online
Join over 3,400 global companies that choose Coursera for Business
Upskill your employees to excel in the digital economy