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
Overview
Syllabus
- Divide and Conquer Algorithms
- 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.
- Dynamic Programming Algorithms
- 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.
- Greedy Algorithms
- 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.
- Intractability and Supplement on Quantum Computing
- P vs NP, Examples such as Travelling Salesperson Problem, Vertex Cover, 3-Coloring and others; Integer Linear Programming and Translating Problems into Integer Programming.
Taught by
Sriram Sankaranarayanan
Tags
Related Courses
Related articles
Reviews
5.0 rating, based on 1 Class Central review
4.6 rating at Coursera based on 165 ratings
-
This has gotten a lot harder than the previous 2 courses of the specialization. At least that's how it felt to me. When taking the time and adding in a few external learning resources, it's very doable.
For some context: I don't have an academic degree, but I've worked as a Software Engineer professionally for almost 10 years and I did an apprenticeship in Computer Science (it was fairly light on theory).
