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
Dynamic Programming, Greedy Algorithms
This course is part of Foundations of Data Structures and Algorithms Specialization
Instructor: Sriram Sankaranarayanan
28,216 already enrolled
Included with 
Gain insight into a topic and learn the fundamentals.
4.6
(172 reviews)
Advanced level
Recommended experience
Flexible schedule
Approx. 37 hours
Learn at your own pace
88%
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
Details to know
Shareable certificate
Add to your LinkedIn profile
Assessments
17 quizzes
Taught in English
See how employees at top companies are mastering in-demand skills
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
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 quizzes1 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 quizzes1 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 quizzes1 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 quizzes1 programming assignment
Instructor
Instructor ratings
4.6 (43 ratings)Offered by
Recommended if you're interested in Algorithms
Amazon Ads
The Chinese University of Hong Kong
University of Colorado Boulder
University of Colorado Boulder
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.¹
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
4.6
172 reviews
- 5 stars
78.61%
- 4 stars
14.45%
- 3 stars
2.89%
- 2 stars
1.73%
- 1 star
2.31%
Showing 3 of 172
RW
5
Reviewed on Apr 5, 2024
Amazing opportunity to learn! A Stanford graduate as a professor, OMG! Super bright!
DM
5
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.
YS
5
Reviewed on Jul 22, 2022
Excellent course! I really learned alot and enjoyed all the challenges and topics in your course. Thank you so much!
New to Algorithms? Start here.
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
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.