Monthly Subscription Starting at AED 99 + VAT

Dynamic Programming, Greedy Algorithms
  • Level Expert
  • Duration 38 hours
  • Course by University of Colorado Boulder
  • Offered by

About

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

Modules

Course Overview

    • 5 Readings
    • 1 Discussion
Show info about module content

1 Discussions

  • Introduce Yourself!

5 Readings

  • Earn Academic Credit for Your Work!
  • Course Support
  • Reading: Important Prerequisites
  • Logistics: Textbook and Readings
  • Important Specialization Information

Overview of Module 1

    • 1 Readings
Show info about module content

1 Readings

  • Overview of Module 1

What Are Divide and Conquer Algorithms?

    • 1 Videos
    • 1 Readings
Show info about module content

1 Videos

  • What Are Divide and Conquer Algorithms?

1 Readings

  • CLRS Chapter 4

Max Subarray Problem Using Divide and Conquer

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Max Subarray Problem Using Divide and Conquer

1 Readings

  • CLRS Chapter 4.1

1 Quiz

  • Max Subarray Problem

Karatsuba’s Multiplication Algorithm

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Karatsuba’s Multiplication Algorithm

1 Readings

  • Jupyter Notebook on Karatsuba's Algorithm

1 Quiz

  • Karatsuba's Multiplication Algorithm

Master Method Revisited

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Master Method Revisited

1 Readings

  • CLRS Chapters 4.3 - 4.5

1 Quiz

  • Master Method

Fast Fourier Transform Algorithm

    • 5 Videos
    • 3 Readings
    • 2 Quiz
Show info about module content

5 Videos

  • FFT Part 1: Introduction and Complex Numbers
  • FFT Part 2: Definition and Interpretation of Discrete Fourier Transforms
  • FFT Part 3: Divide and Conquer Algorithm for FFT
  • Application # 1 : Fast Polynomial Multiplication using FFT
  • Application # 2: Data Analysis using FFT

3 Readings

  • Basics of Complex Numbers
  • Fourier Transforms
  • Fast Fourier Transform

2 Quiz

  • Complex Numbers and Roots of Unity
  • FFT Algorithm and Applications

Problem Set

    • 1 Programming
Show info about module content

1 Programming

  • Problem Set 1

Overview of Module 2

    • 1 Readings
Show info about module content

1 Readings

  • Overview of Module 2

Introduction to Dynamic Programming + Rod Cutting Problem

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Introduction to Dynamic Programming + Rod Cutting Problem

1 Readings

  • Rod Cutting Problem

1 Quiz

  • Rod Cutting Problem and Recurrence

Rod Cutting Problem: Memoization

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Rod Cutting Problem: Memoization

1 Readings

  • Memoization

1 Quiz

  • Memoization

Coin Changing Problem

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Coin Changing Problem

1 Readings

  • Coin Changing Problem

1 Quiz

  • Coinchanging Problem

Knapsack Problem

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Knapsack Problem

1 Readings

  • Jupyter Notebook

1 Quiz

  • Knapsack Problem

When Optimal Substructure Fails

    • 1 Videos
Show info about module content

1 Videos

  • When Optimal Substructure Fails

Dynamic Programming: Longest Common Subsequence

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Dynamic Programming: Longest Common Subsequence

1 Readings

  • CLRS Chapter 15.4

1 Quiz

  • Longest Common Subsequence

Problem Set

    • 1 Programming
Show info about module content

1 Programming

  • Problem Set 2

Overview of Module 3

    • 1 Readings
Show info about module content

1 Readings

  • Overview of Module 3

Introduction to Greedy Algorithms

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Introduction to Greedy Algorithms

1 Readings

  • CLRS Chapter 16

1 Quiz

  • Greedy Algorithms

Greedy Interval Scheduling

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Greedy Interval Scheduling

1 Readings

  • CLRS Chapters 16.1 and 16.2

1 Quiz

  • Greedy Interval Scheduling

Prefix Codes and Optimal Prefix Codes

    • 3 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

3 Videos

  • Prefix Codes
  • Huffman Codes
  • Huffman Codes: Proof of Optimality

1 Readings

  • CLRS Chapter 16.3

1 Quiz

  • Huffman Codes

Problem Set

    • 1 Programming
Show info about module content

1 Programming

  • Problem Set 3

Overview of Module 4

    • 1 Readings
Show info about module content

1 Readings

  • Overview of Module 4

Decision Problems and Languages

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Decision Problems and Languages

1 Readings

  • CLRS Chapter 34

1 Quiz

  • Decision Problems and Languages

Polynomial Time Problems

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • Polynomial Time Problems

1 Readings

  • CLRS chapter 34.1

1 Quiz

  • Polynomial Time and Certificates

NP Definition and NP Completeness

    • 2 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

2 Videos

  • NP Definition
  • NP Completeness and Reductions

1 Readings

  • CLRS Chapter 34.2 and 34.3

1 Quiz

  • NP Completeness Reductions

NP Complete Problems

    • 1 Videos
    • 1 Readings
    • 1 Quiz
Show info about module content

1 Videos

  • NP Complete Problems: Examples

1 Readings

  • CLRS Chapter 34.5

1 Quiz

  • NP Completeness Problems

Supplementary Lectures: Quantum Computing

    • 4 Videos
Show info about module content

4 Videos

  • Computation and Physics
  • Qubits and Operations
  • Bell's Inequality
  • Grover's Search Algorithm

Programming Assignment

    • 1 Programming
Show info about module content

1 Programming

  • Problem Set 4

Auto Summary

Explore key algorithm design techniques with Coursera's "Dynamic Programming, Greedy Algorithms" course, focusing on divide and conquer, dynamic programming, and greedy methods. Ideal for data science and AI enthusiasts, this expert-level course, instructed by CU Boulder, also delves into NP-completeness and optimization using linear/integer programming solvers. Offered as part of CU Boulder’s MS in Data Science or Computer Science on Coursera, it features short 8-week sessions, pay-as-you-go tuition, and performance-based admission, perfect for recent graduates and working professionals.

Sriram Sankaranarayanan
Instructor

Sriram Sankaranarayanan