Algorithm Design and Analysis (edX)

This course, part of the Computer Science Essentials for Software Development Professional Certificate program, is an introduction to design and analysis of algorithms, and answers along the way these and many other interesting computational questions.
You will learn about algorithms that operate on common data structures, for instance sorting and searching; advanced design and analysis techniques such as dynamic programming and greedy algorithms; advanced graph algorithms such as minimum spanning trees and shortest paths; NP-completeness theory; and approximation algorithms.
After completing this course you will be able to design efficient and correct algorithms using sophisticated data structures for complex computational tasks.

This course is part of the Computer Science Essentials for Software Development Professional Certificate

What you'll learn

• How to represent data in ways that allow you to access it efficiently in the ways you need to
• How to analyze the efficiency of algorithms
• How to bootstrap solutions on small inputs into algorithmic solutions on bigger inputs
• Solutions to several classic optimization problems
• How to critically analyze whether a locally optimal approach (greedy) can provide a globally optimal solution to a problem

Syllabus

Week 1: Mathematical Preliminaries; Asymptotic analysis and recurrence relations; Sorting and Searching; Heaps and Binary Search Trees
Week 2: Algorithm Design Paradigms - Divide-and-Conquer algorithms, Dynamic Programming, Greedy Algorithms
Week 3: Graphs and graph traversals; minimum spanning trees; shortest paths
Week 4: Flows; NP-completeness; Approximation Algorithms